Speedy Performance Estimation for Neural Architecture Search
Authors: Binxin Ru
Clare Lyle
Lisa Schut
Miroslav Fil
Mark van der Wilk
Yarin Gal
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: neural architecture search
generalisation
performance estimation

Abstract: Reliable yet efficient evaluation of generalisation performance of a proposed architecture is crucial to the success of neural architecture search (NAS). Traditional approaches face a variety of limitations: training each architecture to completion is prohibitively expensive, early stopped validation accuracy may correlate poorly with fully trained performance, and model-based estimators require large training sets. We instead propose to estimate the final test performance based on a simple measure of training speed. Our estimator is theoretically motivated by the connection between generalisation and training speed, and is also inspired by the reformulation of a PAC-Bayes bound under the Bayesian setting. Our model-free estimator is simple, efficient, and cheap to implement, and does not require hyperparameter-tuning or surrogate training before deployment. We demonstrate on various NAS search spaces that our estimator consistently outperforms other alternatives in achieving better correlation with the true test performance rankings. We further show that our estimator can be easily incorporated into both query-based and one-shot NAS methods to improve the speed or quality of the search.

Speedy Performance Estimation for Neural Architecture Search
Binxin Ru
Clare Lyle'
Lisa Schut
Miroslav Fil
Mark van der Wilk?
Yarin Gal
OATML Group, Department of Computer Science, University of Oxford, UK Department of Computing, Imperial College London, UK
Abstract
Reliable yet efficient evaluation of generalisation performance of a proposed archi- tecture is crucial to the success of neural architecture search (NAS). Traditional approaches face variety of limitations: training each architecture completion is prohibitively expensive, early stopped validation accuracy may correlate poorly with fully trained performance, and model-based estimators require large train- ing sets. We instead propose to estimate the final test performance based on a simple measure of training speed. Our estimator is theoretically motivated by the connection between generalisation and training speed, and is also inspired by the reformulation of PAC-Bayes bound under the Bayesian setting. Our model- free estimator is simple, efficient, and cheap to implement, and does not require syperparameter-tuniinn or surrogate training before deployment. We demonstrate on various NAS search spaces that our estimator consistently outperforms other alternatives in achieving better correlation with the true test performance rankings. We further show that our estimator can be easily incorporated into both query-based and one-shot NAS methods to improve the speed or quality the search.
Introduction
Reliably estimating the generalisation performance of proposed architecture is crucial to the success
of Neural Architecture Search (NAS) but has always been major bottleneck in NAS algorithms (13).
The traditional approach of training each architecture for a large number epochs and evaluating
validation data (full training) provides reliable performance measure, but requires prohibitively
large computational resources on the order of thousands of GPU days [55] 39 56 38 [3]. This
motivates the development of methods for speeding up performance estimation to make NAS practical for limited computing budgets.
A popular simple approach is early-stopping, which offers low-fidelity approximation of generalisa- tion performance by training for fewer epochs 14 25). However, if we stop training early and evaluate the set of models validation data, their relative performance ranking may not correlate well with the performance ranking of the fully-trained models (53), i.c. their relative performance on the test set after the entire training budget has been used. Another line of work focuses on learning curve extrapolation [10] 23 which trains a surrogate model to predict the final generalisation meeta-featrres of the architecture. However, the training of the surrogate often requires hundreds of fully evaluated architectures to achieve satisfac- tory extrapolation performance and the sypee-pprammttrs of the surrogate also need be optimised. Alternatively, the idea weight sharing adopted one-shot NAS methods to speed up evaluation
performance based the initial learning curve
"quual contribution. Correspondence robingrobots. ox. ac.uk.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Despite leading to significant cost-saving, weight sharing heavily underestimates the true performance of good architectures and is unreliable in predicting the relative ranking among
36 28
47
A more recent group of estimators claim to be zero-cost 32 Yet, their performance often not competitive with the state of the art, inconsistent across tasks and cannot be
architectures 49 52
further improved with greater training budgets.
In view of the above limitations, we propose a simple model-free method, Training Speed Estimation (TSE), which provides a reliable yet computationally cheap estimate of the generalisation performance ranking of set of architectures. Our method is inspired by recent empirical and theoretical results linking training speed and generalisation [17 [0 and measures the training speed of an architecture by summing the training losses of the commonly show that our estimator can outperform strong existing approaches to predict the relative performance ranking among architectures, and can remain effective for a variety of search spaces and datasets. Moreover, we verify its usefulness under different NAS settings and find it can speed up query-based NAS approaches significantly as well improve the performance of one shot and differentiable NAS. Our code is available at pettps://githin com wwwm/uuwiniinnss.........
SGD optimiser during training. We empirically
2 Method
The theoretical relationship between training speed and generalisation is described in a number of existing works. Stability-based generalisation bounds for SGD [17 29] bound the generalisation gap of a model based on the number of optimisation steps used to train it. These bounds predict that models which train faster obtain a lower worst-case generalisation error. In complexity measure bound both
Motivation
networks of sufficient width, neural tangent kernel-inspiee the worst-case generalisation gap and the rate of convergence of (full- full-batch) gradient descent 6. However, these bounds cannot distinguish between models that are trained for the same number of steps but attain near-zero loss at different rates as they ignore the training trajectory.
We instead draw inspiration from another approach which incorporates properties of the trajectory taken during SGD, seen in the cooumation-thhorede generalisation bounds of (33] and [34]. These bounds depend the variance of gradients computed during training, quantity which provides first-order approximation of training speed by quantifying how well gradient updates computed for one mini-batch generalize to other points in the training set. In view of this link, the empirical and theoretical findings in recent work [15 43 which show that a notion of the variance of gradients over the training data is correlated with generalisation, become another piece of supporting evidence for training speed as a measure of generalisation.
Finally, 30 prove that, in the setting of linear models and infinitely wide deep models performing Bayesian updates, the marginal likelihood, which a theoretically-justieee tool for model selection in Bayesian learning, can be bounded by notion of training speed. This notion of training speed is defined as a sum of negative log predictive likelihoods, terms that resemble the losses on new data points seen by the model during online learning procedure. Maximising the marginal likelihood is also equivalent to minimising a PAC-Bayesian bound on the generalisation error of a model, as shown by [16]. In particular, this suggests that using the TSE approach for model selection in Bayesian models is equivalent to minimizing an estimate of a PAC- Bayes bound. Because the NAS settings we consider in experiments use neural networks rather than Bayesian models and due to space constraints, we defer the statement and proof of this result to Appendix A.
Training Speed Estimation The results described above suggest that leveraging notion of training speed may benefit model selection procedures in NAS. Many such notions exist in the generalisation literature: [18) count the number of optimisation steps needed to attain loss below a specified threshold, while [17 consider the total number of optimisation steps taken. Both measures are strong predictors of generalisation after training, yet neither is suitable for NAS, where we seek to stop training as early as possible if the model is not promising.
We draw inspiration from the Bayesian perspective and the PAC- MAC-Bayesian bound discussed above and present an alternate estimator of training speed that amounts to the area under the model's training curve. Models that train quickly attain a low loss after few training steps, and so will have lower area-under-curg than those which train slowly. This addresses the shortcomings of the previous two methods as it is able to distinguish models both carly and late in training.

---

Definition 1 (Training Speed Estimator). Let E denote loss function, (x) the output of a neural network f with input x and parameters 6. and let fr,, denote the parameters of the network after epochs and mini-batches of SGD. After training the network for I epoch we sum the training losses collected so far to get the following Training Speed Estimate (TSE):
T Σ
B
TSE =
e
(J....
B
where is the training loss of a bati- Yi) at epoch t and B is the number of training steps within an epoch.
This estimator weights the losses accumulated during every epoch equally. However, recent work suggests that training dynamies of neural networks in the very early epochs often unstable and not always informative of properties of the converged networks [24). Therefore, we hypothesise that estimator of network training speed that assigns higher weights to later epochs may exhibit better correlation with the true generalisation performance of the final trained network. On the other hand, it is common for neural networks overfit on their training data and reach near-zero loss after sufficient optimisation steps, so attempting to measure training speed solely based on the epochs near the end of training will be difficult and likely suffer degraded performance on model selection.
To verify whether is beneficial to ignore or downplay the information from early epochs of training, propose two variants of our estimator. The first, TSE-E, treats the first few epochs phase for ir,; to converge to a stable distribution P(0) and starts the sum from epoch = - F + 1 instead of 1. In the case where F 1, we start the sum at T and our estimator corresponds to the sum over training losses within the most recent epoch t = T.
burn-in
B
T TSE-EMA Σ
B E
TSE-E Σ
e (f... L 1=1
(X),..))
B
B
The second, TSE-EMA, does not completely discard the information from the early training trajectory but takes an exponential moving average of the sum of training losses with y = 0.9, thus assigning higher weight to the sum of losses obtained in later training epochs.
We empirically show in Section 4.2 that our proposed TSE and its variants (TSE-E and TSE-EMA), despite their simple form, can reliably estimate the generalisation performance of neural architectures with a very small training budget, can remain effective for a large range of training epochs, and robust to the choice of hyperparameters such as the summation window E and the decay rate y. However, our estimator is not meant to replace the validation accuracy at the end of training or when the user can afford large training budget. In those settings, validation accuracy remains as the gold standard for evaluating the true test performance of architectures. Ours is just a speedy performance estimator for NAS, aimed at giving an indication early in training about an architecture's generalisation potential under fixed training set-up.
Our choice of using the training loss, instead of the validation loss, measure training speed is an important component of the proposed method. While it is possible to formulate an alternative estimator, which sums the validation losses of a model early in training, this estimator would no longer be measuring training speed. In particular, such an estimator would not capture the generalisation of gradient updates from one mini-batch later mini-batches in the data to the same extent as TSE does. Indeed, we hypothesise that once the optimisation process has reached local minimum, the sum over validation losses more closely resembles the expected loss over parameters sampled via noisy SGD steps around this minimum. We show in Figure T and Appendix that our proposed sum over training losses (TSE) outperforms the sum over validation losses (SoVL) in ranking models in agreement with their true test performance.
rrriuccereduction technique that estimates
3 Related Work
Various approaches have been developed to speed up architecture performance estimation, thus improving the efficiency of NAS. Low-fidelity estimation methods accelerate NAS by using the
2''' can be far from the total training epochs Tend used in complete training
3

---

validation accuracy obtained after training architectures for fewer epochs (namely early-stopping) 27 14 [66 [33, training a down-scaled model with fewer cells during the search phase [56] [8].
or training on a subset of the data [22]. However, low-fidelity estimates underestimate the true performance of the architecture and can change the relative ranking among architectures [3]. This
undesirable effect on relative ranking is more prominent when the cheap approximation set-up is
dissimilar to the full training procedure [53]. As shown in Fig. [bellw, the validation accuracy at early epochs of training suffers low rank correlation with the final test performance, Another class of performance estimation methods trains a regression model to extrapolate the learning curve from what is observed in the initial phase of training or predict the final test accuracy purely based on architecture structure. Regression model choices that have been explored include Gaussian processes with tailored kernel function 4T 19]. ensemble of parametric functions [TO] tree-based models 77 20, 50], Bayesian neural network [23] and a u-support vector machine regressor (u-SVR) ) 3 which achieves oath-offt prediction performance (45). Although these model- methods can often predict the performance ranking better than their model-free early-stopping counterparts, they require relatively large amount of fully evaluated architecture data (e.g. 100 fully evaluated architectures in (3) to train the regression surrogate properly and optimise the model hyperparameters in order to achieve good prediction performance. The high computational cost of collecting the training set makes such model-based methods less favourable for NAS unless the practitioner has already evaluated hundreds of architectures on the target task. Moreover, both low-fidelity estimates and learning curve extrapolation estimators are empirically developed and lack theoretical motivation.
Weight sharing is employed in one-shot or gradient-based NAS methods to reduce computational costs 36 28 47 Under the weight-sharing setting, all architectures are considered as subnetworks of a trained while the architectures (subnetworks) inherit the corresponding weights from the supemettwrk. This removes the need for retraining each architecture during the search and thus achieves significant speed-up. However, the weight sharing ranking among architectures often correlates poorly with the true performance ranking 44 152 (4), meaning architectures chosen by one-shot NAS are likely to be sub-optimal when evaluated independently [54]. In Section 4.4 we demonstrate that we improve the performance of weight sharing correctly ranking architectures by combining our estimator with it.
supemetwork. Only the weights of the supernetwork
Recently, several works propose to estimate network performance without training by using methods from the pruning literature [1] examining the covariance of input gradients across different input images (2). Such methods incur near-zero computational costs but their performances are often not competitive and do not generalise well to larger search spaces, as shown in Section 4.2 below. Moreover, these methods can not be improved with additional training budget. Another line of work studies the effect of architecture encoding on speeding up the search 448 44 40). However, learning better latent representation for architectures is orthogonal to the performance estimation.
Apart from the above mentioned performance estimators used in NAS, many complexity measures have been proposed to analyse the generalisation performance of deep neural networks. [18) provides rigorous empirical analysis of over 40 such measures. This investigation finds that tharpness-basee (including PAC-Bayesiee bounds) obtain a good correlation with test set performance, but their estimation require adding randomly generated perturbations to the network parameters and the magnitude of the perturbations needs to be carefully optimised with additional complexity
measures [31 21 35 12
training, making them unsuitable performance estimators for NAS. Optimisation-bate measures, which counts the number of steps required to reach a certain loss value, also perform well in predicting generalisation. However, as discussed in Section 2 is closely related our approach but not as easy to deploy as our estimators under the NAS setting.
4 Experiments
In this section, we first evaluate the quality of our proposed estimators in predicting the generalisation performance of architectures against a number of baselines (Section ).2). and then demonstrate that simple incorporation of our estimators can significantly improve the search speed and quality of both query-based and weight-sharing NAS (Sections 4.3 (.4).
We measure the true generalisation performance of architectures with their final test accuracy after being completely trained for Tend epochs. To ensure fair assessment of the architecture performance only, we adopt the common NAS protocol where all architectures searched/compared are trained

---

Table 1: NAS search spaces used. The true test accuracy of architectures from each search space is obtained after training with SGD on the corresponding image datasets for Tend epochs. Neotal denotes the total possible architectures exist in the search space and N Ssmpltes denotes the number of architectures we sample/generate for our experiments.
Search space
Tend
N Naamples
Niotal
Image datasets
NASBench-22 201 (NB201) [1
200
6466
15625
CIFAR1O, CIFAR100, ImageNet-16-120
DARTS 28 42
100
5000
(
CIFARIO
ResNet/ResNeXi 37
100
50000
(
CIFAR10
RandWiredNN (RWNN) 46
250
69 8
((2878)
Flower102
and evaluated under the same set of byper-parameters. Also following [50] and [ we compare different estimators based on their Spearman's 's rank correlation which measures how well their predicted ranking correlates with the true test ranking among architectures.
We compare the following performance estimation methods: our proposed estimators TSE, TSE- EMA and TSE-E described in Section 2 and simply the training losses at each mini batch (TLmini). Sum of validation losses over all preceding epochs (SoVL is similar to TSE but uses the validation losses. Validation accuracy at an early epoch (VAccES) corresponds to the early-stopping practice whereby the user estimates the final test performance of a network using its validation accuracy at an early epoch T < Tend- The learning curve extrapolation (LeSVR) method is the sfate-of-the-arr extrapolation approach proposed in [3] which trains a v-SVR on previ- ously evaluated architecture data to predict the final test accuracy of new architectures. The inputs for the SVR regression model comprise architecture meta-features and learning curve features up to epoch T. In our experiments, we optimise the SVR hyperparameters via cross-validation following [3]. Three recently proposed zero-cost basclines are also included: an estimator based on input Jacobian covariance (JavCov) 332 and two adapted from pruning techniques SNIP and SynFlow [ We also compared to XGBoost and LGBoost 20 in Appendix H.
We run experiments on architectures generated from diverse set of NAS search spaces listed in Table show that our estimators generalise well (more details are provided in Appendix B). Note N Nsamples = 6466 for NASBench-201 (NB201) as it is the number of unique architectures in the space. We use the architecture information released in NAS-Bench-301 [42] for DARTS and in (37 for ResNet and ResNeXt. As for RandWiredNN (RWNN) search space [46] 40], although the number of possible randomly wired architectures are immense, they are generated via a random graph generator which is defined by 3 hyperparameters. We thus uniformly sampled 69 sets of hyperparameter values for the generator and generated randomly wired neural networks from each hyperparameter value, leading Naamples 69 x 8 552. Due to space constraints, we include the results on selecting among the generator hyperparameters for RWNN in Appendix E, All experiments conducted on an internal cluster of 16 RTX2080 GPUs.
4.1 Hyperparameter of TSE estimators
Our proposed TSE estimators require very few hyperparametens: the summation window size E for TSE-E and the decay rate for TSE-EMA, and we show empirically that our estimators are robust to these hyperparameters. For the summation window size E, we test different size values, various search spaces and image datasets in Appendix D and find that E' = consistently gives the best results across all cases. This, together with the almost monotonic improvement of our estimator's 's rank correlation score over the training budgets, supports our hypothesis discussed in Section 2 that training information in the more recent epochs is more valuable for performance estimation. Note that TSE-E with E corresponds the sum of training losses over all the mini-batches in one single epoch. We also conducted an ablation study on summing training losses below one epoch, E [0.1, 0.3. 0.5, 0.7 in Appendix D. We observe again that summing over the entire epoch EE- = 1) gives the best performance; this might be because E = 1
E E [1, 10, 20. 20....,70,
NNtee, flip the sign of TTSETSSEEMA/TSE E/SovL/TLmini (which we want minimise) to compare the Spearman's rank correlation the other methods (which we want to maximise). 'For example, E = 0.1 corresponds to the sum of training losses over the last 10% of the mini batcheb in an epoch
5

---

1.00
0.95
0.55
0.25
0.35
Bank Comeatton
0.50
Bank Correatonn
0.50
Rank Concatton
0.90
Bank Cordation
0.85
0.05
0.83
0.85
9.80
0.00
0.00
0.80
0.75
0.75
0.30
0.65
00.581
0.65
0.55
.0.880
0.50
0.50
0.60
0.11
0.50
2.50
Fraction of
Fraction Teee
Froction Tire
Fraction of
(a) NB201-CIFARI0
(h) NB201- 100
(c) NB201- -Imgeeet
(d) RWNN-Flowert
0.50
0.20
0.50
Darti: Mereeeal-.o on
Rand Seddle
0:40
0.00
3.4
0.00
0:30
0.75
13
0:75
0.2
0.0
0.64
6.24
0.50
Fraction of Taue
Fraction
Fraztion
(c) ResNet all
(I) ResNet top 1% VAcCES
gg) ResNeXt all
(h) ResNeXt top 1%
TSE-EMA
TSE-E
TSE
SeVL
LcSVR
SynFlow
SNIP
JacCov
Figure I: Rank correlation performance of various baselines for architectures from a variety of search
spaces: (a) to (c) NB201 architectures on three image datasets, (d) RWNNs on Flowers 102 and (e) to (h) ResNet and ResNeXt architectures CIFARIO. In all cases, TSE-EMA and TSE-E achieve superior rank correlation with the true test performance in much fewer epochs than other baselines. In (f) and (g), we evaluate estimators that our TSE-EMA and TSE-E can remain competitive on ranking among top architectures, which particularly desirable for NAS. In (a) and (c), we mark SNIP in violet dotted line labelled with its rank correlation value as it falls out of the plotted range.
the top 1% of the NesNet/ResNext architectures and show
covers the entire training set as is done by the Bayesian marginal likelihood and PAC-Bayes bounds, which are the theoretical inspirations for our method. On the other hand, we observe that F 2 0.3 can achieve relatively close performance as E' 1, thus motivating our use of a small number of mini-batches to estimate TSE in one-shot and gradient-basee based NAS in Section 4.4
As for 7. we show in Appendix D that TSE-EMA is robust range of popular choices y E [0.9. 0.95, 0.99, 0.999] across various datasets and search spaces. Specifically, the performance difference among these y values are almost indistinguishable compared the difference between TSE-EMA and TSE-E. Thus, we set E = 1 and = 0.999 in all the following experiments and recommend them as the default choice for potential users who want apply TSE-E and TSE-EMA on new task without additional tuning.
4.2 Comparison of Performance Estimation Quality
Robustness across different NAS search spaces We now compare our TSE estimators against a variety of other baselines. To mimic the realistic NAS setting 133, we assume that all of the estimators can only use the information from early training epochs and limit the maximum budget to T < 0.57..dd in this set of experiments. This is because NAS methods often need to evaluate hundreds of architectures or more during the search and thus rarely use evaluation budget beyond 0.5Tend so as to keep the search cost practical/affordaal.. The results on a variety of the search spaces shown in Fig. [ Our proposed estimator ESE-EMA and TSE-E, despite their simple form and cheap computation, outperform all other methods under limited evaluation budget < 0.5I end for all search spaces and image datasets. They also remain very competitive top 1% ResNet/ResNeXt architectures as shown in Fig. f and (g). This is particularly desirable for NAS for which we need to distinguish not only the good architectures from the bad ones but more importantly the top architectures from the merely good ones.
ranking among the
It is worth highlighting that TSE-EMA achieves superior performance over TSE-E especially when is small. This suggests that although the training dynamics at early epochs might be noisy, they still carry some useful information for explaining the generalisation performance of the network.

---

0.20
1.0
0.55
MyM
Rank Correation
Coreaaatn
0.9
Bank Coree Ston
0.8
0.7
3.85
2.6
5.00
...60.......
0.6
0.5
2.55
0.34
0.16
0.02
0.31
.0.002
0.50
0.23
0.327 7
0.50
0.03
0.32
0.50
Fraction
Fraction of
Fraction
(a) 8 cells, 1r=0.025, bs=96, cosine scheduler
(b) 20 cells, 1r-0.025, bs= cosine scheduler
(c) 20 cells, 1=-0.1, bs= (d) 20 cells, 1r=0.05,
step-decay scheduler
by= cosine scheduler
TSF-EMA
TSE-E
VACCES
LCVVR
SoVL
SNPP
SynFiow
JacCov
TLmini
Figure 2: Rank correlation performance of various baselines for 5000 small 8-cell architectures (a) and 150 large 20-cell architectures (b) to (d) from DARTS search space CIFAR1O. We use NASS-Bench-301 dataset(NAS301) for computing (a) and for large architectures, we test three training hyperparameter set-ups with different initial learning rates, learning rate schedulers and batch sizes as denoted in the subcaptions. On all four settings, our TSE-E again consistently achieves superior rank correlation in fewer epochs than other baselines. Note all three zero-cost estimators perform poorly (below the plotted range) on DARTS search space across all settings. We denote them in dotted lines with their rank correlation value labelled.
The learning curve extrapolation method, LcSVR, is competitive. However, the method requires 100 fully trained architecture data to fit the regression surrogate and optimise its hyperparamters via cross validation; a large amount of computational resources are needed to collect these training data in practice. The zero-cost measures JacCov and SynFlow achieve good rank correlation initialisation but are quickly overtaken by T'SE-EMA and TSE-E once the training budget exceeds 6-7 epochs. SNIP performs poorly and falls out of the plot range in Fig. | (a) and (c).
We further validate on the architectures from the more popular search space used in DARTS. One potential concern is that if models are trained using different hyperparameters that influence the learning curve (e.g. learning rate), the prediction performance of our proposed estimators will be affected. However, this is not a problem in NAS because almost all existing NAS methods [1] 46 28 42 45] search for the optimal architecture under a fixed set of training hyperparameters. We also follow this fxeed-hyperpuramter set-up in our work. Verifying the quality of various estimators for predicting the generalisation performance across different hyperparameters lies outside the scope of this paper but present an interesting direction for future work.
Robustness across different NAS set-ups Here, conduct experiments to verify the robustness of our estimators across different NAS set-ups. The relative test performance ranking among the same set of architectures can vary across different set-ups [49]. On top of the architecture data from NASS-Bench-300 [42), we also generate several additional architecture datasets; each dataset correspond to different set-up (e.g. different architecture depth, initial learning rate, learning rate scheduler and batch size) and contains 150 large 20-cell architectures which are randomly sampled from the DARTS space and evaluated on CIFARIO. The results in Fig. 2 show that our estimator consistently outperforms all the competing methods in comparing architectures under different NAS set-ups. Note here the curve of TLmini corresponds to the average rank correlation between final test accuracy and the mini-hatch training loss over the epoch. The clear performance gain of our TSE estimators over TLmini supports our claim that is the sum of training losses, which measures the training speed and thus carries the theoretical motivations explained in Section 2 instead of simply the training loss at a single mini-batch, that gives a good estimation of generalisation performance. Note the rank correlation of all zero-cost measures drop significantly (e.g. SynFlow drops from 0.74 on NB201 to below 0.2) on the DARTS search space, and even do worse than the training losses at the first few mini-batche (TLmini at T=1). Also zero-cost measures do not take into account the training set-up when estimating architecture performance and thus their rank correlation with the true test accuracy varies largely across the set-ups. Such inconsistent prediction performance, especially given the measures' weak performance on the more practical search space, might be undesirable for real-world NAS applications.
7

---

1.0
Rank Correlation
Rank Correlation
0.9
0.0
0.0
0.7
0.6
0.03
0.17
1.00
0.03
0.17
1.00
Fraction Texd
Fraction Tend
(a) NB201-CIIAAAN CIFARIO
(b) 100
EMA
VAcCES
N_s=10
5_
N_s=100
N_s=500
Figure 3: Rank correlation performance up to = Tend. If the users want to apply our estimators for large training budget, they can estimate the effective range of our estimators based on the minimum epoch To when overfitting happens among the N, observed architectures. They can then stop estimators early at 0.9T. (marked by vertical lines) or switch back to validation accuracy beyond that.
Vill AcoTT-10)
TSE EMARTHER
hound
Dounst
trm Drouna
thousl
Oime Trouns)
thoun)
(a) Regularised Evolution (RE)
(b) Bayesian Optimisation (BO)
Figure 4: NAS performance of RE and BO in combined with final validation accuracy Val Acc (T=200), carly-stopping validation accuracy Val Ace (T=10) and our estimator TSE-EMA(T=10) on NB201. For each subplot, experiment on the three image datasets: CIFARIO (left), CIFAR100 (middle) and ImageNet (right). TSE-EMA leads to the fastest convergence to the top performing architectures in all cases. The black dashed line is to facilitate the comparison of runtime taken to reach a certain test error among different variants.
Procedure to decide the elffective training budget We include two examples showing the perfor- mance of our estimator for training budgets beyond 0.57 in Fig. 3 Our estimators can outperform the carly-stopping validation accuracy for relatively wide range of training budgets. Although they will eventually be overtaken by validation accuracy as the training budget approaches Tend as discussed in Section [2] the large training budget regime is less interesting for NAS where we want to maximise the cost-saving by using performance estimators. However, if the user wants to apply our estimators with relatively large training budget, we propose simple method here to estimate when our estimators would be less effective than validation accuracy. We notice that that our estimators, TSE-EMA and TSE-F, become less effective when the architectures compared start to overfit because both of them rely heavily on the lastest-epoch training losses to measure training speed, which is difficult to estimate when the training losses become too small. Thus, if we observe one of the architectures compared overfits beyond To < Tend, can stop the computation of TSE-E and TSE-EMA early by reverting to a checkpoint at T 0.91. We randomly sample N, 10. 50, 100, 500 architectures out of all architectures compared and assume that we have access to their full learning curves. We then decide the threshold training budget 0.9T, (vertical lines) as the minimum training epoch that overfitting happens among these N, architectures. We repeat this for 100 random seeds and plot the mean and standard error of the threshold for each N, in Fig. 3 is evident that
find quite reliable threshold with sample size small as N, 10. Please refer to Appendix F for more analyses.
4.3 Speed up Query-based NAS
In this section, we demonstrate the usefulness of our estimator for NAS by incorporating TSE-EMA,
at T = 10 into several query-based NAS search strategies: Regularised Evolution [38 (a) in Fig.
4). Bayesian Optimisation (S] (b) in Fig. 4 and Random Search 4 (Appendix G). We perform architecture search on NB201 search space. We compare this against the other two benchmarks
which use the final validation accuracy at T Tend 200, denoted as Val Ace (T=200) and the
carly-stop validation accuracy at T 10, denoted as Val Ace (T=10), respectively to evaluate the
8

---

Table 2: Results of performance estimators in one-shot NAS setting over 3 supernetwork training initialisations. For each supernetwor, we randomly sample 500 random subnetworks for DARTS and 200 for NB201, and compute their TSE, Val Acc after inheriting the supernetwork weights and training for B additional mini-batches. Rank correlation measures the estimators' correlation with the rankings of the true test accuracies of subnetworks when trained from scratch independently, and we compute the average test accuracy of the top 10 architectures identified by different estimators from all the randomly sampled subnetworks.
Rank Correlation
Average Accuracy of Top 10 Architectures
B
Estimator
NB20I-CIFARIO
DARTS
NB201-CIFARI0
DARTS
RandNAS
FairNAS
MultiPaths
RandNAS
RandNAS
FairNAS
MultiPaths
RandNAS
TSE
0.70 (0.02)
0.84 (0.01)
0.83 (0.01)
0.304).04)
92.67 (0.12
92.7 (0.1)
92.63 (0.12)
93.64(0.04)
100
Val Ace
0.44 (0.15)
0.56 (0.17)
0.67 (0.05)
0.11(0.04)
91.47 (0.31)
91.73 (0.21)
91.77 (0.78)
93.20(0.04)
TSE
0.70 (0.03)
0,850 (0.01)
0.83 (0.01)
0.32(0.04)
92.70 (0.00)
92.77 (0.06)
92.73 (0.06)
93.55(0.04)
200
Val Ace
0.41 (0.10)
0.56 (0.17)
0.53 (0.11)
0.09(0.02)
91.53 (0.55)
92.40 (0.10)
92.23 (0.23)
93.34(0.02)
TSB
(0.03)
(0.00)
0.82 (0.01)
0.34(0.04)
92.70 (0.00)
92.77 (0.06)
92.70 (0.00)
93.65(0.04)
300
Val Ace
0.44 (0.04)
0.62 (0.08)
0.59 (0.71)
0.06(0.02)
91.20 (0.35)
92.10 (0.50)
91.43 (0:72)
93.31(0.22)
architecture's generalisation performance. All the NAS search strategies start their search from 10 random initial data and are repeated for 20 seeds. The mean and standard error results over the search time are shown in Fig. 4 By using our estimator, the NAS search strategies can find architectures with lower test error given the same time budget identify the top performing architectures using much less runtime as compared to using final or early-stopping validation accuracy. The gain of using our estimator is more significant for NAS methods performing both exploitation and exploration (RE and BO) than that doing pure exploration (Random Search in Appendix G).
4.4 Improving One-shot and Cradient-basee NAS
Different from query-based NAS strategies, which evaluate the architectures queried by training them independently from seratch, another popular class of NAS methods use weight sharing to accelerate the evaluation of the validation performance of architectures (subnetworks) and use this validation information to select architectures or update architecture parameters. Here we demonstrate that our TSE estimator can also be a plug-in replacement for validation accuracy or loss used in this family of NAS methods to improve their search performance.
One-shot NAS We first experiment on classic one-shot method, RandNAS [26), which trains a supernetwork by uniform sampling, then performs architecture search by randomly sampling subnetworks from the trained supernetwork and comparing them based on their validation accuracy. We follow the RandNAS procedure for the supernetwork training but modify the search phase: for each randomly sampled subnetwork, we train it for B additional mini-batches after inheriting weights from the trained supernetwork to compute our TSE estimator. Note that although this introduces some additional cost, our estimator eliminates the cost of evaluation on the validation set as doesn't 't require validation data. Specifically, for single DARTS architecture evaluated on CIFAR 10, the RandNAS protocol takes on average 6.6 seconds to compute the validation accuracy on entire validation set, and 7.5 seconds to train for B = 100 additional mini-batches to compute our TSE estimator. On NB201, the recommended protocol for CIFAR 10 takes on average 6.4 seconds per architecture to compute validation accuracy and only 4.4 seconds to train for B 100 additional mini-batches.
In our experiments, to ensure fair comparison, we recompute the validation accuracy of each subnet- work after the additional training. We also experiment with more advanced supernetwork training techniques such as FairNAS (9] and MultiPaths (5T) and show that our estimators can be applied on top of these techniques to further improve the rank correlation performance.
We evaluate the rank correlation performance and average test accuracy of the top- 10 architectures recommended by different performance estimators among 500 random subnetworks sampled from the DARTS supernef 5 and 200 random subnetworks from the NB201 supernet. We repeat the experiments
'e use Benchh-h33 to compute the true test accuracy of each subnetwork when trained independently from scratch.

---

94.25
Valid. Accursty
80-
Valld Accurocy
60-
94.00
Volld. Accurscy
24.0
DARTS DIMITS-1SE
20-
93.50
00.5
DYN65 DYMAS-13E
92.25
DARTS DAMIS-115
99.0
50
DYMAS-15E
20
40
40
40
20
Search Epocts T
Search Epochs T
Search Epochs T
Search Epochs
(a) NB201-CIFARI0
(b) DARTS-NB30L
Figure 5: Test accuracy of the subnetwork recommended by differentiable NAS methods over the search epochs. Original DARTS, DrNAS (in green) use the gradient of validation loss to update the architecture parameters but their variants (DARTS-TSE and DrNAS-TSE) (in red) uses that of our estimator computed over 100 mini-batches. TSE help mitigate the overfitting of DARTS on NB201.
on B 100, 200, 300 and over different supernetworks training seeds. The mean and standard deviation results are shown in Table 2 It is evident that our TSE leads to 170% to 300% increase rank correlation performance compared to validation accuracy and achieves higher average test accuracy of the top 10 architectures across all supernetwork training techniques and search spaces. This implics that our estimator can lead to architectures with better generalisation performance under the popular weight-sharing setting. We include the results for more estimators in Appendix G.
Differentiable NAS Finally, we briefly demonstrate the use of our estimators on differentiable
NAS. We modify two differentiable approaches. DARTS (28) and DrNAS [8] by directly replacing the derivative of the validation loss with that of our TSE estimator computed over 100 mini-batches (B=100 as in one-shot NAS setting above) to update the architecture parameters. We include in Appendix G additional details of our adaptation. We test both approaches and their TSE variants on the NB201-CIFAR 10 well as DARTS search space. Again we use BAS-Bench-301 true test performance of searched DARTS architectures on CIFARIO DARTS-NBB00 accuracy of the subnetwork recommended over each search epoch is shown in Figure 5 average over seeds for 18200-CIFARIIS 10 and use the default seed for DARTS-NB30L. The results show that simple integration of our estimator into the differentiable NAS framework can lead to clear search performance improvement and even mitigate the overfitting to skip-connections problem suffered by DARTS on the NB201 search space (a). The results for DARTS architectures found with TSE estimator but retrained under the full DARTS training protocol again show the benefit of using estimator.
obtain the The test
28 are shown in Appendix G, which
5 Conclusion
We propose a simple yet reliable method for estimating the generalisation performance of neural architectures based their training speed as measured by the sum of early training losses. Our estimator is theoretically motivated by the connection between training speed and generalisation. and outperforms other efficient estimators in terms of rank correlation with the true test performance under different search spaces as well as different training set-ups. Moreover, it can lead to significant speed-ups ups and performance gains when applied to different NAS strategies including one-shot and differentiable methods. We believe our estimator can be a very useful tool for achieving efficient neural architecture search. Our estimators, by reducing the computation and time required for performance evaluation during NAS, can significantly reduce the environmental costs incurred by NAS as AutoML becomes more widely used in industry. These efficiency gains can further enable potential users with limited computation budgets to use NAS methods.
Acknowledgments and Disclosure of Funding
Binxin Ru was supported by Clarendon Scholarship. Clare Lyle was supported by the Open Phi- lanthropy Foundation AI Fellows program. Lisa Schut was supported by EPSRC (grant number FP/S024050//) and DeepMind. Computational resources were supported by the Oxford-Man Institute of Quantitative Finance as well as JADE HPC at the University of Oxford.
10

---

References
[1] Mohamed Abdelfattah, Abhinav Mehrotra, łukasz Dudziak, and Nicholas Donald Lane. Zero- cost proxies for lightweight [nas]. In International Conference on Learning Representations, 2021.
[2] Sanjeev Arora, Simon S Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.0850 2019.
[3] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. urXiv preprint 17X.v 2017.
[4] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(Feb):281 2012.
[5] James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper- parameter optimization. In Advances in Neural Information Processing Systems (NIPS), pages 25544, 2011.
[6] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bus Buhé E. Fox, and Garnett, editors, Advances Neural Information Processing Systems 32, pages 10836-10846. Curran Associates, Inc., 2019.
[7] Tianqi Chen and Carlos Guestrin. Xgboost: the 22nd aem sigkdd international conference on knowledge discovery and data mining, pages 785-794, 2016.
A scalable tree boosting system. In Proceedings of
[8] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsich. Dr(nas): Dirichlet neural architecture search. In International Conference Learning Representations, 2021.
[9] Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li. Fairnas: Rethinking evaluation faimess of weight sharing neural architecture search. arXiv preprint arXiv:1907.01845 2019.
[10] Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hy- perparameter optimization of deep neural networks by extrapolation of learning curves. In Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015.
[11] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
[12] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 1703. 1008, 2017.
[13] Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv:1808.05377, 2018.
[14] Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter optimization at scale. In International Conference on Machine Learning (ICML), pages 1436- 1445, 2018.
[15] Stanislav Fort, Pawel Krzysztof Nowak, Stanislaw Jastrzebski, and Srini Narayanan. Stiffness: new perspective on generalization in neural networks. arXiv preprint arXiv:I901.0944 1901.0991, 2019.
[16) Pascal Germain, Francis Bach, Alexandre Lacoste, and Simon Lacoste-Julien. Pac-hayesian theory meets bayesian inference. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages 1884-1892, 2016.
[17] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225- 1234, 2016.
11

---

[18] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where find them. In International Conference on Learning Representations, 2020.
[19] Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poezos, and Eric P Xing. Neural architecture search with Bayesian optimisation and optimal transport. In Advances in Neural Information Processing Systems (NIPS), pages 2016-2025, 2018.
[20] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang. Wei Chen, Weidong Ma, Qiwei Ye, and Tie- Yan Liu. Lightgbm: A highly efficient gradient boosting decision tree. Advances in neural information processing systems, 30:3146-3111 2017.
[21] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint 1609.04836 2016.
[22] Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian optimization of machine learning hyperparameters on large datasets. 1605.0777 2016.
[23] Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction with bayesian neural networks. 2016.
[24] Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv preprint 2xXx:20003.02//8, 2020.
[25] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. 1oX1v.190..07638, 2019.
[26] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty Artificial Intelligence, pages 367-377. PMLR, 2020.
[27] Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar Hy- perband: A novel bandit-based approach to hyperparameter oatprraaaattttooiiiiiiiiio arXiv:1603.00 1603.06560, 2016.
[28] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search.
In International Conference Learning Representations (ICLR), 2019.
[29] Tongliang Liu, Gábor Lugosi, Gergely Neu, and Dacheng Tao. Algorithmic stability and hypothesis complexity. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1159-21699 JMLR. org, 2017.
[30] Clare Lyle, Lisa Schut, Binxin Ru, Mark van der Wilk, and Yarin Gal. A Bayesian perspective on training speed and model selection. Thirty-fourth Conference on Neural Information Processing Systems, 2020.
[31] David A McAllester.
Pac-bayesian model averaging. In Proceedings of the twelfth annual conference on Computational learning theory, pages 164-170, 1999.
[32] Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. arXiv preprint arXiv:2006. 04040.004477..... 2020.
[33] Jeffrey Negrea, Mahdi Haghifam, AI Element, Gintare K Dziugaite, Ashish Khisti, and Daniel M Roy. information-thhorrtiic International Conference on Information Processing Systems, 2019.
theoretic generalization bounds for sgld via data-dependent estimates. 33rd
[34] Gergely Neu. Informatiion-theoret generalization bounds for stochastic gradient descent, 2021.
[35] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring generalization deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
12

---

[36] Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning (ICML), pages 4092-4101, 2018.
[37] Ilija Radosavovic, Justin Johnson, Saining Xie, Wan-Yen Lo, and Piotr Dollár. On network design spaces for visual recognition. In ICCV, 2019.
[38] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pages 4780 2019.
[39] Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe Lc, and Alexey Kurakin. Large-scale evolution of image classifiers, In International Conference Machine Learning (ICML), pages 2902-2911 11, 2017.
[40] Binxin Ru, Pedro Esperança, and Fabio Maria Carlucci. Neural architecture generator optimiza- tion. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 12057-12069. Curran Associates, Inc., 2020.
[41] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Interpretable neural ar- chitecture search via bayesian optimisation with weisfeiler-lehman kernels. In International Conference on Learning Representations, 2020.
[42] 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.09977 2020.
[43] Samuel L. Smith, Benoit Dherin, David G. T. Barrett, and Soham De. On the origin of implicit regularization in stochastic gradient descent. In International Conference on Learning Representations, 2021.
[44] Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. Advances in Neural Information Processing Systems, 33, 2020.
[45] Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? arXiv preprint arXiv:2104.01177 2021.
[46] Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. arXiv:1904.01569 2019.
[47] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search. In International Conference on Learning Representations (ICLR), 2019.
[48] Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? Advances in Neural Information Processing Systems, 33, 2020.
[49] Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations (ICLR), 2020.
[50] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS-Bench-101 Towards reproducible neural architecture search. In International Conference on Machine Learning (ICML), pages 7105-7114 14, 2019.
[51] Jiahui Yu and Thomas S Huang. Universally slimmable networks and improved training techniques. In Proceedings of the IEEF/CVF International Conference Computer Vision, pages 1803-1811,
2019. 2019.
[52] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. International Conference on Learning Representations, 2020.
13

---

[53] Arber Zela, Aaron Klein, Stefan Falkner, and Frank Hutter. Towards automated deep learning: Efficient joint neural architecture and hyperparameter search. arXiv preprint arXiv: 06990, 2018.
[54] Arber Zela, Julien Siems, and Frank Hutter. Nas-bench- Benchmarking and dissecting one-shot neural architecture search. International Conference on Learning Representations, 2020.
[55] Barret Zoph and Quoc Le. Neural architecture search with reinforcement learnin. In Interna- tional Conference on Learning Representations (ICLR), 2017.
[56] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697-8710, 2018.
14


Reviews:
[{"review_id": "mqHIHGL-Fy", "reviewer": "Reviewer_Y2bt", "summary": "This work proposes that the summing of training losses may be a better indicator than validation accuracy especially at the early phase of architecture search. Author[s] provides experimental results on various model-free speedy estimators, zero-cost estimators, model-based extrapolators; and shows that TSE-E and TSE-EMA are the most effective two among them. ", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Merits:\n1. Good motivation. The paper starts with the generalization bound based on the properties of the training trajectory, hypothesizing that training speed may be a less noisy measure of generalization compared to the validation accuracy in the view of NAS, where the search budget is usually limited. \n\n2. Solid experiments. The paper conducted experiments on NAS201, RandWire, NDS, DARTS to evaluate the ranking correlation preserving the capability of these performance estimators, as well as on NAS201,  NAS301 (DARTS) to evaluate the NAS performance of both query-based (where they evaluate three subroutines RS, RE, BO) and weight-sharing (where they evaluate four subroutines RandNAS, FairNAS, MultiPahs, Bi-level). In all these experiments, they show that TSE-E and TSE-EMA can better preserve the ranking correlation than SoVL and VAccES; and much better than zero-cost estimators when training progresses (though it is a little bit unfair since zero-cost is designed for epoch 0, depending on how many budgets you have).  They also show its speed-up performance under query-based NAS as well as better search performance under weight-sharing NAS. \n\n3. Simple and effective. Figure 5 in Appendix C.4 looks surprisingly consistent across different datasets and search spaces in terms of rank correlation performance of TSE-E computed over E most recent epochs. If it holds true, in practice it means we can simply query the training loss API in existing NAS benchmarks at each epoch and directly use it as the feedback signal.  \n\n4. Code is provided. \n\n\nImprovement suggestions:\n1. In Line 98, you mentioned measuring training speed solely based on the epochs is likely to suffer overfitting on training data thus cause degraded model selection performance. However, in the experiments the minimum T you choose is 1, meaning that at least all mini-batches within a most recent epoch are used to compute the sum of training losses. I admit that currently NAS benchmarks only provide epoch-level statistics, which may restrict the experimental setup. Nevertheless, could you provide some discussion/results on TSE results based on mini-batch beyond discretized epochs? e.g. conduct some ablations on the actual search space instead of benchmarks so you can run TSE within an epoch. \n\n2. Figure 2 in Appendix C.2 validates the motivation by showing that validation loss may negatively correlate with validation accuracy as training progresses. I don't quite understand why the discrepancy between validation loss and training loss is very large on CIFAR-100 since it is assumed to be i.i.d.\n\n3. I would suggest author[s] take a look at another line of speed-up NAS in the related work. e.g. https://arxiv.org/pdf/2006.06936.pdf, https://arxiv.org/pdf/2102.07108.pdf, https://arxiv.org/pdf/2007.04965.pdf, https://arxiv.org/pdf/2105.06369.pdf. The idea is to design a better neighborhood-aware encoding/representation to build a flatter performance landscape and improve downstream subroutines in the scope of both query-based and weight-sharing based. In practice, architecture parameters could be further combined with partial learning curves to boost the KT and NAS performance, see this for a take https://cvpr21-nas.com/resources/upload/0894f613d1c1/file/1624351763247.pdf. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is solid work. Experiments have been conducted in a comprehensive way in my opinion. In addition to the improvement suggestions as pointed above, there is not too much I can think of now. If time is allowed, author[s] may provide experimental results compared to SOTA NAS results on DARTS search space with the same training protocol as used in DARTS original code. In Line 226, LcSVR (or in general, model-based predictor) can be optimized in an active learning way with the updated pool instead of using a large initial population for a one-time fit to save the computational resources, as used in many recent works such as MLPs in BANANAS, GCN with BLR in BONAS, and DNGO in arch2vec and CATE. This work does not contain any potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "more than 12 hours"}, "extra_text": {}}, {"review_id": "b0fw2s7hXaO", "reviewer": "Reviewer_2hFh", "summary": "This paper proposes a simple yet reliable estimator for fully trained network performance inspired by the PAC-Bayes bounds. Based on the observation in previous work that networks that train faster have better generalization performance, they propose that small areas under the training loss curve early in training correlate with better final performance. They propose several variations of this estimator with varying methods of weighting more recent epochs more than early epochs. They demonstrate the effectiveness of their estimators to provide good ranking correlation performance with the final accuracy with limited training on several search spaces/datasets such as NB-201-cifar10/cifar100/imagenet16 and Resnet/Resnext-cifar10. They also demonstrate that their estimator provides better rankings and find better performing networks compared to using the validation accuracy when applied to the problem of selecting a final architecture from a trained super-network for one-shot NAS. They also demonstrate that it can more efficiently find high performing networks compared to validation accuracy when applied to Regularized Evolution NAS and Bayesian Optimization NAS.", "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": "This paper tackles the problem of finding estimators that can better predict final network performances with few epochs of training. Their proposed estimator based on the area under the training curve is simple and very efficient to calculate and they demonstrate that it is robust with thorough experiments with multiple use cases, multiple search spaces, and multiple datasets. I strongly recommend this paper to be accepted. While the method is not incredibly novel and there is previous work on early stopping, their paper has significance due to the simplicity of the method and the range of experimental evidence they provide to demonstrate their algorithm\n\nStrengths:\nA large strength of this paper is in its simplicity. It target's an important area of model-free accuracy prediction from a single training run. Performance predictors are a very important field of work for NAS and this method has strong performance utilizing only the training loss compared to weight-sharing proxies and model-based performance estimators which requires you start with a relatively large number of trained models.\n\nThe submission is well supported by their diverse experimental results. They demonstrate their simple metric works well to rank architectures on CIFAR10, CIFAR100, Imagenet16, Flower102. They show that it can speed up Regularized Evolution, Bayesian Optimization, and one-shot NAS. They also show that it can rank architectures well in the NB201 search space, RandWiredNN search space, and ResNet/ResNeXT search space. The paper is easy to understand and follow. It tackles an important problem that can increase efficiency for a variety of NAS methods.\n\nOne of the most interesting general indications from the experimental results thoroughly show that early validation loss is a significantly worse measure of later performance compared to early training loss. Their measure seems to only be beat by validation accuracy quite late in training \n \nWeaknesses:\n\nThis paper would benefit from better positioning of the work in relation to related work on performance prediction. While work is well positioned with respect to LcSVR and early validation accuracy in experiments and related work, it would still benefit from additional comparisons to recent work such as tree-based and graph functions like LGBoost[1], XGBoost[2], GIN[3] which were examined as performance predictors in Nasbench-301[4]. LGBoost[1] and XGBoost[2] were also analyzed more thoroughly in [5].\n\nOne area it would actually be very beneficial to test would be comparing your TSE metrics with simply using the training loss as a strong baseline for your proposed variations.\n\nAn interesting additional area to explore may be how the training loss compares to the training accuracy as a metric.\n\nOne area which the paper could be extended to show further robustness of this finding would be testing out a task other than classification such as object detection or regression to see if maybe this is a property limited to simple classification cross entropy loss. If any results could be shown on full sized Imagenet, it would demonstrate that the methodology works also with larger datasets.\n\nIt would also be useful to show the robustness of this general method for performance estimation if you could analyze if this can be extended to other hyperparameter search problems as you mentioned.\n \n[1] G. Ke, Q. Meng, T. Finley, T. Wang, W. Chen, W. Ma, Q. Ye, and T. Liu. Lightgbm: A highly efficient gradient boosting decision tree. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 3146–3154. Curran Associates, Inc., 2017.\n[2] 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.09777, 2020.\n[3] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019a.\n[4] Siems, Julien, et al. \"NAS-Bench-301 and the case for surrogate benchmarks for neural architecture search.\" arXiv preprint arXiv:2008.09777 (2020).\n[5] White, Colin, et al. \"How Powerful are Performance Predictors in Neural Architecture Search?.\" arXiv preprint arXiv:2104.01177 (2021).\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I believe that limitations and societal impacts are sufficiently addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Vpw0Vrtd88p", "reviewer": "Reviewer_BhHR", "summary": "This paper proposes a simple yet effective model-free performance evaluation metric for architectures with partial training. To briefly summarize, the proposed method uses the (weighted) average of training loss over multiple mini-batches. Intuitively speaking, this metric measures the variance of gradients across mini-batches to some extent, which is related to the ease of convergence. Extensive empirical evaluations are conducted across different spaces and the results show that the proposed metric consistently outperforms existing ones; The theoretical aspect of this paper includes a connection of TSE to PAC bound. This work has its value as an add-on to many existing NAS algorithms. For these reasons, I vote for acceptance. I do have a few questions for the author, which I will explain in the detailed comment. And I might adjust my opinion of the paper depending on the responses.", "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 author demonstrates that the proposed method can be used as a simple add-on to improve many existing NAS methods.\n2. Solid experiments, the author studies on a wide range of spaces (e.g. NB201, NB301, DARTS, Randomly wired spaces, ResNeXT space, e.t.c.) and demonstrated consistent results.\n3. ranking among the top 1% architectures on some spaces is also reported, which is an important measure of the effectiveness of the proposed method, especially for NAS.\n4. sufficient discussion/experiments are provided for the hyperparameter of the proposed metric (i.e. window size and decay ratio). A procedure to decide the training budget is also provided.\n\nWeakness:\n1. It seems that the author tests the ranking correlation on larger scale search spaces like DARTS Space, but does not report and compare the final results. Perhaps turning the proposed metric into a full search algorithm (by combining it with random sampling or some other existing method) and evaluating on DARTS Space might make the paper stronger. Like those experiments in Figure 5. But this is not a major point.\n2. Please refer to the questions in the Detailed Comment Section.\n\nDetailed Comments:\n1. The paper mentioned that the training speed is related to generalization. However, in NAS, people generally believe that architectures that are easier to train (e.g. with more parameter-free operations) might stand out in the beginning but plateau quickly and therefore falls behind eventually [2]. These two conclusions seem a bit contradictory at first sight. I would like to hear the author's comment on this matter.\n\n2. It is interesting to see that using training loss works better than the valid loss in TSE. I wonder if the same result can be observed in early stopping: Could you also show the curves of early stopping + training loss and early stopping + valid loss in Figure 1 (a-c would be sufficient)?\n\n3. For DrNAS in Figure 5a: this curve seems different from their original paper [1] (Figure 1). From your curve, it seems that the performance of DrNAS drops to ~50% on 201 (which is basically an architecture full of skip/none) in the middle run. But in Figure 1 of the original paper, the solid line - the test accuracy of the best architecture derived by argmax of the concentration parameter - seems pretty stable. Do you have any idea about the difference?\n\nMinors:\n1. You might want to move Figure 1 up to page 3/4, as it is cued twice there.\n\n[1] Chen et al. DrNAS: Dirichlet Neural Architecture Search (ICLR2021)\\\n[2] Zhou et al. Theory-Inspired Path-Regularized Differential Network Architecture Search (NIPS2020)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, it is addressed in the appendix.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "So_r6Repy8L", "reviewer": "Reviewer_Ctey", "summary": "Performance estimation is an important point to speed up the search process in NAS.\nThis paper proposes a simple method for estimating the generalisation performance of neural architectures via training speed measured by the training loss, which is theoretically motivated by the relation between training speed and generalisation of neural networks.\nExperiments demonstrate the effectiveness of the proposed TSE (training speed estimators) compared to other commonly used estimators. Further, it can be incorporated into existing NAS algorithms and make improvements.", "questions": "", "limitations": "", "rating": 6, "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 proposed TSE is a simple yet effective estimator for performance prediction.\nThe metric is easy to compute during the training and correlates with the generalisation of neural architectures.\nBelow are some problems/questions:\n1. In line 201, E=1 performs well and implies that more recent training steps is better for TSE. Then what if you limit the minibatches used to calculate the TSE, rather than the B batches in an epoch?\n2. In line 268, you choose different N_s values to identify the best T_o. Does this mean that for other practitioners applying your TSE on their task, they can use N_s = 10 to identify the overfit point T_o?\n3. In Figure 4, why T=200 is worse than T=10 across all the experiments? This is not reasonable.\n4. In line 299, what is the additional cost of training B additional mini-batches?\n5. In Figure 1, why does SoVL not appear in d-h, LcSVR not in h, SNIP not in d-h, and JacCov not in d-h ?\n\nTypos and grammar mistakes:\n1. Line 28, trainin -> training\n2. In Table 1, N_{total} appears in the caption but not in the table, and N_{T} appears in the table rather in the caption.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a strong paper in a somewhat crowded research area, performance prediction for NAS. Even within such a crowded area, this paper stands out for the thoughtfulness of its experiments and the grounding of the approach proposed. The reviewers asked for more depth in the related work section and for some additional experiments, but overall have no remaining concerns regarding the paper. 
Decision: Accept (Spotlight)