Neural Architecture Search without Training
Authors: Joseph Mellor
Jack Turner
Amos Storkey
Elliot J. Crowley
Venue:  (2021)
Keywords: NAS
efficiency
search
fast
cheap
convnets

Abstract: The time and effort involved in hand-designing deep neural networks is immense. This has prompted the development of Neural Architecture Search (NAS) techniques to automate this design. However, NAS algorithms tend to be slow and expensive; they need to train vast numbers of candidate networks to inform the search process. This could be remedied if we could infer a network's trained accuracy from its initial state. In this work, we examine the correlation of linear maps induced by augmented versions of a single image in untrained networks and motivate how this can be used to give a measure which is highly indicative of a network’s trained performance. We incorporate this measure into a simple algorithm that allows us to search for powerful networks without any training in a matter of seconds on a single GPU, and verify its effectiveness on NAS-Bench-101 and NAS-Bench-201. Finally, we show that our approach can be readily combined with more expensive search methods for added value: we modify regularised evolutionary search to produce a novel algorithm that outperforms its predecessor.

Under review as a conference paper at ICLR 2021
NEURAL ARCHITECTURE SEARCH WITHOUT TRAINING
Anonymous authors Paper under double-blind review
ABSTRACT
The time and effort involved in hand-designing deep neural networks is immense. This has prompted the development of Neural Architecture Search (NAS) tech- niques to automate this design. However, NAS algorithms tend be slow and expensive; they need to train vast numbers of candidate networks to inform the search process. This could be remedied if we could infer a network's s trained accuracy from its initial state. In this work, we examine the correlation of linear maps induced by augmented versions of a single image in untrained networks and motivate how this can be used to give a measure which is highly indicative of network's 's trained performance. We incorporate this measure into a simple algorithm that allows to search for powerful networks without any training in a matter of seconds on a single GPU, and verify its effectiveness on NAS-Bench-100 Finally,
and NAS-B LuS--Bnch-200 bined with more expensive search methods for added value: we modify regularised evolutionary search to produce a novel algorithm that outperforms its predecessor.
show that approach can be readily com-
INTRODUCTION
The success of deep learning in computer vision is in no small part due to the insight and engineering
efforts of human experts, allowing for the creation of powerful architectures for widespread adop- tion (Krizhevsky et al. 2012, Simonyan & Zisserman 2015 He et al. [016] Szegedy et al., 2016)] Huang et 2017). However, this manual design is costly, and becomes increasingly more difficult as networks get larger and more complicated. Because of these challenges, the neural network community has seen shift from designing architectures to designing algorithms that search for candidate architectures (Elsken et al. [2099 Wistuba et al.) 2019). These Neural Architecture Search (NAS) algorithms are capable of automating the discovery of effective architectures (Zoph & Le
2017 Zoph al. 2018 Pham al. 2018 Tan et al. 2019 Liu et al. 2019
Real et al., 2019).
NAS algorithms are broadly based on the seminal work of Zoph & Le 2017). A controller network generates architecture proposal, which is then trained to provide signal the controller through REINFORCE (Williams 1992). which then produces a new proposal, and so on. Training a network for every controller update extremely expensive; utilising 800 GPUs for 28 days in Zoph & Le) (0077). Subsequent work has sought to ameliorate this by (i) learning stackable cells instead of whole networks (Zoph et al. 2018) and (ii) incorporating weight sharing; allowing candidate networks to share weights to allow for joint training (Pham et al. 2018). These contributions have accelerated the speed of NAS algorithms e.g. to half a day on a single GPU Pham et al. (2018).
For some practitioners. NAS is still too slow; being able to perform NAS quickly (i.e. in seconds) would be immensely useful in the hardware- aware setting where separate search is typically required for each device and task (Wu et al.] 2019 Tan et al. (209)). Moreover, recent works have scrutinised NAS with weight sharing (Li & Talwalkar 2019: Yu et al.) 2020); there is continued debate as to whether it is clearly better than simple random search.
The issues of cost and time, and the risks of weight sharing could be avoided entirely a NAS algorithm did not require any network training. In this paper, we show that this can be achieved. We explore two recently released NAS benchmarks, MAS--Bnnh-11e 101 (Ying et al. 2019), and NAS- Bench-201 (Dong& & Yang 2020) and examine the relationship between the linear maps induced by an untrained network for a minibatch of augmented versions of a single image (Section B) These maps are easily computed using the Jacobian. The correlations between these maps (which denote

---

Under review as a conference paper at ICLR 2021
[60.0%, 70.0%)
[70.0% 80.0%)
[80.0% 90.0%)
90.0%
-1
-1
0
1
-1
0
(a) NAS- MAS-Bench-101
[60.0% 70.0%)
[70.0%
80.0%)
[80.0% 90.0%)
>= 90.0%
-1
-1
0
1 1
0
1
-1
0
1
(b) NAS-Bench-e
Figure 1: Histograms of the correlations between linear maps in an augmented minihatch a single CIFAR-10 image for untrained architectures in (a) NAS-Bench-1u (b) NAS-Bench-201. The histograms are sorted into columns based on the final CIFAR-IO validation accuracy when trained. The y-axes are individually scaled for visibility. The profiles distinctive; the histograms for good architectures in both search spaces have their mass around zero with small positive skew. We can look at this distribution for untrained network to predict its final performance without any training. More histograms are available in Appendix A
by Σ)) are distinctive for networks that perform well when trained on both immediately apparent from visualisation alone (Figure T. We devise score based on Σ, and perform an ablation study to demonstrate its robustness to inputs and network initialisation.
this
simple search algorithm that doesn't require training (Section This allows to perform architecture search quickly, for example, on CIFAR-10 10 (Krizhevsky 2009) we are able to search for a network that achieve 93.36% accuracy in 29 seconds within the NAS-Bench-200 search space; several orders of magnitude faster than traditional NAS methods for modest change in final accuracy (e.g. REINFORCE finds 93.85% net in 1200 seconds). Finally, we show that we combine our approach with regularised evolutionary search (REA, (REA,|Pham et al. (018)) to produce a new NAS algorithm, Assisted-RES (AREA) that outperforms its precedessor, attaining 94.16% accuracy on NAS- MAS--Bnnh-101 in 12,000 seconds. Code for reproducing our experiments is available in the supplementary material.
We incorporate our score
We believe this work is important croff-of-coneppt for NAS without training, and shows that the large resource costs associated with NAS can be avoided. The benefit is two-fold, as we also show that we can integrate our approach into existing NAS techniques for scenarios where obtaining as high an accuracy as possible is of the essence.
2 BACKGROUND
Designing neural architecture by hand a challenging and time-consuming task. extremely difficult to intuit where to place connections, which operations use. This has prompted an abundance research into neural architecture search (NAS); the automation of the network design process. In the pioneering work of Zoph & Le (007). the authors RNN controller generate
2

---

Under review as a conference paper at ICLR 2021
descriptions of candidate networks. Candidate networks are trained, and used to update the controller using reinforcement learning to improve the quality of the candidates it generates. This algorithm is very expensive: searching for an architecture to classify CIFAR-10 required 800 GPUs for 28 days. It is also inflexible; the final network obtained is fixed and cannot be scaled e.g. for use on mobile devices or for other datasets.
The subsequent work of Zoph et al. (2018) deals with these limitations. Inspired by the modular nature of successful hand-designed networks (Simonyan & Zisserman| [015 He et al. 2016:] Huang
et al. 2017), they propose searching over neural building blocks, instead of over whole architectures. These building blocks, or cells, form part of fixed overall network structure. Specifically, the authors learn standard cell, and a reduced cell (incorporating pooling) for CIFAR-10 classification. These are then used as the building blocks of a larger network for ImageNet (Russakovsky et al. 2015) classification. While more flexible-thh the number of cells can be adjusted according to budget- and cheaper, owing to a smaller search space, this technique still utilises 500 GPUs across days.
ENAS (Pham et al. 2018) reduces the computational cost of searching by allowing multiple candidate architectures to share weights. This facilitates the simultaneous training of candidates, reducing the search time on CIFAR-10 to half a day on a single GPU. Weight sharing has seen widespread adoption
in a host of NAS algorithms (Liu et al. 2019, Luo et al. 2018: Caa et al. 2019; Xie et al. 2019
Brock et al. 2018). However, there evidence that it inhibits the search for optimal architectures Yuu et al.
2020). Moreover, random search proves to be an extremely effective NAS baseline (Yu et al.
2020 Li & Talwalkar 2019). This exposes another problem: the search space is still vast- vast-there
1.6 x 10ad possible architectures in Pham et al. (0188) for example-thai it is impossible to isolate
the best networks and demonstrate that NAS algorithms find them.
An orthogonal direction for identifying good architectures is the estimation of accuracy prior to training (Deng et al. 2017 Istrate et al., 2019), although these differ from this work in that they rely on training a predictive model, rather than investigating more fundamental architectural properties.
2.1 NAS BENCHMARKS
A major barrier to evaluating the effectiveness of a NAS algorithm is that the search space (the set of all possible networks) is too large for exhaustive evaluation. Moreover, popular search spaces have been shown to be over-engineered, exhibiting little variety in their trained networks Yang
et al. 2020). This has led to the creation of several benchmarks (Ying et al.) 2019 Zela al. 2020
Dong& & Yang 2020) that consist of tractable NAS search spaces, and metadata for the training of networks within that search space. Coneretely, this means that is now possible to determine whether an algorithm is able to search for a good network. In this work we utilise NAS- NAS-Bench-100 (Ying let al. 2019) and NAS-Bench-200 (Dong& & Yang 2020) to evaluate the effectiveness of our approach. NAS- MAS-Bench-100 101 consists of 423.624 neural networks that have been trained exhaustively, with three different initialisations, on the CIFAR- 10 dataset for 108 epochs. NAS-Bench-20 consists of 15.625 networks trained multiple times on CIFAR- 10, CIFAR-100, and ImageNet-16-120 (Chrabaszez et al.
2017 Both benchmarks are described in detail in Appendix B
3 SCORING NETWORKS AT INITIALISATION
Our goal is to devise means to score a network architecture at initialisation in way that is indicative of its final trained accuracy. This can either replace the expensive inner-loop training step in NAS, or better direct exploration in existing NAS algorithms.
Given a neural network with rectified linear units, we can, at each unit in each layer, identify a binary indicator as whether the unit is inactive (the value is negative and hence is multiplied by zero) or active (in which case its value is multiplied by one). Fixing these indicator variables, it is well known that the network is now locally defined by linear operator (Hanin & Rolnick] 2019); this operator is obtained by multiplying the linear maps at each layer interspersed with the binary rectification units. Consider a minibatch of data X { 1 Let us denote the linear map for input x; E RD by column vector w,, which maps the input through the network f fxx) to a final choice of scalar
0f()) representation 2; E T This linear map can be easily computed using the Jacobian w; 8x
3

---

Under review as a conference paper at ICLR 2021
foud foea
@foss
@/iss)
(f
COIT
score
Σ I ( (E5()م)))
Ux
Figure 2: How to score untrained networks: (i) Create minibatch of an image repeatedly augmented with cutout; (ii) Perform a forward and backward pass using that minibatch to compute J; (iii) Compute the correlation matrix for J and count the number of entries in it that lie between and 3.
How differently network acts at each data point can be summarised by comparing the corresponding local linear operators. Correlated operators for nearby points (such as small perturbations from training point) relate potential difficulty in handling the points differently during learning. The Frobenius inner product Tr((w; 14)² (w, (2)]] provides a natural basis for defining how two linear operators corresponding to data points x; and x, covary (p are mean Jacobian elements, and usually close to zero). We can examine the correspondences for the whole minibatch by computing
(8((x))
8.(xg)
0f(xx) 8x
8x
8x
M,)" where M, is the matrix with entries (M,), = Н E Jadd Vt, where d, f index over the elements of each input (i.c. channels x pixels). It is more salient to focus on the the correlation matrix E, as the appropriate scaling in input space around each point is arbitrary. The (i,j) element of Σ, is given by (Es).. (C.),,
and observing the covariance matrix (J-
(CC.),
We want an untrained neural network to be sufficiently flexible to model a complex target function. However, also want network be invariant small perturbations. These two requirements antagonistic. For an untrained neural network to be sufficiently flexible it would need to be able to distinguish the local linear operators associated with each data point: if two the same then the two points are coupled. To be invariant to small perturbations the same local linear operators would need be weakly coupled. Ideally a network would have low correlated local maps associated with each data point to be able to model each local region.
We empirically demonstrate this by computing Σ, for random subset of NAS-Bench- 101 (Ying et al., (019)) and NAS-Bench-201 (Dong & Yang. (020) networks at initial- isation for minibatch of a single CIFAR-IÓ image replicated 256 times with dif- ferent cutout (DeVries & Taylor 2017) perturbation applied to each replicant.
We use torchvisi wwecchiisinn..m Gransforme RandomErasine (p=0. 9, scale= (0. 02, 0.04)) in our experiments. To form J we flatten the Jacobian for each input (so D = 3 x 32 x 32 3072), and adjust the final classifier layer to output a scalar. The plots of the histograms networks, categorised according the validation accuracy when trained given in Figure 1 for sample of networks in both benchmarks. Further plots are given in Appendix A
Σ, for different
The histograms very distinet: high performing networks in both benchmarks have their mass tightly around zero with a small positive skew. We can therefore use these histograms to predict the final performance of untrained networks, in place of the expensive training step in NAS. Specifically, we score networks by counting the entries in Σ, that lie between and an small upper bound 3. A E, where inputs are marginally positively-correhle
will have higher score. Our score given by
S= S= (0 (Ea)ss 3) w
4

---

Under review as a conference paper at ICLR 2021
NAS-Bench-101 cifar10 T 0.437
NAS-Bench-201 cifar10
== 0.527
6,0E+4
6.0E+4
5.0E+4
5,0E+4
4.0E+4
4.0E+4
3.0E+4
Score
3.0E+4
2.0E+4
2.0E+4
1.0E
1.0E+4
0E+0
0E+0
50
80
90
95
50
80
90
Validation accuracy
Validation accuracy
NAS-Bench-22 cifar100 T= 0.555
NAS-Bench-22 ImageNet
0.485
6.
6.0E+4
5.0E+4
5.0E+4
4.0E+4
4.0E
Score
3.0E+4
3.0E+4
2.0E+4
2.0E+4
1.0E+4
1.0E+4
0E+0
60
70
20
Validation accuracy
Validation accuracy
Figure 3: Plots of our score for 1000 randomly sampled untrained architectures in NAS-Bench-101 and WAS-Bench-201 against validation accuracy when trained. The inputs when computing the score and the validation accuracy for each plot are from CIFAR-10 (top). CIFAR- 100 (bottom-left and ImageNet16- 120 (bottom-right) In all cases there is a noticeable correlation between the score for an untrained network and the final accuracy when trained.
where 1 is the indicator function. In this work set 3 = 1. An overview is provided in Figure 2 To be clear, we are not claiming this score is particularly optimal; rather we use to demonstrate that there ways of scoring untrained networks that provide significant value for architecture search.
We sample 1000 different architectures at random from plot our score on the untrained network versus their validation accuracies when trained for the datasets in these benchmarks in Figure 3 In all cases there is a strong correlation between our score and the final accuracy, although
101 and NAS-Bench-201 and
noisier for ImageNet- 16-120; this dataset has smaller images compared to the other datasets so it may be that different cutout parameters would improve this. In Section we demonstrate how our score can be used in NAS algorithm for extremely fast search.
3.1 ABLATION STUDY
How important the image used to compute the score? Our score relies on a single image being repeatedly augmented to form minibatch. To determine how important the image randomly select 9 architectures in MAS-Bench-201 and compute the score separately for 10 random CIFAR-10 10 images. The resulting hox-anr-whisker plot is given in (left): different architectures vary in
5

---

Under review as a conference paper at ICLR 2021
CIFAR-10 images
Random images
40000
40000
score
score
20000
20000
0
0
5 6 7 8 Uninitialised network
1
2
3 4
0
2 3
4
5
6 7 8
Uninitialised network
Figure 4: Effect of different CIFAR-10 image (left), and random input images (right) for 9 randomly selected MAS-Bench-201 architectures (one in each 10% percentile range from 10-20, ... 90-100). Random input data are normally distributed. For each network 10 samples were taken for each ablation. There less variance score when using different random input images as opposed to different CIFAR-10 images.
sensitivity, although the ranking of the scores is reasonably robust to the specific choice of image. In Figure&rigg right) compute our score using normally distributed random inputs, which seems have little impact on the general trend. This leads us to believe the score captures property of the network architecture, rather than something data-specific.
Does the score change for different intialisations? Figure (bottoo-left) in Appendix C shows the score for different initial weights. This has small effect on the score, supporting the idea that are quantifying an architectural property.
Does the size of the minibatch matter? The size of Σ, scales with minibatch size. As our score sums entries of this matrix, we need to normalise our score to compare different minibatch sizes. F bittom-right) in Appendix C presents this normalised score for different minibatch sizes, which shows little variation.
What cell types score highly? We were unable detect any obvious patterns in the types of network architecture our score ranks highly. High scoring networks contained range of operations, and connectivities. We leave fine-grained analysis of this for future work.
NEURAL ARCHITECTURE SEARCH WITHOUT TRAINING: - NASWOT
In Section 3 we derived a score for cheaply rank- ing networks initialisation based their pected performance (Equation 2). Here as a proof of concept, we integrate this score into simple search algorithm and evaluate its ability to alleviate the need for training in NAS. Code for reproducing our experiments is available in the supplementary material.
Table 1: Mean + std. accuracy from NAS-Bench- 101. NASWOT is our sampling algorithm (500 runs). REAL (our implementation of REA) uses evolutionary search to select an architecture (50 runs), Random selects one architecture (500 runs). AREAL (aSA)))ed-REAA)) uses our score to select the starting population for REAL (50 runs). Search times for REAL and AREAL were calculated using the NAS-Bench-101 API.
Many NAS algorithms are based on that of Zoph (017). J. which is illustrated Algorithm It consists of learning generator network which proposes an architecture. The weights of the generator are learnt by training the networks it generates, either on a proxy task or on the dataset itself, and using their trained accuracies as signal through e.g. REINFORCE (Williams) 1992). This is repeated until the generator is
Method
Search (s)
CIFAR-10
Random
N/A
90.38+5.51
NASWOTO==000)
55
92.9540.88
REAL
12000
93.88+0.30
AREAL (Ours)
12000
94.16+0.18

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Standard NAS
Algorithm 2 NASWOT
generator GeneratorNett)
generator RandomGeneratoor)
best_net, best_score None, 0 for i=1:N do
for i do
net cennerator.generater
net generator (ccneratorggeneraee generate()
trained net net.train()
score = net.score)
Training net every step is expensive
if score > best score then best_net, best_score = net, score
ceneraaorrppdate(rraieeed.d
chosen_nee net generatoo..eneratte)
chosen net best_network
trained; it then produces final network which is the output of this algorithm. The vast majority of the cost is incurred by having to train candidate architectures for every single controller update. Note that there exist alternative schema utilising c.g. evolutionary algorithms such (Real et al. 2019) or bilevel optimisation (Liu et al. 2019) but all involve a training element.
We instead propose a simple a neural network as a generator, we randomly propose a candidate from the search space and then rather than training it, score it in its untrained state using Equation [ We do this N times- -ic. have a sample size of N architectures- requires computing gradients for a single minibatch, this takes very little time.
in Algorithm Instead of having
then output the highest scoring network. As scoring only
NAS-Bench-101. We compare NASWOT to 1 12000 seconds of REAL-ou our implementation of REA (Real et al., 2019) and random selection on NAS- MAS-Bench-101 101 (Ying et al./ 2019) in Table I We can see that we are able to find a network with a final accuracy within a percent of REAL in under minute on a single GPU.
NAS-Bench-201. Dong & Yang (2200) benchmarks a wide range of NAS algorithms, both with and without weight sharing, that we compare to NASWOT. The weight sharing methods are random search with parameter sharing (RSPS, [L & Talwalkar 2019). first-order DARTS (DARTS- V1, Liu al. 2019), second order DARTS (DARTS-VE V2, Liu et al. 2019), GDAS (Dong & Yang 201 9b),
SETN (Dong & Yang 2019a), and ENAS (Pham et al. 2018). The non- weight sharing methods are random search with training (RS), REA (Real et al. 2019). REINFORCE (Williams) 1992), and BOHB (Falkner et al. 2018). For implementation details we refer the reader to Dong & Yang (2020). The hyperparameters in NAS-Bench-201 for training and search are fixed - these results may not be invariant to hyperparameter choices, which may explain the low performance of c.g. DARTS.
We report results on the validation and test sets of CIFAR- 10, CIFAR-100, and ImageNet- 120 in Table 2 Search times are reported for CIFAR-10 a single GeForce GTX 1080 Ti GPU. As setup, the nei-weight sharing methods are given a time budget of 12000
per the seconds. For NASWOT and the non-weight sharing methods, accuracies are averaged over 500 runs. For weight-sharing methods, accuracies are reported over 3 runs. We report NASWOT for sample sizes of 1=10 and 1=100. With the exception of GDAS (Dong & Yang 2019b), NASWOT is able to outperform all of the weight sharing methods while requiring a fraction of the search time.
The noi-wt sharing methods do outperform NASWOT, though they also incur large search time cost. REA for instance, also requires a large memory budget due to the maintenance of a population of parallel architectures which may suffer from scalability issues as model and dataset sizes increase. For CIFAR- 10 and CIFAR- 100 NASWOT is able to find networks with performance close to the best non-weight sharing algorithms, suggesting that network architectures themselves contain almost as much information about final performance at initialisation as after training.
Table 2
also shows the effect of sample size (N). We show the accuracy of networks chosen by our method for each N. We list optimal accuracy for each N. and random selection over the whole bench- mark, both averaged over 500 runs. We observe that sample size increases NASWOT performance.
A key practical benefit of NASWOT is its execution time. Where time is a constraint, our method is very appealing. This may be important when repeating NAS several times, for instance for several hardware devices datasets. This affords us the ability in future to specialise neural architectures for a task and resource environment cheaply, demanding only a few seconds per setup. A visualisation of the time/accuracy trade-off for different mehods is shown in Appendix D
7

---

Under review as a conference paper at ICLR 2021
Table 2: Mean std. accuracies on NAS-Bench-201 datasets. Baselines are taken directly from Dong & Yang 2020), averaged over 500 runs (3 for weight-sharing methods). Search times are given for a CIFAR- 10 search on a single 1080Ti GPU. NASWOT CIFARIO 10-search refers to searching on the CIFAR-10 dataset and then evaluating the final model on an alternative dataset. Performance of our training-free approach is given for different sample size N (also 500 runs). We also report the results for picking network at random, and the best possible network from the sample. i This is our own implementation of REA for fair comparison against AREAL (50 runs each).
CIFAR-10
CIFAR-100
ImageNat-16-120
Method
Search
validation
test
validation
test
validation
test
Non-weight sharing
REA
12000
91.1910.31
93,92=0.30
718111112
7188110.99
45.15
15.51=:1003
RS
12000
90.93:10.36
93.70.10.36
70.93:11.09
1.00111077
44.451:.10
44.57::1.25
REINFORCE
12000
91.0911..37
93.85
71.111112
71.7111009
45.051:1.02
45.24
BOHB
12000
90.82:0..53
93.61:0.52
70.74::1.29
70.85&1.28
4..26
4..42::1.49
Weight sharing
RSPS
7587
84.161 69
87.
59.00:1:460
58.33-44.34
31,56++3.28
31.14=188
DARTS-VI
10890
39.77::0.00
54.30=0.00
15.03:00.00
15.61:00000
16.43:00000
16:32=00000
DARTS-V2
29902
39.77.1.000
54.30:10.00
15.03.1:0.00
15.61:00.00
16.43.10.00
16.32:10.00
GDAS
28926
90.00::0211
93.11
71.14::0.77
70.61::0.26
41,70 1,26
41.84:00900
SETN
31010
82.25:4-.17
86. 1.669-4-.6
56.86++7.59
56.87-47.77
32.5443366
31.90-:4.77
ENAS
13315
39.77:+0.00
54, 0..30=00000
15.03++0.00
15.61=+0.00
16.43+00.00
16.32:00.00
Training-free
NASWOT (I=10)
3.8
89.13 + 1,26
92.28 + 1.13
68.19 + 1,97
68.32 #: 1.99
39.11 + 4.39
38.80
4.73
NASWOT ()==100)
28.73
90.54 + 0.83
93.36 +: 0.72
70.15 + 1.37
70.31 1.58
39.60
2.98
39.21
3.23
NASWOT CIPAR10-search (000100)
43.67
1.73
43.74 + 1.81
NASWOT (0==0000)
429.2
90.97
93.75 + 0.32
70.85 + 1.02
71.09 0.96
Rondom
N/A
13.28
86.61 +: 13.46
60.70 + 12.55
60.83
33.34 + 9.39
Optimal (4-10)
N/A
93.06 + 0.59
69.61 + 1,21
69.76 1.25
43.11 +: 1,85
Optimal (1=100)
N/A
91.05 + 0.28
93.84 1: 0.23
71,45 +: 0.79
71.56 0.78
45.37
1: 0.61
45.67 1 0.64
REAL 1
12000
93.59 # 0.53
70.84 =: 1.41
44,90 + 1.16
AREAL
12000
93.80 +: 0.29
71.30 1.27
44.84 =: 1.05
5
ASSISTED REGULARISED EA - AREA
Our proposed score can also be incorporated into existing NAS algorithms. To demonstrate this we implemented variant of REA (Real et al., 2019), which we call Assisted-REA (AREA). REA starts with randomly-selectee population (in our experiments the population size is 10). AREA instead randomly-samples a larger population (in our experiments 1000) and uses our score to select the initial population for the REA algorithm. Pseudocode can be found in Appendix E. When implementing API the precise epoch accuracy used was not specified in Dong Yang 2020) for their REA results across all datasets. Therefore we opted to use 'ori-test@ @ 12 for this benchmark. We denote the algorithms REAL and AREAL (for Local implementations) to distinguish them from those using the settings in Dong & Yang (2020). Tables and 2 shows AREAL improves upon REAL in most cases across NAS-Bench: 101 and NAS 201-
AREA using the NAS- NAS-BBench-25
6 CONCLUSION
NAS has previously suffered from intractable search spaces and heavy search costs. Recent advances in producing tractable search spaces, through NAS benchmarks, have allowed us to investigate if such search costs can be avoided. In this work, we have shown that it is possible to run search algorithm- NASWOT-in matter of seconds, relying on simple, intuitive observations made on initialised neural networks, that challenges more expensive black box methods. We also demonstrate how our score can be combined into an existing NAS algorithm. We find our score-assisted algorithm- AREA-performs better than the original version on a number of benchmarks. This work is not without its limitations; our scope is restricted to convolutional architectures for image classification on benchmark search spaces. However, we hope that this will be powerful first step towards removing training from NAS and making architecture search cheaper, and more readily available to practitioners.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Andrew Brock, Theo Lim, J.M. Ritchie, and Nick Weston. SMASH: One-shot model architecture
search through hypernetworks. In International Conference on Learning Representations, 2018.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations, 2019.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv: 088,1,8777,8,, 2017.
Boyang Deng, Junjie Yan, and Dahua Lin. Peephole: Predicting network performance before training. arXiv preprint 1x1v::712.003552 2017.
Terrance Vries and Graham W Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint arXiv: 2017.
Xuanyi Dong. NAS-Bens Be-BBnch--21, NAS-Bench-2011
May 2020.
URL https://github. hww.atthu.ccoom/0. www.pow-mm-eoo..e
Xuanyi Dong and Yang. One-shot neural architecture search via self-evaluated template network. In Proceedings of the International Conference on Computer Vision, 2019a.
Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four gpu hours. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019b.
Xuanyi Dong and Yi Yang. Nas-hench-200 Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20155):1-21, 2019.
Stefan Falkner, Aaron Klein, and Frank Hutter. BOHB: Robust and efficient hyperparameter opti- mization at scale. International Conference on Machine Leurning, 2018.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2017.
Roxana Istrate, Florian Scheidegger, Giovanni Mariani, Dimitrios Nikolopoulos, Constantine Bekas, and Adelmo Cristiano Innocenza Malossi. Tapas: Train-less accuracy predictor for architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3927- 3934, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master's thesis, University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. ImageNet classification with deep convolu- tional neural networks. In Advances in Neural Information Processing Systems, 2012.
Liam Li and Ameet Talwalkar, Random search and reproducibility for neural architecture search. In Conference Uncertainty in Artificial Intelligence, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. In Advances in Neural Information Processing Systems, 2018.

---

Under review as a conference paper at ICLR 2021
Hieu Pham, Melody Y. Guan, Barret Zoph, Quoe V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning. 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet large scale visual recognition challenge. Int. Journal of Computer Visi-on (IJCV), 115(3); 211-252, 2015.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In International Conference on Learning Representations, 2015.
Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Rethinking the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
Mingxing Tan, Bo Chen, Ruoming Pang. Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe Le. MnasNet: Platform-awaee neural architecture search for mobile. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2019.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-255 1992.
Martin Wistuba, Ambrish Rawat, and Tejaswini Pedapati. survey on neural architecture search. arXiv preprint 1rXiv:1905.01399 2019.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. FBNet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, 2019.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. In International Conference Learning Representations, 2019.
Antoine Yang, Pedro M. Esperança, and Fabio M. Carlucci. Nas evaluation frustratingly hard, In International Conference on Learning Representations, 2020.
Chris Ying, Aaron Klein, Esteban Real, Eric Christiansen, Kevin Murphy, and Frank Hutter. Nas- sench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, 2019.
Kaicheng Yu, Christian Seiuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluat- ing the search phase of neural architecture search. In International Conference on Learning Representations, 2020.
Arber Zela, Julien Siems, and Frank Hutter. Nas-bench-Ishone Benchmarking and dissecting one-shot neural architecture search. In International Conference Learning Representations, 2020.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference Learning Representations, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shiens, and Quoc V. Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018
10

---

Under review as a conference paper at ICLR 2021
A HISTOGRAMS OF CORRELATIONS
[60.0%, 70.0%) [70.0% (0.0%) 90.0%)
> = 90.0%
-1
0 1 -11
O
0
1-1
(a) Additional NAS-Bench- 101 histograms.
O
-1
0
(b) Additional NAS- B--BBnhhh-21 histograms.
11

---

Under review as a conference paper at ICLR 2021
B NAS BENCHMARKS
B.1 NAS-BENCH-IE 101
In 101, the search space is restricted as follows: algorithms must search for an individual cell which will be repeatedly stacked into pre-defined skeleton, shown in Figure 6c] Each cell can be represented directed acyclic graph (DAG) with up to 9 nodes and up to 7 edges. Each node represents an operation, and each edge represents state. Operations can be chosen from: 3 x 3 convolution, 1 convolution, de-duplication, this search space contains 423,624 possible neural networks. These have been trained exhaustively, with three different initialisations, on the CIFAR- 10 dataset for 108 epochs.
max pool. An example this shown in Figure 6a After
B.2 NAS- NAS-BENCH-22 BL--BENCH-211
In NAS-Bench-200 networks also share a common skeleton (Figure 6c) that consists of stacks of its unique cell interleaved with fixed residual downsampling blocks. Each cell (Figure (bb) can be represented as densely-connected DAG of 4 ordered nodes (A, B, C, D) where node A is the input and node D is the output. In this graph, there is an edge connecting each node to all subsequent nodes (A > B, A C, A- D, B- C. B D, C-> D) for total perform one of 5 possible operations (Zeroise, Identity, 3 3 convolution, x convolution, 3 x 3 average pool). The search space consists every possible cell. As there are 6 edges, on which there may be one of 5 operations, this means that there are 56 15625 possible cells. This makes for a total of 15625 networks as each network uses just one of these cells repeatedly. The authors have manually split CIFAR-10, CIFAR- 100, and ImageNet- 16- 620 (Chrabaszez et al., (017)) into train/val/test, and provide full training results across all networks for (i) training on train, evaluation on val, and (ii) training on train/val, evaluation test. The split sizes are 25k/25k/10k for CIFAR-10. 50k/5k/5k for CIFAR- 100, and 151.7k/3k/38 for ImageNet-16-- 120 We obtained these datasets via
edges, and each edge can
the A---Bench-201 repository (Dong 2020).
out
zeroize
identity
identity
3x3
B
3x3
convixl
convaxe
mp
1xt
(b) NAS-Bench-200 cell.
Paanee Hanneay
(a) A NAS-Bench-100 101 cell.
(c) The skeleton for NAS-Bench- 101 and 201.
Figure 6: (a): An example cell from NAS-Bench-101, represented directed acyclic graph. The cell has an input node, an output node, and 5 intermediate nodes, each representing an operation and connected by edges. Cells can have at most 9 nodes and at most edges. NAS Bench- 101 contains 426k possible cells. By contrast, (b) shows a NAS Bench-201 (Dong & Yangl 2020) cell, which uses nodes as intermediate states and edges as operations. The cell consists of an input node (A), two intermediate nodes (B, C) and an output node (D). An edge e.g. A-> B performs operation on the state and adds to the state at B. Note that there are edges, and possible operations allowed for each of these. This gives total of 56 15625 possible cells. (c): Each cell is the constituent building block in an otherwise- fixed network skeleton (where N=5). As such, BAAS-Bench-We 201 contains 15625 architectures.
12

---

Under review as a conference paper at ICLR 2021
C
ABLATION FIGURES
CIFAR-10 images
Random images
50000
50000
40000
40000
30000
30000
score
score
20000
20000
10000
10000
0
0
1
2 3 4
5
6
7
8
0
2
3
4
5
6
7
8
Uninitialised network
Uninitialised network
Initialisations
Mini-batch size
0.6
40000
0.5
Normalised score
30000
0.4
Score
0.3
20000
0.2
10000
0.1
0.0
1
2
3
4 5 7
8
0
2
3
4 5 6
8
Uninitialised network
Uninitialised network
Figure 7: Effect of different CIFAR-I0 image (top-left), initialisation (bottom-left), random input images (top-right), and mini-batch sizes (bottom-right) for 9 randomly selected NAS-Bench-201 architectures (one in each 10% percentile range from 10-20, .... 90-100). Random input data are normally distributed. For each network 10 samples were taken for each ablation, using a mini-batee size of 256, except for mini-batch size for which mini-batch sizes of 32, 64, 128, 256, and 512 were used. There is less variance score when using different random input images as opposed to different CIFAR- 10 images.
13

---

Under review as a conference paper at ICLR 2021
CIFAR-10 images Kendall == 0.472
Random images Kendall T= 0.428
50000
40000
40000
B
Score
30000
score
20000
20000
10000
85
80
85 Uninitialised network
Uninitialised network
Initialisations
Kendall T = 0.453
40000
score
20000
80
85
Uninitialised network
Figure 8: Further ablation showing the effect of different CIFAR-10 image (top-left), initialisation (bottom-left), random input images (top-right). and mini-batch sizes (bottom-right) for 100 randomly selected NAS-Bench- Bench-201 architectures in the 80% + CIFAR-10 10 accuracy range when using cutout as the augmentation method when calculating the score. For each network 20 samples were taken for each ablation.
14

---

Under review as a conference paper at ICLR 2021
CIFAR-10 images Kendall T= 0.305
Random images
Kendall T= 0.291
60000
60000
40000
40000
score
score
20000
20000
80
85
85 Uninitialised network
Uninitialised network
Initialisations
Kendall T= 003199
60000
40000
score
20000
80
80
85
Uninitialised network
Figure 9: Further ablation showing the effect of different CIFAR-10 image (top-left), initialisation (bottom-left), random input images (top-right). and mini-batch sizes (bottom-right) for 100 randomly selected BeSShhnh--21 architectures in the 80% CIFAR-10 10 accuracy range when using additive Gaussian noise the augmentation method when calculating the score. For each network 20 samples were taken for each ablation.
15

---

Under review as a conference paper at ICLR 2021
D SEARCH TIME COMPARISON
CIFAR-10 (test)
BOHB REINFORCE
GDAS SETN
90
Ours (N=100)
RS
REA
RSPS
% acc
80
70
60
DARTS-V1
ENAS
DARTS-V2
O
5000
10000 15000
20000 25000 30000
Search time (s)
Figure 10: Visualising the tradeoff between search time and accuracy on CIFAR-10 (test) for different NAS algorithms on accurate networks in seconds instead of hours.
By removing the need for training, method is able find
E AREA ALGORITHM
Algorithm 3 Assisted Regularised EA AREA
population []
generator = RandomGenerator()
for i=1:M do
net generaatoo..eeeeeteee
scored_net = net.score()
population.append(ccorre net)
Keep the top N scored networks in the population
history= =
for net in popul ition on do
trained net = net.train()
history.ppenndtrainee..eg
while time limit not exceeded do
Sample sub-population, S, without replacement from population
Select network in S with highest accuracy as parent
Mutate parent network to produce child
Train child network
Remove oldest network from population population.appemit achend(child network)
history, appendd network)
chosen_net = Network in history with highest accuracy
16

---

Under review as a conference paper at ICLR 2021
F VARYING INITIALISATIONS
In Figure 11 we examine the effect of different initialisation functions on the efficacy of our score. We find that the scoring function is robust many different intialisation strategies, though it fails for Uniform (0, 1) initialisation. In Figure 12 we confirm that this effect similar when the score is aggregated over multiple re-initialisations of the network.
MAS-Bench-201 cifar10
Orthogonal-Saxe Kendall 0.446
Normal(O,
Kendall 0.267
6.0E+4
6.0E
5.0E+
4.0E
4.0E++4
Score
3.0E+4
Score
2-0E+4
2.0E++
1.0++4
0E+0
0E+0
Test accuracy
Test accuracy
NAS-B Bench-201 cifar10
Uniform(-L, 1) Kendall 0.294
Uniform(o, Kendall -0.096
6.0E +-4
6.0E
5
4.0E
Score
4
2.0E+4-
+
0E+0
90
Test accuracy
Test accuracy
NAS-Bench-200 cifar10
NAS- AAS-Bench-201
cifar10
XavierUniform(ReLL) Kendall 0.354
NavierNomal((eeLU
Kendall 0.336
6.0E
6.0E
4-0E
5.0E
4.0E+4
4.0E+4
Score
3.0E+4
Score
3.0E+4
2.0E+4
2.0E+4
1.0E+4
0E+0
0E+0
90
Test accuracy
Test accuracy
Figure 11: Plots of association between score and final CIFAR-10 validation accuracy for various initialisation strategies.
17

---

Under review as a conference paper at ICLR 2021
NAS-Bench-201 cifar10
Orthogonal-Saxe
Kendall = 0.463
Normal(o, 1) Kendall 0.307
6.0E+4
5.0E+4
5.0E+4
4.0E+4
4.0E+4
3.0E+4
Score
3.0E+4
2.0E+4
2.0E+4
1.0E+4
1.0E+4
DE+0
0E+0
Test accuracy
Test accuracy
NAS-Bench-201 cifar10 Uniform(-1, Kendall 0.324
Uniform(0, Kendall -0.110
6.0E+4
6.0E+4
5.0E+4
5.0E+4
1.0E+4
4,0E+4
Score
3.0E+4
2.0E+4
2.0E+4
1.0E+4
1.0E+4
DE+0
0E+0
Test accuracy
Test accuracy
NAS-Bench-201 cifar10
XavierUniform(ReeL) Kendall 0.373
XavierNormal(RcL)
Kendall 0.356
6.0E+4
6.0E+4
5.0E+4
5.0E+4
4.0E+4
4.0E+4
3.0E+4
Score
3.0E+4
2.0E++
2.05+4
1.0E+4
1.E++4
0E+0
0E+0
50
80
90
50
80
90
Test accuraty
Test accuracy
Figure 12: Plots of association between aggregated score and final CIFAR-10 validation accuracy for various initialisation strategies. The aggregated score is the maximum score of 10 independent initialisations of the same architecture.
18

---

Under review as a conference paper at ICLR 2021
G VARYING B
The scoring mechanism introduced in Section relles on cutoff value 3 that decides which portion of the histogram of correlations we look Given that our goal is assign high scores histograms with a small positive skew, we set the default value of 3 = 0.25. In Figure 13 we investigate different values of 3. reporting the CIFAR-10 10 test accuracy for networks NAS- Bench-101 101 and NAS- MAS-Bench--21.
We linearly sample five values of 3 between 0.025 and 1 and report mean accuracy over 500 runs. We also show the standard deviation in accuracy for each 3 in the shaded area. The figure shows that both benchmarks, the scoring mechanism reasonably robust different choices 3, but deteriorates at very large values.
NAS-Bench-101 CIFAR-10 (test)
NAS-Bench-201 CIFAR-10 (test)
95
94
92
90
% acc
% acc
90
85
88
86
N=100
N=100
75
Random
Random
84
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Value of beta (B)
Value of beta (B)
Figure 13: Controlling for different values of 3 in the scoring function. Points are shown as the mean value over 500 runs, with the standard deviation shown in the shaded areas.
19

---

Under review as a conference paper at ICLR 2021
H SCORE BY EPOCH
We evaluated the score during training and plotted the trajectory of the score for 100 networks for NAS-Bench-20) trained using the CIFAR-I0 dataset in Figure
40000
Score
20000
0
20
40
60
80
100
Epoch
Epoch 0
Epoch 25
Epach 50
Epoch 75
Epoch 99
Kendall-T 0.606 Kendall-r 0.580 Kendall-T 0.562 Kendall-T 0.574 Kendall-T 0.569
40000
Score
20000
0
50
80
90
50
80
90
50
80
90
50
80
90
50
80 90 Final CIFAR-10
Final CIFAR-10
Final CIFAR-10 Validation Accuracy
Final CIFAR-10 Validation Accuracy
Final CIFAR-10 Validation Accuracy
Validation Accuracy
Validation Accuracy
Figure 14: (top) A plot of score trajectories during training for 20 networks in NAS-Bench-201. (bottom) Plots of final CIFAR-10 Validation accuracy compared to score for 125 networks for epoch 0, 25, 50, 75, and 99. The correlation between score and final test accuracy reduces marginally with training epoch but association between the two quantities remains.
20

---

Under review as a conference paper at ICLR 2021
I AUGMENTING WITH GAUSSIAN NOISE AND COLOUR JITTER
NAS-Bench-201 cifar10
NAS-Bench-20D cifar10
Pytorch default
Kendall 0.347
Pytorch default
Kendall 0.511
6.0E+4
6.0E+44
5.0E+4
+.
4.0E+4
4.0E 4-4
Score
3.0E+4
3.0E+4
2-0E+4
2.0E+4
1.0E+4
1.0E+4
0E+0
50
50
90
Test accuracy
Test accuracy
Figure 15: Plots CIFAR-10 final accuracy against score for alternative augmentation types: (left) Additive gaussian noise N(0, 0.01), (right) colour jitter.
J
FURTHER RANDOM IMAGE EXPERIMENTS
We ran further evaluations of the score for random images for 6 seeds. These shown in Figure [6
21

---

Under review as a conference paper at ICLR 2021
NAS-Bench-201 cifar10
Pytorch default
Kendall T= 0.499
Pytorch default
Kendall t= 0.477
6.0E+4
5.0E+4
5.0E+4
4.0E++4
4,0E++
Score
3.0E+4
3.0E+4
2.0E+4
1.0++4
1.0E+4
DE+0
0E+0
50
50
80
90
Test accuracy
Test accuracy
NAS-Bench-201 cifar10
Pytorch default
Kendall r 0.479
Pytorch default
Kendall T 0.489
6.0E+4
5,0E+4
5.0E+4
1.0E+4
1.0E+4
Score
3,0E+4
3.0E+4
2.0E+4
1.0++4
1.0E+4
0E+0
0E+0
50
90
Test accuracy
Test accuracy
NAS-Bench-201 cifar10
6.0E+4
Pytorch default
Kendall == 0.506
Pytorch default
Kendall == 0.478
6.0E+4
5.0E+4
5.0E++
4.0E+4
4.0E+4
Score
3.0E+4
2.0E+4
2.0E+4
1.0++4
1.E+4
0E+0
0E+0
50
8D
90
accuracy
Test accuracy
Figure 16: Plots of association between score and final CIFAR-10 validation accuracy for seeds using random images (generated via torchvision FakeData).
22


Reviews:
[{"review_id": "hqd5t_dj1Jp", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "** Summary\n\nThe paper mainly introduces a metric to benchmark the performance of neural networks without training – the correlation of Jacobian subject to different augmented versions of a single image. The key motivation is, high-performance networks tend to represent data of small perturbations with different hyperplanes at initialization, so that the distinguishing capability may also be stronger. The divergence of the hyperplanes can be efficiently estimated via the correlation of the Jacobian, thus quantified by the score in Eq. 2. The effectiveness of the proposed metric is mainly verified in two NAS benchmarks (NAS-Bench-101 and NAS-Bench-201), whose correlation to the actual accuracy is relatively significant (Fig 3). Compared with existing NAS frameworks, the proposed method is very efficient, moreover, able to obtain competitive performance.\n\n** Pros\n\nI really appreciate the paper proposes a new direction to benchmark and understand neural networks. The motivation is very impressive. Previous NAS frameworks based on score predictors, e.g. NAO [*1] and ChamNet [*2], have shown that it is possible to directly predict the performance from the architecture embeddings without training, however, the underlaying mechanism is not clear. The proposed metric may help to uncover the relation between architecture choices and the performances. Furthermore, with the help of the metric, the proposed NAS framework (NASWOT) is elegant and seems to be effective, which could be useful in practice.\n\n** Cons\n\n1)\tLack of theoretical evidence to support the intuition of the proposed method. To my knowledge, network initialization is important but cannot interpret all the behaviors; so, I still doubt why and how the Jacobian at initialization reflects the final score. I guess [*3] may help in the analysis. \n2)\tSome important ablations are missing in the experiments, which makes the method less convincing. Please refer to the following suggestions. \n\n** Concerns and suggestions\n\nMajor:\n\nTo my understanding, the methodology of initialization (such as identity init, random gaussian with fixed variance (e.g. 0.01), MSRA init. [*4], etc.) could affect the initial Jacobian a lot, but little on the final accuracy especially with BN, which is not compared in the paper (I suppose the comparison in Fig 7 (bottom-left) is performed with different runs rather than different initialization methods, please correct me if I make some misunderstandings). Notice that some initialization methods like [*4] may leak architecture parameters (e.g. number of input channels). I think it is very important to check whether the Jacobian under a certain initialization methodology (improperly) takes advantage of the architecture bias in NAS benchmarks. I am pleased to raise the rating if the authors clear my concern, for example, providing comparisons of different initialization methods, or benchmarking the method with different search spaces on large datasets (e.g. search space of FBNet [*5] on ImageNet). \n\nMinor:\n\n1)\tIt is interesting if the authors analyze or visualize (just like Fig 1) how the correlation of Jacobian evolves during the training for different architectures. \n2)\tPlease clarify the details about “… adjust the final classifier layer to output a scalar” in Page 4. \n\n[*1] Luo, Renqian, et al. \"Neural architecture optimization.\" Advances in neural information processing systems. 2018.\n\n[*2] Dai, Xiaoliang, et al. \"Chamnet: Towards efficient network design through platform-aware model adaptation.\" Proceedings of the IEEE Conference on computer vision and pattern recognition. 2019.\n\n[*3] Jacot, Arthur, Franck Gabriel, and Clément Hongler. \"Neural tangent kernel: Convergence and generalization in neural networks.\" Advances in neural information processing systems. 2018.\n\n[*4] He, Kaiming, et al. \"Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.\" Proceedings of the IEEE international conference on computer vision. 2015.\n\n[*5] Wu, Bichen, et al. \"Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search.\" Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2019.\n\n===================\n\nThanks for the rebuttal and the additional empirical results. In general, I really appreciate the \"brave new idea\" proposed by the authors, which could inspire new insights on neural architecture design.  However, my major concern still exists: the proposed metric seems to be sensitive to the choice of initialization functions. For example, uniform initialization [0, 1] seems not work at all but no further explanations, which may indicate the proposed method may work in a different way (e.g. taking advantage of some search space's bias).  So, I keep my original rating. \n  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "8cb-qlgG7YQ", "reviewer": "AnonReviewer1", "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": "Summary:\nThe authors propose a training-free way of estimating the performance of a deep net architecture after training using correlations between linearizations of the network at initialization for different augmentations of the same image. This estimate is used as signal to construct NAS algorithms that do not require training deep nets and is evaluated on two datasets. Although I have significant concerns about the practicality of the method, I believe it establishes a sufficiently distinct direction for NAS research that could merit acceptance.\n\nStrengths:\n1. To my knowledge the paper is the first to implement training-free NAS. \n2. The method is simple and easy to implement.\n3. The method achieves decent performance on CIFAR in dramatically less time than previous approaches.\n4. What seems like a complete codebase is provided (although see Question 1 below).\n5. The paper is clear and easy-to-follow.\n\nWeaknesses:\n1. The justification for the actual score used is weak (see Questions 2-3 below).\n2. The method seems limited to vision data and networks with ReLU activations.\n3. Performance on the ImageNet subset of NAS-Bench-201, the only evaluation using non-CIFAR data, is poor.\n4. Limited exploratory and benchmark evaluations (see Questions 4-7 below).\n\nQuestions:\n1. I was not able to run the provided code (search.py) using the instructions provided; could the authors provide a dependency list?\n2. As the score used is non-obvious and has no mathematical basis, it seems likely some trial-and-error was used to find it; is this the case, and if so what sorts of rules were tried that did not work.\n3. Why not just use the correlations between gradients rather than using the indicator function to obtain some linearization?\n4. What is the effect of beta on performance? \n5. Do other types of data augmentation work?\n6. For NAS-Bench-201, why was N>100 (e.g. N=1000) not tried? There is clearly room to improve and going that high still leaves the NASWOT algorithm by far the fastest. \n7. How does NASWOT perform on larger search spaces such as DARTS (Liu et al., 2019)?\n\nNotes:\n1. In two locations in the paper (3rd para of intro, 3rd para of background) the authors suggest that Li & Talwalkar (2019) show that WS inhibits architecture search and/or struggles against random search; however, that paper also shows that combining WS with random search is outperforms the latter.\n2. “Moreover, popular search spaces have been shown to be over-engineered, exhibiting little variety in their trained networks (Yang et al., 2020).” - is there evidence that NAS-Bench-101 and NAS-Bench-201 do not also suffer from this? Both were released before the publication of Yang et al. (2020).\n3. “Given a neural network with rectified linear units, we can, at each unit in each layer, identify a binary indicator as to whether the unit is inactive (the value is negative and hence is multiplied by zero) or active (in which case its value is multiplied by one).” - is the proposed method dependent on ReLU activations being used?\n4. Figure 4: what is the small circle that appears either above or below many of the box-and-whisker points?\n5. Table 2: it is standard to report the optimal in the entire search space, not just for N=10/100.\n\n# Post-response update\nThank you to the authors for very helpful clarifications. This paper provides a reasonable start for a new potential direction in NAS research and so may be worth presenting at the conference, but the justification and applicability of the method is somewhat limited. I therefore stand by my original assessment.", "extra_scores": {}, "extra_text": {}}, {"review_id": "3QVLB97mDI4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "### Summary\nThis paper proposes a zero-shot NAS algorithm.  Instead of using validation accuracy that requires training, a score **S** is defined. It is computed as follows:\n    A single image is augmented using cut-out several times to produce a batch of images. For every datapoint, the Jacobian is computed to form a vector J. Then the correlation matrix $\\Sigma$ for the J is computed. Score S is the total number of entries in $\\Sigma$ between 0 and upper bound $\\beta$. $\\beta$ is a hyper parameter.\nThe search algorithm **NASWOT** now randomly samples K networks from the search space and finds the network with the highest score **S**. \n\n###Pros:\n  The idea of using a metric based on Jacobian rather than validation accuracy is interesting. \n   Their experimental setup demonstrated the correlation between ranking based on S and validation accuracy, NAS on 3 datasets on NASBENCH-201\n\n###Questions\n\n 1. Main concern is that as the method relies on only 1 image and the initialization, what is the guarantee that it would generalize.  In Figure 4, the ablation study considers networks from different accuracy buckets. The Standard deviation of the score is high for some networks.  What would be more useful is if around 200 networks were sampled from 80 to 100 accuracy bucket, for each of the 20 images (instead of 10), we compute the Kendall Tau of the ranking based on **S** and validation accuracy. You can report the average Kendall Tau. Similar experiment can be performed for initialization too.\n \n2. How will this method account for the fact that some datasets have very diverse images? For example, NASWOT deteriorates in performance on Imagenet which has more diverse images. Kendall Tau computed on ImageNet in Figure 3 also reflects the same. Instead of 1 image, can we sample 10 representative images from the distributed and compute average of S on all of them?\n\n3.  In their paper, Real et al. use an initial population of 100. 10 might be too less for initial population. So the comparison of REAL vs AREAL might not be fair. Even in that case, the performance improvement is not significant.\n\n4. In figure 3, why is the correlation not higher than 0.55? Does this mean that while it has some signal, it is not enough to discriminate well performing networks from others?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0Nh6y3BICBk", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThis paper attempts to infer a network's accuracy at initialization without training it, which can speed up neural architecture search and greatly reduce the search cost. Specifically, they propose a metric based on the Jacobian of the loss with respect to a minibatch of input data. The authors show that with this metric, they can find architectures with reasonable accuracy on CIFAR-10/CIFAR-100 in the NAS-Bench-201, while using much less search cost compared to previous NAS methods.\n\n\n\n# Strong points\n1. This paper is exploring a novel and interesting direction. Estimating the network’s performance at initialization can greatly reduce the search speed.\n2. It might be difficult for the training-free metric to outperform conventional metrics (e.g., validation accuracy after training). This paper finds a good use case of the training-free metric in practice. The authors propose to use the training-free metric to select the initial population of evolutionary algorithms and empirically demonstrate its usefulness on CIFAR-10 and CIFAR-100.\n\n\n# Weak points\n1. It will be helpful to make the motivation of the proposed metric more clear. I found the second paragraph in Section 3 hard to understand without digging into the cited literature.\n\n2. How to interpret the value in the correlation matrix \\Sigma? Empirically, Figure 1 shows that we want to find an architecture whose values in matrix \\Sigma are mostly around zero with a small positive skew. But how does this relate to the two motivations mentioned in Section 3: (1) being flexible and (2) being invariant/robust to small perturbations. Does small value mean less or more flexible/robust? This is important for people to understand why the metric works.\n\n3. In the experiments, all the images in the minibatch are data augmentations of the same image. This seems to be an important design choice. More insights on this part would be very helpful. How is this design choice (using data augmentations of the *SAME* image) related to the two motivations (flexible & invariant)? \n\n4. As mentioned by the authors, the two motivations are actually antagonistic. How does the proposed method balance them?\n\n5. Why choose cutout as the data augmentation strategy? Is the method sensitive or not to other perturbations, e.g., adding small noise?\n\n6. I notice that the correlation (tau) value in Figure 3 is not high. What is the correlation between the typical criteria (e.g., validation accuracy after training a small number of epochs) and the final test accuracy?\n\n  The tau in Figure 3 is actually undefined. Is that Kendall tau?\n\n  Why evaluate the correlation between **validation** accuracy, not the final **test** accuracy, as provided in NAS-Bench-201?\n\n7. Section 5 mentions that “ori-test@12” is used as the metric during search. Is that the accuracy on the **test** set after 12 epoch training (with learning rate decay to 0)? But the common practice is to use the **validation** accuracy during search and report the final test accuracy. This seems to be unfair.\n\n8. For NASWOT (N=100), the accuracy on CIFAR-10 is reasonable and actually pretty good considering the small search cost. However, the accuracy in ImageNet-16-120 seems to be very low. Why does this happen? Is it possible that the proposed method overfit to CIFAR-10?\n\n  If I understand correctly, the architecture is searched on CIFAR-10, and then evaluated on all three datasets. What if we search on ImageNet-16-120 with this metric and can we match the performance of other baselines on ImageNet-16-120? This might be an unfair comparison, but will be important for people to know whether the proposed method/metric can generalize to different datasets.\n\n9. Table 2 only reports N=10 and N=100. What if we significantly increase the value of N and will the performance be similar or better than other methods like RS and REINFORCE? As the proposed method uses very small cost, even using a large N, the cost would still be reasonable. It will be great to see we can achieve much better performance when increasing N.\n\n10. The writing and organization in Section 4 need to be improved. Adding subtitles might make it easier to read. Also, Section 4 mentions REAL at the beginning but REAL is not explained in detail until Section 5. The rows “Optimal (N=10/100)” don’t seem to help validate the proposed method and are a bit confusing.\n\n11. It will also greatly strengthen this work if the authors can show the effectiveness of the proposed metric on a more realistic search space, e.g., the DARTS search, and evaluate the found architecture on a larger dataset, e.g., ImageNet.\n\n# Justification of rating\nI like the idea of estimating a network’s performance without training it. But this paper needs more refinement before being accepted. As mentioned above, the motivation, and the relationship between the method and motivation, need to be explained more clearly. More analysis is needed to understand and justify the proposed method. The writing also needs improvement.\n\n# After rebuttal\nI would like to thank the authors for the hard work during the rebuttal. The ablation study of the data augmentation strategy and other added results are very helpful. Regarding the explanation of the flexibility and invariance, although I could get some intuition, I am still not fully convinced. So I keep my original rating. One possible way to make this work stronger and meet the acceptance criteria is to provide some empirical (or even better, theoretical) analysis of the influence of $\\Sigma$ on the flexibility and invariance of a network.\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an interesting new direction for low-cost NAS. However, the paper is not quite ready for acceptance in its current form. The main area of improvement is around the generalizability of the score presented, both empirically and (ideally) theoretically. The two main directions of generalizability that would be worth investigating are 1) different image datasets (see comments around Imagenet-16) 2) different/larger search spaces. Even simple search spaces consisting of a few architectural modification starting from standard architectures (e.g. resnets) would go a long way in convincing the community that the proposed method generalizes past NasBench.
Decision: Reject