Revisiting the Train Loss: an Efficient Performance Estimator for Neural Architecture Search
Authors: Binxin Ru
Clare Lyle
Lisa Schut
Mark van der Wilk
Yarin Gal
Venue:  (2021)
Keywords: performance estimation
neural architecture search

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 stopping estimates may correlate poorly with fully trained performance, and model-based estimators require large training sets. Instead, motivated by recent results linking training speed and generalisation with stochastic gradient descent, we propose to estimate the final test performance based on the sum of training losses. Our estimator is inspired by the marginal likelihood, which is used for Bayesian model selection. Our model-free estimator is simple, efficient, and cheap to implement, and does not require hyperparameter-tuning or surrogate training before deployment. We demonstrate empirically that our estimator consistently outperforms other baselines under various settings and can achieve a rank correlation of 0.95 with final test accuracy on the NAS-Bench201 dataset within 50 epochs.

Under review as a conference paper at ICLR 2021
REVISITING THE TRAIN Loss: AN EFFICIENT PER- FORMANCE ESTIMATOR FOR NEURAL ARCHITECTURE SEARCH
Anonymous authors Paper under double-blind review
ABSTRACT
Reliable yet efficient evaluation of generalisation performance of a proposed ar- chitecture is crucial to the success of neural architecture search (NAS). Tradi- tional approaches face variety of limitations: training each architecture to com- pletion is prohibitively expensive, early stopping estimates may correlate poorly with fully trained performance, and model-based estimators require large train- ing sets. Instead, motivated by recent results linking training speed and gener- alisation with stochastic gradient descent, performance based on the sum of training losses. Our estimator is inspired by the marginal likelihood, which used for Bayesian model selection. Our model- free estimator is simple, efficient, and cheap to implement, and does not require hyperparameter-tum tuniin or surrogate training before deployment. We demonstrate empirically that our estimator consistently outperforms other baselines under var- ious settings and can achieve rank correlation of 0.95 with final test accuracy on the NAS-Bench201 dataset within 50 epochs.
propose to estimate the final test
INTRODUCTION
Reliably estimating the generalisation performance of proposed architecture is crucial to the suc- cess of Neural Architecture Search (NAS) but has always been a major bottleneck in NAS algorithms (Elsken al. 2018). The traditional approach of training each architecture for a large number of epochs and evaluating it on validation data (fill evaluation) provides a reliable performance mea- sure, but requires prohibitively high computational resources on the order of thousands of GPU days (Zoph & Le 2017 Real et al. 2017] Zoph et al. 2018 Real et al.) 2019 Elsken et al. 2018). 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 a low-fidelity approximation of generalisation performance by training for fewer epochs (Li et al., 2016 Falkner al.) 2018 Li & Talwalkar 2019). However, if we stop the training early at small number of epochs and evaluate the model on validation data, the relative performance ranking may not correlate well with the performance ranking of the full evaluation (Zela et al. 2018). Another line of work focuses on learning curve extrapolation (Domhan et al.) 2015 Klein et af. 2016b) Baker et al. (207)). which trains surrogate model predict the final generalisation performance based on the initial learning curve and/or meta-features of the architecture. However, the train- ing of the surrogate often requires hundreds of fully evaluated architectures achieve satisfactory extrapolation performance and the hyper-parae parameters of the surrogate also need to be optimised. Al- ternatively, the idea of weight sharing adopted in one-shot NAS methods speed up evaluation (Pham et al.) 2018 Liu et al.) 2019 Xie et al.) 2019b). Despite leading to significant cost-saving, weight sharing heavily underestimates the true performance of good architectures and unreliable in predicting the relative ranking among architectures (Yang et al. 2020 Yu et al.) 2020).
In view of the above limitations, we propose simple model-free method which provides a reliable yet computationally cheap estimation of the generalisation performance ranking of architectures: the Sum over Training Losses (SoTL). Our method harnesses the training losses of the commonly SGD optimiser during training, and is motivated by recent empirical and theoretical results linking training speed and generalisation (Hardt et al., 2016 Lyle et al.) 2020). We ground our method in the Bayesian update setting, where show that the SoTl. estimator computes lower bound the

---

Under review as a conference paper at ICLR 2021
model evidence, a quantity with sound theoretical justification for model selection (MacKay 1992). We show empirically that our estimator can outperform a number of strong existing approaches to predict the relative performance ranking among architectures, while speeding up different NAS approaches significantly.
METHOD
We propose a simple metric that estimates the generalisation performance of deep neural network model via the Sum of its Training Losses (SoTL). After training a deep neural network whose prediction is fo(-) for T epochs" we sum the training losses collected so far:
T
SoTL = Σ
1
(X...
(1)
where is the training loss a mini-batch yz) at epoch t and is the number of training steps within epoch. If distribution P(0) and start the sum from epoch 1 = T ++1 instead of f 1, we obtain a variant we start the sum at T and our estimator corresponds the
the first few epochs the burn-in phase for o,,; converge certain
SoTL-E. In the case where sum over training losses within epoch t = T. We discuss SoTL's theoretical interpretation based on Bayesian marginal likelihood and training speed Section B and empirically show that SoTL, despite its simple form, can reliably estimate the generalisation performance of neural architectures in Section 5
If the sum over training losses is useful indicator for the generalisation performance, one might expect the sum over validation losses to be a similarly effective performance estimator. The sum over validation losses (SoVL) lacks the link to the Bayesian model evidence, and so its theoretical motivation is different from our SoTL. Instead, the validation loss sum can be viewed as performing bias-variance trade-off;; the parameters at epoch & can be viewed as potentially high-variance sample from a noisy SGD trajectory. and so summation reduces the resulting variance in the valida- tion loss estimate at the expense of incorporating some bias due to the relative ranking of models' test performance changing during training. We show in Section that SoTL clearly outperforms So in estimating the true test performance.
THEORETICAL MOTIVATION
The SoTL metric is a direct measure of training speed and draws inspiration from two lines of work: the first Bayesian perspective that connects training speed with the marginal likelihood in the model selection setting, and the second is the link between training speed and generalisation (Hardi 2016). In this section, we will summarize recent results that demonstrate the connection between SoTL and generalisation, and further show that in Bayesian updating regimes, the SoTL metric corresponds to an estimate of a lower bound on the model's marginal likelihood, under certain assumptions.
3.1 TRAINING SPEED AND THE MARGINAL LIKELIHOOD
We motivate the SoTL estimator by a connection to the model evidence, also called the marginal likelihood, which is the basis for Bayesian model selection. The model evidence quantifies how likely a dataset D is to have been generated by a model, and so can be used to update a prior belief distribution over which model from given set most likely to have generated D. Given model with parameters 0, prior (0), and likelihood P(D(0) for a training data set DD = (Di....,y,, with data points D.- (z,, v:). the (log) marginal likelihood expressed as follows.
log P(D) = log Ba(o) [P(D]()] + log P(D) = Σ log P(D.(De)) = Σ log [EPOeES [P(D,
Interpreting the negative log posterior predictive probability log P(D, of each data point as 'loss' function, the log evidence then corresponds to the area under training loss curve, where each
'T' he far from the total training epochs Tend used in complete training
2

---

Under review as a conference paper at ICLR 2021
training step would be computed by sampling data point Dj, taking the log expected likelihood under the current posterior (() as the current loss, and then updating the posterior by incorpo- rating the new sampled data point: Dei+1 = ee U [D:). One can therefore interpret the marginal likelihood as a measure of training speed in a Bayesian updating procedure. In the setting where we cannot compute the posterior analytically and only samples 0 from the posterior over parameters are available, we obtain an unbiased estimator of lower bound L(D) Σ Ep(()P..)) [log P(D) on the marginal likelihood by Jensen's 's inequality, which again corresponds to minimizing a sum over training losses
Σ log P(D,10) = Σ EP(O [log P(D.10) - Σ log [B(()).))P((.1)) = log P(D)
with denoting equality in expectation. A full analysis of the Bayesian setting is outside of the scope of this work. We refer the reader to (Lyle et al. (020)) for more details of the properties of this estimator in Bayesian models. Although the NAS setting does not yield the same interpretation of SoTL as model evidence estimation, we argue that the SoTL metric is still plausibly useful for model selection. Just as the marginal likelihood measures the utility of updates based on early data points in predicting later data points, the SoTL of a model trained with SGD will be lower for models whose mini-batch gradient descent updates improve the loss of later mini-batchin We refer the reader to Apppendix tB see demonstration of the SoTL metric in the Bayesian linear regression setting. We emphasize that the Bayesian connection thus justifies the sum over training losses as a tool for model selection, but not the training loss from single parameter update.
seen during optimisation.
3.2 TRAINING SPEED AND GENERALISATION
Independent of the accuracy of SoTL in estimating the Bayesian model evidence, it is also possible to motivate our method by its relationship with training speed: models which achieve low train- ing loss quickly will have low SoTL. There are both empirical and theoretical lines of work that illustrate deep connection between training speed and generalisation. On the theoretical front, we find that models which train quickly can attain lower generalisation bounds. Training speed and generalisation can be related via stability-based generalisation bounds (Hardt al., 2016] al.) 2017), which characterize the dependence of the solution found by learning algorithm on its train- ing data. In networks of sufficient width, (Arora et al. 2019) propose a taarrralttnnntt-kee -ernel-baaedd data complexity measure which bounds both the convergence rate of SGD and the generalisation er- ror of the model obtained by optimisation. A similar generalisation bound and complexity measure is obtained by (Cao & Gu 2019).
While theoretical work has largely focused on ranking bounds on the test error, current results do not provide guarantees on consistency between the ranking of different models' test set performance and their generalisation bounds. The empirical work of (Jiang* et al. 2020) demonstrates that many complexity measures are uncorrelated or negatively correlated with the relative performance of models on their test data but notably, a particular measure of training speed - the number of steps required to reach cross-entropy loss of 1, was highly correlated with the test set performance rank- ing of different models. The connection between training speed and generalisation is also observed by (Zhang et al., 2016), who find that models trained on true labels converge faster than models trained on random labels, and attain better generalisation performance.
4 RELATED WORK
Various approaches have been developed to speed up architecture performance estimation, thus im- proving the efficiency of NAS. Low-fidelity estimation methods accelerate NAS by using the vali- dation accuracy obtained after training architectures for fewer epochs (namely carly-stopping) (Li et al. 2016, Falkner et al., 2018 Zoph et al. 2018 Zela et al. 2018), training a down-scaled model with fewer cells during the search phase (Zoph et al. 2018 Real et al. (2019) or training on a subset of the data (Klein et al. 2016a). However, low-fidelity estimates underestimate the true perfor- mance of the architecture and can change the relative ranking among architectures (Elsken et al.) 2018). This undesirable effect on relative ranking is more prominent when the cheap approximation set-up is too dissimilar to the full evaluation (Zela al. 2018). As shown in our Fig. 2 below, the validation accuracy at early epochs of training suffers low rank correlation with the final test performance.
3

---

Under review as a conference paper at ICLR 2021
Another way to cheaply estimate architecture performance is train a regression model to trapolate the learning curve from what is observed in the initial phase of training. Regression model choices that have been explored include Gaussian processes with tailored kernel function (Domhan (et al. 2015). an ensemble of parametric functions (Domhan et al. 2013), a Bayesian neural network (Klein et al. 2016b) and more recently v-support vector machine regressor (u-SVR) (Baker al.) 2017) which achieves state-of-the-art prediction performance. Although these model- based methods can often predict the performance ranking better than their model-free early-stopping counterparts, they require a relatively large amount of fully evaluated architecture data (e.g. 100 fully evalu- ated architectures in (Baker et al. 2017)) 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 un- less 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.
Finally, one-shot NAS methods employ weight sharing to reduce computational costs (Pham et al, 2018 Liu al. 2019; Xie et al., 2019b). Under the one-shot setting, all architectures considered as subgraphs of a supergraph. Only the weights of the supergraph are trained while the architectures (subgraphs) inherit the corresponding weights from the supergraph. Weight sharing removes the need for retraining each architecture during the search and thus achieves a significant speed-up. However, the weight sharing ranking among architectures often correlates very poorly with the true performance ranking ( (Yang et al., 2020; Yu et al., 2020 Zela et al., (020)), meaning architectures chosen by one-shot NAS are likely to be sub-optimal when evaluated independently (Zela et al.) 2020). Moreover, one-shot methods are often outperformed by sample- sample-based NAS methods (Dong
& Yang 2020 Zela et al., 2020).
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. (Jiang* et al. 2020) provides rigorous empirical analysis of over 40 such measures. TThis investigation
measures (McAllester) 1999] Keskar et al. 2016 Neyshabur et al. 2017 Dziugaite & Roy| 2017) (including PAC-Bayesian bounds) provide good correlation with test set performance, but their estimation requires adding randomly generated perturbations to the network parameters and the magnitude of the perturbations needs to be carefully optimised with additional training, making them unsuitable performance estimators for NAS. Optimisation- based complexity measures also perform well in predicting generalisation. Specifically, the number of steps required to reach loss of 0.1, as mentioned in Section 3.2 is closely related to our approach as both quantities measure the training speed of architectures. To our knowledge though, this measure has never been used in the NAS context before.
finds that sharpncss-basee
5 EXPERIMENTS
In this section we compare the following measures. Note T denotes the intermediate training epoch, which is smaller than the final epoch number Tend > T: Our proposed estimator Sum of training losses over all preceding epochs (SoTL), which sums the training losses of architecture from epoch t = 0 to the current epoch t = T, and its variant Sum of training losses over the most recent E epochs (SoTLL-E) which uses the sum of the training losses from epoch t T - E to t T. Sum of validation losses over all preceding epochs (SoVL) computes the sum of the validation losses of an neural architecture from epoch at an early epoch (VAccES) corresponds to early-stopping practice whereby the user assumes the validation accuracy of an architecture at early epoch
0 to the current epoch / T. Validation accuracy
T < Tend is good estimator its final test performance at epoch t = Tend- Learning curve extrapolation (LcSVR) method is the state-of- are extrapolation method proposed in (Baker et al. 2017) which uses a trained v-SVR to predict the final validation accuracy of an architecture. The inputs for the SVR regression model comprise architecture meta-features (c.g. number of parameters and depth of the architecture), training hyper- parameters (e.g. initial learning rate, mini-batch size and weight decay), learning curve features up to epoch = T (c.g. the validation accuracies up to epoch t = T, the Ist-order and and-order differences of validation curve up to epoch t T). In experiments, 200 randomly sampled architectures and following the practice in (Baker et al., 2017), we optimise the SVR hyperparameters via random search using 3-fold cross cross-validation. We also compare against
train the SVR on data of
4

---

Under review as a conference paper at ICLR 2021
1.0
1.0
1.0
Correltiion
0.9
Pank Correlation
0.9
0.9
0.8
0.8
Sarl-E
50TL
TeciLIT=2001
SoVi
SOVL-E
10a
10a
104
10a
10:
Training Epoch
Training Epoch
Training Epoch
CIFARTO
(b) CIFARI0O
(c) IMAGENET-16-120
Figure 1: Rank correlation (with final test accuracy) performance of the sum of training losses, SoTL (blue) and SoTL-E (red), and those of validation losses (purple), SoVL (solid) and SoVL-E (dash dot), well as that of final test loss (black) for 5000 random architectures in NASBench-200 on three image datasets. Note the correlation performances of final test loss and SoVL-E near the end of training get surprisingly poor for CIFARI0/100 We explain this in Section 5.1
with two baselines on the DARTS search space: the training losses at each mini batch (TLmini) and the variant of VAccES, VAcCES(EMA) whereby the exponential moving average of the weights Tan & Le 2019) is used during validation to improve validation accuracy.
The datasets we used to compare these performance estimators are:
NASBench-201 (Dong & Yang 2020h: the dataset contains information of 15,625 different neu- ral architectures, each of which is trained with SGD optimiser for 200 epochs (Tend = 200) and evaluated on 3 different datasets: CIFARIO, CIFAR 100, IMAGENET-16- 120. The NASBench- 201 datasets can used to benchmark almost all up-to-date NAS search strategies.
RandWiredNN:
we produced this dataset by generating 552 randomly wired neural architec- tures from the random graph generators proposed in (Xie et al., 2019a) and evaluating the archi- tecture performance on the FLOWFRS1022 dataset (Nilshack Zisserman, 2008). We explored 69 sets of hyperparameter values for the random graph generators and for each set of hyper- parameter values, we sampled randomly wired neural networks from the generator. All the architectures trained with SGD optimiser for 250 epochs (Tend 250). This dataset allows us to evaluate the performance of our simple estimator on model selection for the random graph generator in Section 5.3
DARTS: we produce this dataset by randomly sampling 100 architectures from the search space used in DARTS (Liu et 2019) and evaluating them on CIFARIO. This search space is more
general than that of NAS Bench-201 and widely adopted in NAS (Zoph et al.) 2018 Liu et al., 2019
Chen et al. 2019
Xie et al. [019b] Xu et al.] 2019 Real et al. 2019 Li Talwalkar Shaw et al. 2019 Zhou al. 2020). We experiment with different
2020 Pham et al. 2018
evaluation set-ups in Section 5.2 and use this dataset to assess the stabilitylrobusteess of our estimator well as make comparison to TLmini and VAcc(EMA).
More details on the three datasets are provided in Appendix A In NAS, the relative performance ranking among different models matters more than the exact test performance of models. Thus, we evaluate different performance estimators by comparing their rank correlation with the model's true/final test accuracy. We adopt Spearman's rank correlation following (Ying et al. 2019 Dong VSSSTTLLE//VLLLLLLm.
& Yang, 2020). We flip the sign of compare to the Spearman's rank correlation of the other methods (which we want to maximise). We test different summation window sizes in Appendix C and find E = consistently give the best results. Thus, we set = as the default choice for our SoTL-E estimator in the following experiments. Note SoTL-E with E 1 corresponds to the sum of training losses over all the batches in one single epoch. All experiments were conducted on a 36-core 2.3GHz Intel Xeon processor with 512 GB RAM.
(which we want to minimise) to
5

---

Under review as a conference paper at ICLR 2021
1.00
0.95
0.95
Correlaion
0.90
Correlation
0.90
Corelation
0.30
Rank Corrlation
0.90
0.85
0.05
0.85
2.85
0.80
6.80
0.20
2.80
0.75
0.75
0.75
0.75
SoiL-E
0.70
0.70
0.70
0.70
0.65
VAcCES
0.65
0.65
0.65-
L:SVR
0.60
0.60
0.60
0.60
102
Training Lpoch
Training Eooch
Training Epoch
Training Epoch
(a) CIFARIO
(b) CIFARIO0
(c) IMAGENET-I66 1--GENETT-1--220
(d) FLOWERS102
Figure 2: Rank correlation performance of various baselines: SoTL-E, SoTL, SoVL, Val Acc and LR for 5000 random architectures in NASBench-201 on three image datasets (a) (c) and for 552 randomly wired architectures on FLOWERS102 (d). In all cases, our SoTT--- achieves superior rank correlation with the true test performance in much fewer epochs than other baselines. We shade the region T' > 100; this shaded region is less interesting in NAS where we want to use as fewer training epochs as possible to maximise the speed-up gain compared to full evaluation 7 T Tend-
5.1 TRAINING LOSS VS VALIDATION LOSS
We perform a simple sanity check against the validation loss on NASBench-200 datasets. Specif- ically, we compare our proposed estimators, SoTL and SoTL-E, against two equivalent variants of validation loss-based estimators: SoVL and Sum of validation losses over the most recent epoch (SoVL-E with E = 1). For each image dataset, we randomly sample 5000 different neural network architectures from the search space and compute the rank correlation between the true test accuracies (at T = 200) of these architectures and their corresponding SoTL/SoTL-E as well as SoVL/SoVL-E up to epoch T. The results in Fig. shoow that our proposed estimators SoTL and SoTL-E clearly outperform their validation counterparts.
Another intriguing observation is that the rank correlation performance of SoVL-E drops signifi- cantly in the later phase of the training (after around 100 epochs for CIFAR10 and 150 epochs for CIFAR 100) and the final test loss, TestL (T=200), also correlates poorly with final test accuracy. This implies that the validation/test losses can become unreliable indicator for the validation/test accuracy on certain datasets; as training proceeds, the validation accuracy keeps improving but the validation losses could stagnate a relatively high level or even start to rise (Mukhoti et al. 2020 Soudry et al. 2018). This is because while the neural network can make more correct classifica- tions on validation points (which depend on the argmax of the logits) over the training epochs, also gets more and more confident on the correctly classified training data and thus the weight norm and maximum of the logits keeps increasing. This can make the network overconfident on the mis- classified validation data and cause the corresponding validation loss to rise, thus offsetting or even outweighing the gain due to improved prediction performance (Soudry et al.) 2018). Training loss won't suffer from this problem (Appendix D). While SoTL-E struggles to distinguish architectures once their training losses have converged to approximately zero, this contributes to a much smaller drop in estimation performance of SoTTL- compared that of SoVL.-E and only happens near the very late phase of training (after 150 epochs) which will hardly be reached if we want efficient NAS using as few training epochs as possible. Therefore, the possibility network overconfidence under misclassification is another reason for our use of training losses instead of the validation losses.
5.2 COMPARISON AGAINST OTHER BASELINES
We now compare our estimators SoTL and SoTL-E against other baselines mentioned at the start of Section The results on both NASBench-201 and RandWiredNN datasets are shown in Fig. 2 Our proposed estimator SoTL-E, despite its simple form and cheap computation, outperforms all other methods under evaluation for T < 100 for all architecture/image datasets. Although the validation accuracy( accuracy(VAccES) VAccES) at T 2 150 can reach similar rank correlation, this is less interesting for appli- cations like NAS where we want to speed up the evaluation as much as possible and thus use as fewer training epochs as possible. The learning curve extrapolation method, LcSVR, is competitive.

---

Under review as a conference paper at ICLR 2021
1.0
0.9
Correlation
0.7
Rank Correlation
0.8
Rank Corelation
0.8
0.7
0.6
0.7
0.5
SLTL
0.5
0.6
0.4
Timini
0.4
SoVL
0.5
VACCES
0.3
0.2
0.4
10'
10'
10'
10'
10
10a
Training Epcch
Training Epoch T
Training Epoch T
(a) 1r=0.05, bs=128, 8 cells. cosine scheduler
(b) 1r=0.025, bs=96, 20 cells,
(c) 1r=0.1 bs= 20 cells, step-decay scheduler
cosine scheduler
Figure 3:
Rank correlation performance of various baselines: SoTL-E, SoTL, SoVL, VAccES, VAc- CES(EMA) and TLmini for 100 random architectures from DARTS search space on CIFARIO. We test the three training set-ups used in (Liu et al.] 2019): (a) the search phase (over 200 architec- tures), (b) the retraining phase for CIFARTO and (c) the retraining phase for ImageNet. Our SoTL-E achieves superior rank correlation in much fewer epochs than other baselines. Note also that the sum of training loss (SoTL/SoTTL-E) gives better test performance estimation than individual training loss (TLmini).
However, the method requires hundreds of fully trained architecture date to train the regression surrogate. Lots of computational resources are needed obtain such training data.
We further verify the robustness of our estimator across different training set-ups adopted in (Liu
al. 2019) on the DARTS dataset. Specifically, we evaluated on architectures of different sizes (8 cells and 20 cells) as well as different training set-ups (initial learning rate, learning rate scheduler and batch size). The results in Fig. show that our estimator again outperforms the competing methods. Note here the curve of TLmini corresponds to the average rank correlation with final test accuracy achieved by the mini-batch training loss over the epoch. The clear performance gain of our SoTL estimator over TLmini supports our claim that it is the sum of training losses, which carries the theoretical interpretation explained in Section instead of the training loss at a single minibatch, that serves good estimator of generalisation performance. Further, the results of VAcc(EMA) show that the EMA technique, which smooths and improves the accuracies during validation, does not necessarily improve the rank correlation of validation accuracy with the final test performance.
5.3 ARCHITECTURE GENERATOR SELECTION
For the RandWiredNN dataset, we use 69 different hyperparameter values for the random graph gen- erator which generates the randomly wired neural architecture. Here we would like to investigate whether our estimator can be used in place of the true test accuracy to select among different hyper- parameter values. For each graph generator hyperparameter value, we sample 8 neural architectures with different wiring. The mean and standard error of both the true test accuracies and SoTL-E scores over the 8 samples are presented in Fig. 4 Our estimator can well predict the relative per- formance ranking among different hyperparameters (Rank correlation 0.85) based on as few as 10 epochs of training. The rank correlation between our estimator and the final test accuracy improves as we use the training loss in later epochs.
5.4 SPEED UP NAS
Similar to early stopping, our method is model-free and can significantly speed up the architecture performance evaluation by using information from early training epochs. In this section, we incor- porate our estimator, SoTL-E, at T' = 50 into several NAS search strategies: Regularised Evolution RRall et al. 2019) (top row in Fig. 5). TPE (Bergstra et al. 201T) (bottom row in Fig. 5 and
Random Search (Bergstra & Bengio 2012) (Appendix [ and performance architecture search on NASBench-201 datasets. We compare this against the other two benchmarks which use the final validation accuracy at T = 200, denoted as Val Acc (T=200) and the early-stop validation accuracy at T = 50, denoted as Val Ace (T=50), respectively to evaluate the architecture's generalisation
We follow (aker et al. 2017) and train the SVR 200 architectures.

---

Under review as a conference paper at ICLR 2021
-15
Asc (T=250)
Rtak
-2.0
SOTL-E (ETLE(T=aa (T=90)
85
Rank Com--
SOTLE (T=70)
Rank 0orr=0,903
SoTL
75
SOTLE (T=50)
Rank - 0,950
-3.5
SOTLE (T=30)
65
SoTL-E (Tm
-..0
10
20
30
40
50
60
70
Hyperparameter
(a) Sum of training losses: SoTL-E
Test (T=250)
Rank Cor==100
90
VAcEE5 (T=
85
(est Sccuro
Rank 003--0.952
Vicct5 (1
Rank Comm
VAcceS
40
-75
VAccE5 (T=50)
Rank Corr=
VAccES (T=30)
20
000dato4 00000t00000
VAccE5 (T=
Rank Cor- 6.626
30 40
50
Hyperparameter ID
(b) strly-stopped validation accuracy: VAccES
Figure 4: Model selection among 69 random graph generator hyperparamters RandWiredNN dataset using (a) our SOTL-E and (b) VAceES. We use each hyperparameter value to generate architectures and evaluate their true test accuracies after complete training. The mean and standard error of the test performance across architectures for each hyperparameter value are presented as Test Acc (yellow) and treated as ground truth (Right y-axis). We then compute our SoTL-E=1 esti- mator for all the architectures by using their first T < 250 epochs training losses. The mean and standard error of SoTL-E scores for T 10, .... 90 presented in different colours (Left y-axis of (a)). The rank correlation between the mean Test Acc and that of SoTL-E for various 7 is shown in the corresponding legends in (a). The same experiment is conducted by using early-stopped validation accuracy (VAccES) for performance estimation (b). With only 10 epochs of training, our SoTL-E estimator can already capture the trend of the true test performance of different hyperparam- eters relatively well (Rank correlation= 0.851) and can successfully identify 24-th hyperparamter setting as the optimal choice. The prediction of best hyperparameter by VAccES less consistent and the rank correlation scores of VAccES at all epochs are lower than those of SoTL-E
performance. All the NAS search strategies start their search from 10 random initial data and repeated for 20 seeds. The mean and standard error results over the search time are shown in Fig. 5 By using our estimator, the NAS search strategies given the same time budget or identify the top performing architectures using much less runtime as compared using final or early-stopping validation accuracy. Also the gain of using our estimator is more significant for NAS methods performing both exploitation and exploration (RE and TPE) than that doing pure exploration (Random Search in Appendix E).
find architectures with lower test error
CONCLUSION
We propose a simple yet reliable method for estimating the generalisation performance of neural architectures based its early training losses. Our estimator enables significant speed-up for per- formance estimation in NAS while outperforming other efficient estimators in terms of rank corre- lation with the test performance. More importantly, our estimator has theoretical interpretation based on training speed and Bayesian marginal likelihood, both of which have strong links with generalisation. We believe our estimator can be a very useful tool for achieving efficient NAS.
REFERENCES
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint
8

---

Under review as a conference paper at ICLR 2021
0.105
Val Acc (T=50)
Val Acc (T-200)
Val Acc (T=50)
Val (T-200)
0.57
Val Acc (T=50)
Val Acc (T=200)
Best test testeeror error
0.100
SeTL-E (T=50)
Best test error
SoTL-E (T=50)
0.56
SoTL-E (T-50)
0.55
0.095
0.54
0.090
0.27
0.085
0.26
0.52
100
150
200
200
400
600
Run time (hours)
Run time (hours)
time (hours)
(a) RE-CIFARIO
(b) RE- COF
(c) RE I-AAIMMA-EETLIL 120
0.105
Acc (T-200)
0.30
Val Acc (T=200)
(T-200)
Val Acc (T=50)
SoTL-E (T=50)
Best test test error
0.29
Val Acc (T=
SoTL-E (T=50)
Best test error
0.56
Val Acc (T=50)
SoTL-E (T-50)
0.55
0.095
0.54
0.27
0.085
20
50
100
150
200
400
600
Run time (hours)
Run time (hours)
Run time (hours)
(d) TPE-CIFARI0
(c) 10
(I) IPE-IMAGENET-I6-IE
Figure 5: NAS performance of Regularised Evolution (RE) (Top row) and TPE (Bottom row) in combined with final validation accuracy (Val Acc (T=200)), early-stopping validation accuracy (Val Acc (T=50) and our estimator SoTL-E on NASBench-2N1 SoTL--E leads to the fastest convergence the top performing architectures in all cases.
arXiv:1901.08584 2019.
Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. arXiv preprint arXiv:170S. 2017.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(Feb):281-30) 2012.
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), pp. 2546-2554, 2011.
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é-Bue, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 10836-10846. Curran Associates, Inc., 2019.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search. In International Conference on Computer Vision (ICCV), 2019.
Tobias Domhan, Jost Tobias Springenberg, and Frank Hutter. Speeding up automatic hyperparam- eter optimization of deep neural networks by extrapolation of learning curves. Ewenty-Fourth International Joint Conference Artificial Intelligence, 2015.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope reproducible neural architec-
ture search. In International Conference on Learning Representations, 2020. URL https: //openreview,
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: /703. 1008, 2017.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv: arXiv:1808.00 05377, 2018.

---

Under review as a conference paper at ICLR 2021
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter op- timization at scale. In International Conference on Machine Learning (ICML), pp. 1436-1445, 2018.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-12344 2016.
Yiding Jiang*, Behnam Neyshabur*, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference Learning Representationss 2020. URL
net Eorum?ia wtt.:/eeew/ruuuuuoo-SSSSSS..S.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On latce-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609 04836, 2016.
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast Bayesian optimization of machine learning hyperparameters on large datasets. arXiv:/605.0700 2016 6a.
Aaron Klein, Stefan Falkner, Jost Tobias Springenberg, and Frank Hutter. Learning curve prediction with bayesian neural networks. 2016b.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. AXiv:/902.07000 2019.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, pp. 367-377. PMLR, 2020.
Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit- approach to hyperparameter optimization. arXiv:1603.06566 2016.
Hanxiao Liu, Karen Simonyan. and Yiming Yang. DARTS: Differentiable architecture search. In
International Conference on Learning Representations (ICLR), 2019.
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, pp. 1159-2167, JMLR. org, 2017.
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.
David JC MacKay. Bayesian methods for adaptive models. PhD thesis, California Institute of Technology, 1992.
David A McAllester. Pac-bayesian model averaging. In Proceedings of the twelfth annual confer- ence on Computational learning theory, pp. 164-170, 1999.
Jishnu Mukhoti, Viveka Kulharia, Amartya Sanyal, Stuart Golodetz, Philip HS Torr, and Puneet K Dokania. Calibrating deep neural networks using focal loss. arXiv preprint arXiv:2002.09437, 2020.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In Advances Neural Information Processing Systems, pp. 5947-5956, 2017.
Maria-Elena Nilsback and Andrew Zisserman. Automated flower classification over a large number of classes. In 2008 Sixth Indian Conference Computer Vision, Graphics & Image Processing, pp. 722-729. IEEE, 2008
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning (ICML), pp- 4092-4101, 2018.
10

---

Under review as a conference paper at ICLR 2021
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe V Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In International Conference Machine Learning (ICML), pp. 2902-29111 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780 2019.
Albert Shaw, Wei Wei, Weiyang Liu, Le Song, and Bo Dai. Meta architecture search. In Advances in Neural Information Processing Systems, pp. 11227-11237, 2019.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The im- plicit bias gradient descent on separable data. The Journal of Machine Learning Research, 19 (1):2822 2878, 2018.
Mingxing Tan and Quoe V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint 1rXi:: 2019.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. vrXiv://04.0f. 2019a.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search. In International Conference on Learning Representations (ICLR), 2019b.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe- darts: Partial channel connections for memory-efficient differentiable architecture search. arXiv preprint (tt::/907.05731 2019.
Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. NAS evaluation is frustratingly hard. In International Conference on Learning Representations (ICLR), 2020.
Chris Ying, Aaron Klein, Eric Christiansen, Estehan Real, Kevin Murphy, and Frank Hutter. NAS- Bench- 101: Towards reproducible neural architecture search. In International Conference on Machine Learning (ICML), pp. 7105-7114 2019.
Kaicheng Yu, Christian Sciuto, Martin Jaggi. Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In International Conference on Learning Repre- sentations, 2020. URL
Arber Zela, Aaron Klein, Stefan Falkner, and Frank Hutter. Towards automated deep learning: Efficient joint neural architecture and hyperparameter search. arXiv preprint rrXiv:1807.06966, 2018.
Arber Zela, Julien Siems, and Frank Hutter. Nas-bench-Ishot! Benchmarking and dissecting one- shot neural architecture search. In International Conference Learning Representations, 2020.
URL htttps://openne http:::////peneeiie..... So
wtrumoormmmmmm 2dd 83x9ngStPHI
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 16/ 1. 1.05530, 2016.
Pan Zhou, Caiming Xiong, Richard Socher, and Steven CH Hoi. Theory-inspired path-regularized differential network architecture search. arXiv preprint arXiv:2006. 16537, 2020.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations (ICLR), 2017.
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, pp. 8697-8710, 2018.
11

---

Under review as a conference paper at ICLR 2021
A DATASETS DESCRIPTION
The datasets we experiment with are:
NASBench-201 (Dong & Yang, 2020): the dataset contains information of 15.625 different neural architectures, each of which is trained with SGD optimiser and evaluated on 3 differ- ent datasets: CIFARIO, CIFA 100, IMAGENET-16-120 for 3 random initialisation seeds. The training accuracy/loss, validation accuracy/loss after every training epoch as well as architec- ture meta-information such as number of parameters, and FLOPs are all accessible from the dataset. The search space of the NASBench-201 dataset is a 4-node cell and applicable to almost all up-to-date NAS algorithms. The dataset is available at https: //gttub.///ttu.../ com/D-X-V NAS-Bench-201
WandWiredNN: we produce this dataset by generating 552 randomly wired neural architectures from the random graph generators proposed in (Xie et al. 2019a) and evaluating their perfor- mance on the image dataset FLOWERS 102 (Nilsback & Zisserman 2008). We explore 69 sets of hyperparameter values for the random graph generators and for each set of hyperparameter values, we sample 8 randomly wired neural networks from the generator. A randomly wired neu- ral network comprises cells connected sequence and each cell is a 32-node random graph. The wiring/connection within the graph is generated with one of the three classic random graph and Watt-Strogatz(WS) models. Each random graph models have 1 or 2 hyperparameters which decide the generative distribution over edge/node connection in the graph. All the architectures are trained with SGD optimiser for 250 epochs and other training set-ups follow those in (Liu et al. 2019). This dataset allows us to evaluate the performance of our simple estimator on hyperparameter/modell selection for the random graph generator. We will release this dataset after paper publication.
models in graph theory: EFdos-RenyiiER), Barabasi-Albert(/
we produce this dataset by randomly sampling 100 architectures from the search space used in DARTS (Liu et al., 2219)) and evaluating them on CIFAR10. This search space comprises a cell of 7 nodes. An architecture from this search space is formed by stacking the cell 8 or 20 times. Specifically, the first two nodes in cell are the input nodes which equals to the outputs of cell k - 2 and cell h: 1-1 respectively. The last node in the cell & is the output node which gives a depthwise concatenation of all the intermediate nodes. The remaining four intermediate nodes are operation nodes take can take one out of eight operation choices. This search space is larger and more general than that of NA NASBench-225 201, and is also widely adopted in NAS (Zoph et al.) 2018 Liu et al.] 2019 Chen al. 2019 Xie et al. 2019b Xu et al.] 2019 Real al. 2019 Li
DARTS:
& Tal walkar) 2020) Pham et al. 2018 Shaw et al. 2019 Zhou et al., 2020). In Section 5.2 we
experiment with the three different evaluation set-ups used in (Liu et al. 2019):
1. Search phase: We stack 8 cells to form the architecture and train the architecture for 150 epoch on CIFAR10 with a batch size of 128. We use the SGD optimiser with an initial learning rate of 0.05 and cosine-annealing schedule, momentum of 0.9 and weight decay 3 x 10-4;
2. Retraining phase for CIFARIO: We stack 20 cells to form the architecture and train the architecture for 150 epoch on CIFARIO with batch size of 96. We use the SGD optimiser with an initial learning rate of 0.025 and a cosine-annealin schedule, momentum of 0.9 and weight decay of 3 x 10
3. Retraining phase for ImageNet: We stack 20 cells to form the architecture and train the architecture for 150 epoch on CIFARIO 10 with a batch size of 128. We use the SGD optimiser with an initial learning rate of 0.1 and a step-decay schedule (decayed by factor of 0.97 after each epoch). momentum of 0.9 and weight decay of 3 x 10
For this dataset, we also record the training loss for each minibatch and an alternative validation accuracy value evaluated using the exponential moving average (EMA) of the network weights TTan & Le. (219)) on top of the conventional training and validation loss/accuracies. The mini- batch training loss is used to verify our claim that it is the sum of training losses, which has nice theoretical interpretation, instead of individual training loss that gives good correlation with the generalisation performance of the architectures. The EMA version of the validation accuracy is used to check whether a smoothed and improved version of the carly-stopped validation accuracy will have better correlation with the final true test performance.
12

---

Under review as a conference paper at ICLR 2021
Rebia)) 86)
EL (oiz)) Circca
60-
((ba))))))) 86)
Data point som
Figure 6: Example on simple Bayesian linear regression problem. We see that the sum over training losses gives an estimator for the lower bound L of model evidence, and that the SoTL measure is more effective than the final training loss at distinguishing the two models M, and M2.
B EXAMPLE ON BAYESIAN LINEAR REGRESSION
We illustrate how the SoTL metric corresponds to lower bound on the marginal likelihood that can be used for model selection in simple Bayesian linear regression setting. We consider an idcalised data set v) with X E Inx(n+1) and E IR", with X of the form X = (x:) = ((y, + Bayesian linear regression models MM and M2, each of which uses one of two different feature embeddings: d1 and d2. where &1 (z)
<6. O..... .... 0))==> and 6, _N(0, 1). We wish compare
the identity and (2(x)) = ee = (y + cu) retains only the single dimension that is correlated with the target, removing the noisy components of the input. The model which uses d2 will have less opportunity to overfit to training data, and will therefore generalise better than the model which uses Φ1; similarly, it will also have higher marginal likelihood. We demonstrate empirically in Fig. 6 that the SoTL estimator computed on the iterative posterior updates of the Bayesian linear regression models also exhibits this relative ranking, and illustrate how the SoTL relates to the lower bound described in Section B
C EFFECT OF SUMMATION WINDOW E
As shown in Fig. summing the training losses over E most recent epochs (SoTL-E) achieve higher rank correlation with the true test accuracy than summing over all the previous T epochs (SoTL), especially early on in training. We grid-search different summation window sizes E 10, 70 to investigate the effect of E and observe consistently across all 3 image datasets that smaller window size gives higher rank correlation during the early training phase and all E values converge to the same maximum rank correlation (Fig.
We further verify this observation by performing the same experiments on DARTS dataset for which we have saved the mini-batch training losses and thus can compute the sum of training losses for less than one epoch < For example, = 0.3 corresponds to the sum of training losses over the first 30% of the maini-batches/opiiiisst that E is the optimal choices although smaller summation window in general leads to better performance than large window sizes the very early part of the training. Thus, recommend E as the default choice for our SoTL-E estimator. Note SoTL-E=1 corresponds to the sum of training losses over all the batches in one single epoch.
steps in the epoch. The results in Fig. g show again
D TRAINING LOSSES VS VALIDATION LOSSES
D.1 EXAMPLE SHOWING TRAINING LOSS IS BETTER CORRELATED WITH VALIDATION ACCURACY THAN VALIDATION LOSS
We sample three example architectures from the NASBench-201 dataset and plot their losses and validation accuracies on CIFAR 100 over the training epochs T. The relative ranking for the vali- dation accuracy is: Arch A (0.70) > Arch B (0.67) Arch C (0.64), which corresponds perfectly (negatively) with the relatively ranking for the training loss: Arch A (0.05) < Arch B (0.31) < Arch C (0.69). Namely, the best performing architecture also has the lowest final training epoch loss. However, the ranking among their validation losses is poorly/wrongly correlated with that of validation accuracy; the perf-ineg architecture has the lowest final validation losses but the
13

---

Under review as a conference paper at ICLR 2021
0.975
1.000
0.950
0.950
0.975
Pank Correlation
0.925
S9TL
Correlation
0.925
Rank Correiation
0.950
S-
0.925
0.900
SoTL E-20
0.900
E-30
0.875
0.875
0.875
0.850
SoTl-E-Ro
0.850
0.825
0.825
0.025
0.800
0.800
0.000
Training Epoch T
Training Epoch T
Training Epoch
(a) CIFARIO
(b) CIFARIO0
(c) IMAGENET-I6-
Figure 7: Rank correlation performance of the sum of training losses over E' most recent epochs (SoTL-E) on the NASBench-201 dataset. Different E values are investigated for 5000 random architectures in IASBench-201 three image datasets. In all three cases, smaller E consistently achieves better rank correlation performance in the early training phase with E being the best choice.
0.00
0.45
5.90
SMT-C-00 6.5
6MT1--6.3
9.85
5UTLiz00
5.30
0.09
S0TL--1
56T1---0 6.7
56T1-2-1
0.85
5011-5-67
S6T1-C-1
20TL-C-30
So11:ce10
6.70
50T1-2-10
50 1:100010
0.60
SeTL---30
0.0
6.05
6.75
0.40
0.00
0.70
Training
Trairing
(a) 100005, bs=128, cells. cosine scheduler
(b) I==05025, bs=96, cells, cosine scheduler
(c) Ir-011, bs=128, cells, step-decay scheduler
Figure 8:
Rank correlation performance of the sum of training losses over E most recent epochs (SoTL-E) on the DARTS dataset. Different E values include those < 1 are investigated for 100 random architectures in DARTS search space under three different evaluation set-ups. all three settings, smaller E in general achieves better rank correlation performance in the early training phase with = again being the best choice. The performance of E not stable and deteriorates from F 1.
train loss
velld ecc
XC
Irain vo lil Ices
train
ace
70
ueild
valid loss
60
60
Trainvold Loss
wanaviie Lona
vild 40C0UI POO
20
20
20
10
200
200
150
200
Trainig spech
Trainig
Tra mi Spoch
(a) Arch A: Train loss=0.05, Val. loss=1.36, Val. acc 0.70
(b) Arch B: Train loss=0.31.
(c) Arch C: Train loss=0.69, Val. loss=1.29, Val acc = 0.64
Val. loss=1.30. Val. acc 0.67
Figure 9: Training losses, validation losses and validation accuracies of three example architectures on CIFARIO0. The average of the training losses, validation losses and validation accuracies over the final 10 epochs is presented in the subcaption of each architecture.
best- pess--eeformin architecture has the highest validation losses. Moreover, in all three examples, es- pecially the better-performing ones, the validation loss stagnates relatively high value while the
14

---

Under review as a conference paper at ICLR 2021
validation accuracy continues to rise. The training loss doesn't have this problem and it decreases while the validation accuracy increases. This confirms the observation we made in Section 5.2 that the validation loss will become unreliable predictor for the final validation accuracy well as the generalisation performance of the architecture as the training proceeds due to overconfident misclassification.
D.2
COMPARISON WITH SUM OVER VALIDATION ACCURACY
CIFARIO-VALID
CIFAR100
IMAGENET16-120
1:00
1.00
1.00
0.95
0.95
0.95
Rank Correlation
0.90
Rank Correlatoo
0.90
Rank Correlation
0.90
0.85
0.85
SOTL
SoTL
0.80
SOTAcE
0.80
SaTAcE
0.80
SoTAcE
0.75
SOVACE
SATT-E
0.75
SoVAcc
0.75
W47 1.
SoVAcc
0.70
SOVL-E
/.
SOVL-E
SOVL-E
0.65
SoTAcc-F
0.65
SaTAcc-E
0.65
SoTAcc-E
E
SOVAcc
SoVAcc
0.60
0.60
0.60
10a
10a
101
10
10
10"
Training Epoch T
Training Epoch
Training Epoch
(a) CIFARIO
(b) CIFARIOO
(c) IMAGENET-16-- 16-100166220000
Figure 10: Rank correlation performance of the sum over training losses, SoTL (red), the sum over training accuracy, SoTAce (blue), the sum over validation losses, SoVL (purple) and the sum of validation accuracy, SoVAcc (green) for 5000 random architectures in NASBench-201 on three image datasets. Note SoTL denotes the summation from epoch 0 to epoch T and SoTL-E denotes the summation over the most recent epoch T. The same applies for those of SoVL.-E. SoTAcc/SoTAcc-EE and So VAcc-E. The results on CIFARIO and CIFAR 100 confirm the discussion Section 5.2 and in the subsection above; as the training proceeds, the validation loss can become poorly correlated with the validation/test accuracy while the training loss still perfectly correlated with the training accuracy. Thus, another baseline to check against is the over validation accuracy, Vo VAcc-F. It's expected that SoVAcc- should converge to a perfect rank correlation (=1) with the true test performance the end of the training. However, the results in (a), (b) and (c) show that our proposed estimator SoTL-E can consistently outperform So VACCC- in the early and middle phase of the training (roughly T < 150 epochs). This reconfirms the usefulness of our estimator.
D.3 OVERHITING ON CIFARIO AND CIFARI00
In Figure 2 in Section 5.2, the rank correlation achieved by SoTL-E CIFARIO and CIFAR100 will drop slighted after around T = 150 epochs but similar trend is not observed for IMAGENET- 16-120. We hypothesise that this is due the fact that many architectures converge very small training losses on CIFAR 10 and CIFARIOR in the later training phase, making it more difficult to distinguish these good architectures based on their later-epoch training losses. But this doesn't happen on IMAGENET-16 120 because it's more challenging dataset. We test this by visualising the training loss curves of all 5000 architectures Figure Taa where the solid line and error bar correspond to the mean and standard error respectively. We also plot out the number of architectures with training losses below 0.1 Figure 1 It is evident that CIFARIO and CIFAR 100 both see an increasing number of overfitted architectures as the training proceeds whereas all architectures still have high training losses on IMAGENET-I6- 120 at end of the training T = 200 with none of them overfits. Thus, our hypothesis is confirmed. In addition, similar observation is also shared in Jaing et al. 2020) where the authors find the number of optimisation iterations required to reach loss equals 0.1 correlates well with generalisation but the number of iterations required going from loss equals 0.1 to loss equals 0.01 doesn't.
'he threshold 0.1 chosen following the threshold for optimisation-baser measures in Jiang* al. 2020
15

---

Under review as a conference paper at ICLR 2021
CIFAR1O-VALID
CIFAR100
IMAGENET16-120
N archhs with loss <0.1
10a
Training loss
102
2
10
1
50
100
150
200
50
100
150
200
Training Epoch T
Training Epoch T
(a) Training loss
(b) No. of with loss 0.1
Figure 11: Mean and standard error of training losses and validation losses on 5000 architectures on different NASBench-200 caanchh22limmann image datasets. (a) shows the training curves and (b) shows the number of architectures whose training losses go below 0.1 as the training proceeds. Many architectures reach very small training loss in the later phase of the training on CIFAR 10 and CIFAR 100, thus may overfitting on these two datasets. But all the architectures suffer high training losses on IMAGENET- 16- 12- which is much more challenging classification task, and none of them overfits.
E ADDITIONAL NAS EXPERIMENTS
In this work, incorporate our estimator, SoTL-E, T 50 into three NAS search strategies: Regularised Evolution (Real et al. 2019), TPE (Bergstra et al. 2011 and Random Search (Bergstra & Bengio 2012) and performance architecture search NASBench-201 datasets. We modify the
implementation available at lhtps:: //gibub.. com/ aut huttom///abbbenccaakk three methods.
benchmarks for these
0.1050
Val Acc (T=200)
0.305
Val Acc (T=200)
Val Acc (T=200)
0.1025
Val Acc (T=50)
0.300
Val Acc (T=50)
0.565
Val Acc (T=50)
SoTL-E (T-50)
0.295
SoTL-E (T=
0.560
SoT (T=50)
Best test
0.290
Best test
0.555
0.285
0.550
0.0925
0.280
0.0900
0.275
0.535
0.0875
0.270
20
40
60
50
100
150
200
Run time (hours)
Run time (hours)
time (hours)
(a) RS-CIFARIO
(b) RS-CIFARI00
(c) RS EE-IMAGENET--6... 16-
Figure 12: NAS performance of Random Search (RS) combined with final validation accu- racy (Final Val Acc), carly-stop validation accuracy (ES Val Acc) and our estimator SoTL-E on NASBench-201. SoTL-E enjoys competitive convergence as ES Val Acc and both are faster than using Final Val Acc.
Random Search (Bergstra & Bengio 2012) is very simple yet competitive NAS search strategy
(Dong & Yang 2020). We also combined our estimator, SoTL-E, at training epoch T = 50 with Random Search to perform NAS. We compare it against the baselines using the final validation = 50, denoted as Val Ace (T=50). Other experimental set-ups follow Section 5.5. The results over running
curacy at T 200, denoted as Val Ace (T=200), and the early-stop validation accuracy
16

---

Under review as a conference paper at ICLR 2021
hours all three image tasks shown in Figure 12 The use of our estimator clearly leads to faster convergence as compared to the use final validation i... Val Acc (T=200). Moreover, our estimator also outperforms the early-stop validation accuracy, Val Acc (T=50) on the two more chal- lenging image tasks, CIFAR 100 and IMAGENET-I6-1 performance gain of using estimator the early-stopped validation accuracy is relatively less significant in the case of Random Search compared to the cases of Regularised Evolution and TPE. For example, given budget 150 hours on CIFAR 100, Regularised Evolution and TPE when com- bined with our estimator can find an architecture with test error around or below 0.26 but Random Search only finds architecture with test eπrоr of around 0.27. This due the fact that Random Search is purely explorative while Regularised Evolution and TPE both trade off exploration and exploitation during their search; our estimator by efficiently estimating the final generalisation per- formance of the architectures will enable better exploitation. Therefore, we recommend the users to deploy our proposed estimator onto search strategies which involve some degree exploitation to maximise the potential gain.
and is on par with on CIFAR1O. The
17


Reviews:
[{"review_id": "k28BWRPs4Ee", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a simple model-free method to estimate the generalization performance of deep neural architectures based on their early training losses. The proposed method uses the sum of training losses during training to estimate the performance and is motivated by recent empirical and theoretical results. The experimental results show that the proposed estimator outperforms the existing methods that predict the performance ranking among architectures.\n\nPros\n- The proposed approach is simple yet shows better performance than the existing estimator.\n- This paper is discussed from both theoretical and empirical perspectives.\n\nCons\n- I am wondering how the proposed estimator can be used in recent gradient-based NAS methods. For instance, DARTS optimizes architecture parameters during the search phase and pick up the top two operations that have the highest values after optimization. Is it possible to use the proposed estimator for DARTS optimization (i.e. recent gradient-based methods) and to speed up the optimization? Also, although One-shot NAS based on random sampling (e.g [1]) achieves good performance, can we apply the proposed method to such methods? I would like to know the scope of the application of the proposed method.\n- In the first experiment, this paper randomly samples 100 architectures from the DARTS search space and evaluate the proposed estimator based on them. I would like to see the behavior of the proposed method with more samples to get a more accurate understanding because the search space of DARTS is much large.\n- Regarding Figure 5, in the case of the regularized evolution (RE), I would like to know how much the speed of the optimization is improved. For instance, it would be nice to provide how much the proposed method can speed up the optimization to achieve the same performance reported in their paper. I am also interested in how fast it is compared with recent gradient-based NAS methods.\n[1] G. Bender+, Understanding and Simplifying One-Shot Architecture Search, ICML, 2018\n\nOverall, this paper proposes a simple yet effective method to estimate the generalization performance among deep neural networks and it is motivated by both empirical and theoretical aspects. However, there are some unclear points to be clarified for the publication as described above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "gL5b0-RPssX", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "###############################################################\n\nSummary:\n\nThis paper provides a new method for estimating the generalization performance of neural architectures. This method used the sum of training loss as a criterion. The paper gave some intuitions about the method from the perspective of Bayeian model selection. \n\n###############################################################\n\nReason for Score:\n\nUsing training loss to improve generalization performance is unreasonable. And the paper didn't give some convincing reason to this method. The method has no theoretical guarantee, and its analogy with Bayesian model selection seems problematic.\n\n###############################################################\n\ncons:\n\n1, The method in this paper purely used training loss as a criterion for generalization performance. This is unreasonable. And the paper didn't give some convincing reason to this method.\n\n2, The analogy with the Bayesian model selection is problematic. In Bayesian model selection, the parameter in the following step is the posterior estimator based on previous data. This paper think of the SGD optimizer as a way to find the posterior estimator. This is problematic.", "extra_scores": {}, "extra_text": {}}, {"review_id": "X6Ibs-oztA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Instead of using validation accuracy to determine the efficacy of a network,  this paper recommends to use Sum over Training Losses (SOTL). SOTL-E is a variant where the sum of training losses begins to be computed after the first E epochs. \nThey also designed an early stopping mechanism based on Baker et al's SVR where they extrapolate SOTL instead of validation accuracy.\n\nQuestions:\n1. How can training loss be used to identify a good network? It should theoretically lead to overfitting and poor generalization. Going by this argument, if we apply any kind of regularization such as dropout or weight decay, the training loss would not be low  while the test accuracy might still improve.\nIt is surprising that SOTL-E is able to rank the networks better than TestL at 200 for cifar10 and cifar100. Why do you think this is the case? \n\n2. DARTS Experiment: \n   (a) In  Figure 3(a), how is DARTS search replicated using just 100 random architectures? As it uses a SuperNet, it requires all possible architectures possible with the chosen operations. \n   (b) In  Figure 3(b) and 3(c), the final architecture needs to be trained for 600 epochs. So it is natural that the rank correlation of SOVL, SOVL-E etc is poor for the first 100 epochs. \n\n3. What would be more interesting is,  DARTS currently they perform a bi-level optimization. So instead of the architecture parameters $\\alpha$ trying to minimize the validation loss, can they also minimize the training loss (theoretically this should not generalize well)? If not this, can you devise a way to plug in SOTL in the bi-level optimization and choosing the best architecture? If SOTL performs well even in that case, then you could a stronger case.\n\n4.  Training very deep networks is not easy and takes more than 100 epochs to obtain good accuracy. So your observation might be a side effect of that too.  As SOTL could be applied to any deep learning networks, can you also repeat the experiment by training 100 networks sampled from a smaller search space, such as mobile search space (mobilenet, squeezenet, shufflenet etc), that takes less than 80 epochs to finish training, to see if it still holds true? Then use this SOTL and SOTL-E to determine the best network. Also compare with the baselines.\n\n5. In Figure 4, how do SOVL, SOVL-E and Validation accuracy fare? Please include those too in the plots. \n\n6. What is the difference between the setup of 1 and 2 (a) to (c) apart from the fact that SOVL-E and TestL are not included in 2?\n\n7. If SOTL-E is the average training loss of the final epoch, why not call it that? (I understand that it is still the sum of losses for all the batches but as it not across epochs it is misleading).\n\nAs this is paper is proposing something that is fundamentally opposite to what has been studied widely thus far, it requires a lot more scrutiny. I do not think we can accept it with just empirical results and the theoretical motivation currently provided.\n\n_____________________________\n_____________________________\nPost Rebuttal:\n\nThank you for replying to all of my questions.. \n\nPlugging in your new metric to DARTS seems to be promising, especially if it alleviates the DARTS collapse problem. Given that the community is more interested in one-shot NAS algorithms, this might be worthwhile pursuing\n\nFrom the new plot in Figure 4 and NAS experiment in Figure 5, it is evident that the sum of training loss is able to rank the networks more effectively in the first 50 epochs. So one could use SOTL-E for early stopping rather than validation accuracy. This would also be effective in hyperband where the architectures are discarded after training them for very few epochs.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes to use the sum of training losses during training, or a variant where the sum of training losses begins to be computed after the first E epochs, to estimate the generalization performance of the corresponding network. Although the results seem promising for query-based NAS strategies, the reviewers agree that as the paper proposes something that is fundamentally opposite to the common practice, it requires more careful and thorough analysis. Besides, while the connection made by authors to the Bayesian marginal likelihood is interesting, it's not a rigorous argument that convinces the audience about the applicability of the proposed method. I strongly encourage the authors to add more analysis and discussion to the revised version to strengthen their claim and clarify its scope.


Decision: Reject