Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective
Authors: Wuyang Chen
Xinyu Gong
Zhangyang Wang
Venue: ICLR 2021 Poster (2021)
Keywords: Neural Architecture Search
neural tangent kernel
number of linear regions

Abstract: Neural Architecture Search (NAS) has been explosively studied to automate the discovery of top-performer neural networks. Current works require heavy training of supernet or intensive architecture evaluations, thus suffering from heavy resource consumption and often incurring search bias due to truncated training or approximations. Can we select the best neural architectures without involving any training and eliminate a drastic portion of the search cost? 

We provide an affirmative answer, by proposing a novel framework called \textit{training-free neural architecture search} ($\textbf{TE-NAS}$). TE-NAS ranks architectures by analyzing the spectrum of the neural tangent kernel (NTK), and the number of linear regions in the input space. Both are motivated by recent theory advances in deep networks, and can be computed without any training. We show that: (1) these two measurements imply the $\textit{trainability}$ and $\textit{expressivity}$ of a neural network; and (2) they strongly correlate with the network's actual test accuracy. Further on, we design a pruning-based NAS mechanism to achieve a more flexible and superior trade-off between the trainability and expressivity during the search. In NAS-Bench-201 and DARTS search spaces, TE-NAS completes high-quality search but only costs $\textbf{0.5}$ and $\textbf{4}$ GPU hours with one 1080Ti on CIFAR-10 and ImageNet, respectively. We hope our work to inspire more attempts in bridging between the theoretic findings of deep networks and practical impacts in real NAS applications.

Published as a conference paper at ICLR 2021
NEURAL ARCHITECTURE SEARCH ON IMAGENET IN FOUR GPU HOURS:
A THEORETICALLY INSPIRED PERSPECTIVE
Wuyang Chen, Xinyu Gong, Zhangyang Wang
Department of Electrical and Computer Engineering The University of Texas at Austin, Austin, TX. USA (wuyang. chen, xinyu. gong, at @wang)
ABSTRACT
Neural Architecture Search (NAS) has been explosively studied to automate the discovery of top-performer neural networks. Current works require heavy train- ing of supernet or intensive architecture evaluations, thus suffering from heavy resource consumption and often incurring search bias due to truncated training or approximations. Can we select the best neural architectures without involving any training and eliminate a drastic portion of the search cost? We provide an affirmative answer, by proposing a novel framework called training-free neural architecture search (TE-NAS). TE-NAS ranks architectures by analyzing the spec- trum the neural tangent kernel (NTK) and the number of linear regions in the input space. Both are motivated by recent theory advances in deep networks and can be computed without any training and any label. We show that: (1) these measurements imply the trainability and expressivity of neural network; (2) they strongly correlate with the network's 's test accuracy. Further on, we design a pruning-based NAS mechanism achieve a more flexible and superior trade-off between the trainability and expressivity during the search. In NAS-Bench-20) and DARTS search spaces, TE-NAS completes high-quality search but only costs 0.5 and 4 GPU hours with one 1080Ti on CIFAR- 10 and ImageNet, respectively. We hope our work inspires more attempts in bridging the theoretical findings of deep networks and practical impacts in real NAS applications. Code is available at: https:/ /tte:///gttttuttu com / /ttp://cc/////TT---O///////AOA
INTRODUCTION
The recent development of deep networks significantly contributes to the success of computer vision. Thanks many efforts by human designers, the performance of deep networks have been significantly
boosted (Krizhessky et al., 2012, Simonyan Zisserman, 2014 Szegedy et al. 2013 He et al., 2016 Xie et al. 2017). However, the manual creation of network architectures not only costs enormous time and resources due to trial-and -erero,, always scale up. To reduce the human efforts and costs, neural architecture search (NAS) has recently amassed explosive interests, leading to principled and automated discovery for good architectures in given search space of candidates (Zoph & Le 2016 Brock al. 2017 Pham et 2018 Liu et al. 2018a Chen et al. 2018; Bender et al. 2018 Gong et al. 2019 Chen et al. 2020a Fu et al. 2020).
error, but also depends on the design experience that does not
As an optimization problem, NAS faces core questions: "how to evaluate". i.e. the objective function that defines what are good architectures we want; 2) "how to optimize", i.e. by what means we could effectively optimize the objective function. These two questions are entangled and highly toiiirivial, since the search spaces are of extremely high dimension, and the generalization ability of architectures cannot be easily inferred (Dong Yang 2020 Dong et al. 2020). Existing NAS methods mainly leverage the validation set and conduct accuracy-driver architecture optimization. They either formulate the search space as a super-network ("supernet") and make the training loss differentiable through the architecture parameters (Liu al. 2018b), or treat the architecture selection as a sequential decision making process (Zoph & Le 2016) or evolution of genetics (Real et al. 2019). However, these NAS algorithms suffer from heavy consumption of both time and GPU resources. Training supernet till convergence is extremely slow, even with many effective heuristics for sampling channel approximations (Dong & Yang 2019 Xu et al. 2019). Approximated proxy

---

Published as a conference paper at ICLR 2021
inference such as truncated training/early stopping can accelerate the search, but is well known to introduce search bias to the inaccurate results obtained (Pham et al., 2018 Liang et al.) 2019 Tan
et al. 2020). The heavy search cost not only slows down the discovery of novel architectures, but also blocks us from more meaningfully understanding the NAS behaviors.
On the other hand, the analysis of neural network's trainability (how effective network can be optimized via gradient descent) and expressivity (how complex the function a network can represent) has witnessed exciting development recently in the deep learning theory fields. By formulating neural networks as a Gaussian Process (no training involved), the gradient descent training dynamics can be characterized by the Neural Tangent Kernel (NTK) of infinite (Lee al. 2019) or finite (Yang) (019) width networks, from which several useful measures can be derived to depict the network trainability at the initialization. [Hanin Rolnick (2019a b); Xiong et al. (2020) describe another measure of network expressivity, also without any training, by counting the number of unique linear regions that a neural network can divide in its input space. We are therefore inspired to ask:
How to optimize NAS at network's 's initialization without involving any training, thus significantly eliminating a heavy portion of the search cost?
Can we define how to evaluate in NAS by analyzing the trainability and expressivity of architectures, and further benefit our understanding of the search process?
Our answers are yes to both questions. In this work, we propose TE-NAS, a framework for training- free neural architecture search. We leverage two indicators, the condition number of NTK and the number of linear regions, that can decouple and effectively characterize the trainability and expressivity of architectures respectively in complex NAS search spaces. Most importantly, these two indicators can be measured in a training-free and label-free manner, thus largely accelerates the NAS search process and benefits the understanding of discovered architectures. To our best knowledge, TE-NAS makes the first attempt to bridge the theoretical findings of deep neural networks and real-world NAS applications. While we intend not claim that the two indicators we use are the only nor the best options, we hope our work opens door to theoretically-inge -inssiire NAS and inspires the discovery of more deep network indicators. Our contributions are summarized as below:
We identify and investigate two training-free and label-free indicators to rank the quality of deep architectures: the spectrum of their NTKs, and the number of linear regions in their input space. Our study finds that they reliably indicate the trainability and expressivity of a deep network respectively, and are strongly correlated with the network's 's test accuracy.
We leverage the above two serretccally-inspree indicators to establish training-free free NAS framework, TE-NAS, therefore eliminating a drastic portion of the search cost. We further introduce pruning-basee mechanism, to boost search efficiency and to more flexibly trade-off between trainability and expressivity.
In Bew---eennnnnrrr---- 201//ARTS search spaces, TE-NAS discovers architectures with a strong perfor- mance at remarkably lower search costs, compared to previous efforts. With just one 1080Ti, it only costs 0.5 GPU hours to search on CIFAR10, and 4 GPU hours on ImageNet, respectively, setting the new record for ultra-efficient yet high-quality NAS.
2 RELATED WORKS
Neural architecture search (NAS) is recently proposed to accelerate the principled and automated discovery of high-perffrmance networks. However, most works suffer from heavy search cost, for both weight-sharing based methods (Liu et al. 2018b; Dong & Yang 2019 Liu et al. 2019 Yu
et al.
2020a Li et al., 2020a Yang et al. 2020a) and single-path sampling based methods (Pham
al.
2018 Guo et al. 2019
al. 2019 Tan et al., 2020; Li al. 2020c Yang al.) 2020b).
A one-shot super network can share its parameters to sampled sub-networks and accelerate the architecture evaluations, but it very heavy and hard to optimize and suffers from poor correlation between its accuracy and those of the sub-networks (Yu et al.) (020c). Sampling-bast baasedg methods achieve more accurate architecture evaluations, but their truncated training still imposes bias to the performance ranking since this is based on the results of early training stages.
Instead of estimating architecture performance by direct training, people also try to predict network's s accuracy (or ranking), called predictor based NAS methods (Liu et al. 2018a Luo et al. 2018; Dai et al. 2019; Luo et al. 2020). Graph neural network (GNN) is a popular choice as the predictor model (Wen et al. 2019 Chen al. 2020b). Siems et al. (2020) even propose the first large-scale
2

---

Published as a conference paper at ICLR 2021
surrogate benchmark, where most of the architectures' accuracies predicted by pretrained GNN predictor. The learned predictor can achieve highly accurate performance evaluation. However, the data collection step sampling representative architectures and train them till converge still requires extremely high cost. People have to sample and train 2,000 to 50,000 architectures to serve as the training data for the predictor. Moreover, none of these works can demonstrate the eross-space transferability of their predictors. This means one has to repeat the data collection and predictor training whenever facing an unseen search space, which is highly nonscalable.
The heavy cost of architecture evaluation hinders the understanding of the NAS search process. Re- cent pioneer works like Shu al. (2019) observed that DARTS and ENAS tend to favor architectures with wide and shallow cell structures due to their smooth loss landscape. (Siems et al. (2020) studied the distribution of test error for different cell depths and numbers of parameter-free operators. Chen & Hsieh (2020) for the first time regularizes the Hessian norm of the validation loss and visualizes the smoother loss landscape of the supernet. [Li et al. (2020b) proposed approximate the validation loss landscape by learning mapping from neural architectures to their corresponding validate losses. Still, these analyses cannot be directly leveraged to guide the design of network architectures.
Mellor et al. (2020) recently proposed a NAS framework that does not involve training, which shares the same motivation with us towards training-free -ree architecture search at initialization. They empirically find that the correlation between sample- wise input-output Jacobian can indicate the architecture's 's test performance. However, why does the Jacobian work is not well explained and demonstrated. Their search performance on NAS- -0S-Bench-201 is still left behind by the state-of-the-art NAS works, and they did not extend to DARTs space.
Meanwhile, we see the evolving development of deep learning theory on neural networks. NTK (neural tangent kernel) is proposed to characterize the gradient descent training dynamics of infinite wide (Jacot et al. 2018) or finite wide deep networks (Hanin & Nica 2019). Wide networks are also proved to evolve as linear models under gradient descent (Lee et al.. 2019). This is further leveraged to decouple the trainability and generalization networks (Xiao et al. 2019). Besides, natural measure of ReLU network's expressivity is the number of linear regions it can separate in its input space (Raghu al., 2017] Montúfar 2017 [Seraa al., 2018 Hanin Rolnick 2019a [b) Xiong al.] (2020). In our work, we for the first time discover two important indicators that can effectively rank architectures, thus bridging the theoretic findings and real-world NAS applications. Instead of claiming the two indicators discover the best, we believe there more meaningful properties of deep networks that can benefit the architecture search process. We leave them as open questions and encourage the community study.
3 METHODS
The core motivation of our TE-NAS framework is to achieve architecture evaluation without involving any training, significantly accelerate the NAS search process and reduce the search cost. In section 3.1 we present our study on two important indicators that reflect the trainability and expressivity of neural network, and in section we design a novel pruning- based method that can achieve superior trade-off between the two indicators.
3.1 ANALYZING TRAINABILITY AND EXPRESSIVITY OF DEEP NETWORKS
Trainability and expressivity are distinct notions regarding neural network (Xiao et al. 2019). A network can achieve high performance only if the function it can represent is complex enough and at the same time, it can be effectively trained by gradient descent.
3.1.1 TRAINABILITY BY CONDITION NUMBER OF NTK
The trainability of a neural network indicates how effective it can be optimized using gradient descent (Burkholz & Dubatovkal 2019 Hayou et al. 2019 Shin & Karniadakis 2020). Although some heavy networks can theoretically represent complex functions, they not necessarily can be effectively trained by gradient descent. One typical example is that, even with a much more number of parameters, Vgg networks (Simonyan & Zisserman 2014) usually perform worse and require more special engineering tricks compared with ResNet family (He et al. 2016),, whose superior trainability property is studied by Yang & Schoenholz (2017).
3

---

Published as a conference paper at ICLR 2021
Recent work (Jacot et al. 2018 Lee et al. 2019 Chizat et al. 2019) studied the gradient descent training of neural networks using a quantity called the neural tangent kernel (NTK). The finite width NTK is defined by Ó(xr, x²) = (ax) [az)²² where Jia (2:) = de 2 (a:) is the Jacobian evaluated at a point æ for parameter 0., and o is the output of the i-th neuron in the last output layer L.
Lee et al. (2019) further proves that wide neural networks evolve linear models using gradient descent, and their training dynamics is controlled by ODEs that can be solved as
Me main) = (I e -mmitt) Yuain
(I)
for training data. Here f4 (x)) = T2] [ (a)) is the expected outputs of an infinitely wide network. Q
denotes the NTK between the training inputs. and unin and Y rain are drawn from the training set Durain As the training step tends to infinity we can see that Eq. reduce to μu rain) = Irain
The relationship between the conditioning of Ô and the trainability of networks is studied by Xiao et al. (2019) and we brief the conclusion as below. We can write Eq. i terms of the spectrum O:
[e( 1.(Xmmin main): (I - - Yiainn
where A; are the eigenvalues of Orain and we order the eigenvalues Ao 2 ... 2 Am- As it has been hypothesized by Lee et al. (2019) that the maximum feasible learning rate scales as ~ 2/A0, plugging this scaling for y) into Eq. 2 we see that the Am will converge exponentially at a rate given by 1/K, where Ao/Xn, is the condition number. Then we can conclude that if the of the NTK associated with a neural network diverges then will become untrainable, so we use as metric for trainability:
Figure 1: Condition number of NTK KN exhibits negative correlation with the test accuracy of archi- tectures HAS-Bench201 (Dong & Yang 2020).
Xo
KN
Am
KN is calculated without any gradient descent or label. Figure [ demonstrates that the AN is negatively correlated with the architecture's test accuracy, with the Kendall-tau correlation as -0.42. Therefore, minimizing the Ky during the search will encourage the discovery of architectures with high performance.
3.1.2 EXPRESSIVITY BY NUMBER OF LINEAR REGIONS
The expressivity of neural network indicates how complex the function can represent (Homik et al. 1989 Giryes et al., 2016). For ReI.U networks, each ReLU function defines a linear boundary and divides its input space into two regions. Since the composition of piecewise linear functions is still piecewise linear, every ReLU network can be seen as a piecewise linear function. The input space of a ReLU network can partitioned into distinct pieces (i.e. linear regions) (Figure 2 each of which is associated with a set of affine parameters, and the function represented by the network affine when restricted to each piece. Therefore, it is natural measure the expressivity of ReLU network with the number of linear regions can separate.
Input dim
Input dim 2 Figure 2: Example of linear regions divided by ReLU network
Following Raghu et al. 2017);; Montúfar 2017 7); Serra et al. (2018) Hanin & Rolnick 2011 b); Xiong et al. (2020), we first introduce the following definition of activation patterns and linear regions for ReLU CNNs.
Definition 1. Activation Patterns and Linear Regions (Xiong et al. (2020) Let N be a ReLU CNN. An activation pattern of Nf is function P from the set of neurons to (1,-1}, i.e., for each neuron z in N, we have P(z) E (1, -1}. Let 0 be a fixed set of parameters (weights and biases) in N, and P be an activation pattern. The region corresponding
P and is
P(P:)) == (x E Cx :2(x"; ;8) P(z) > 0, Vz E),
(4)
where 2(x :)) is the pre-activation of neuron z. Let RN denote the number of linear regions of N at 0, Le., RN == ((R(P:)) R(P: 8) + 0 for some activation pattern P).
Plot is generated by with the same method descrihed by Hanin & Rolnick 2019a).
4

---

Published as a conference paper at ICLR 2021
Eq- 4 tells us that a linear region in the input space is set of imput data x that satisfies a certain fixed activation pattern P(2). and therefore the number of linear regions Ry.0 measures how many unique activation patterns that can be divided by the network.
Acuntor (CS000
In our work, we repeat the measurement of the number linear regions by sampling network parameters from the
Kaiming Norm Initialization (He et al. 2013), and calculate the average as the approximation to expectation:
230
2000
12:00
2000
2002
3000
200
Ric #iiice Readona
Figure 3: Number of linear regions Rv of exhibits pos-
architectures in itive correlation with test accuracies.
RN Bg
(5)
We iterate through all architectures in NAS-Bench-20)
(Dong& & Yang 2020). and calculate their numbers of linear regions (without any gradient descent or label). Figure 3 demonstrates that the number of línear regions is positively correlated with the architecture's 's test accu- racy, with the Kendall-tau correlation 0.5. Therefore, maximizing the number of linear regions during the search will also encourage the discovery of architec- tures with high performance.
0.33
Lineur Region Ry
0.30
0.15
Tatio
0.20
0.15
0.10
6.90
0.03
0.0
Finally, in Figure we analyze the operator composi- tion of top 10% architecture by maximizing Ry and minimizing KW. respectively. We can clearly see that Ry and Ky have different preferences for choosing operators. They both choose large ratio of conv3 x 3 for high generalization performance. But meanwhile, Ry heavily selects convl 1, and RA leads to skip-connect, favoring the gradient flow.
pag
Figure KN and RNv prefer different operators HAS-Bench201.
3.2 PRUNING-BY-IMPORIAN
ARCHITECTURE SEARCH
Given the strong correlation between the architecture's 's test accuracy and its Rv and Rv, how to build an efficient NAS framework on top of them? We motivate this section by addressing two questions:
1. How to combine KN and Rx together, with good explicit trade-off?
We first need to turn the two measurements Rxcand Ry into one combined function, based on which we can rank architectures. As seen Figure and the magnitudes of Kд and Ry differ much. To avoid one overwhelming the other numerically, one possible remedy is normalization; but we cannot pre-know the ranges nor the value distributions of KN and RN, before computing them over search space. order make our combined function well defined before search and agnostic to the search space, instead of using the numerical values of KN and Ry,, we could refer to their relative rankings. Specifically, each time by comparing the sampled set of architectures peer-to-peer, can directly sum up the two relative rankings of KW and Ry the selection criterion. The equal-weight summation treats trainability and expressivity with the same importance conceptually Saatuualllyannddda and delivers the best empirical result: we thus choose it as our default combined function. We also tried some other means to combine the two, and the ablation studies can be found in Appendix D.2
How to search more efficiently?
Sampling-based methods like reinforcement learning or evolution can use rankings as the reward or filtering metric. However, they are inefficient, especially for complex cell-based search space. Consider network stacked by repeated cells (directed acyclic graphs) (Zoph et al.) [0188] Liu et al.)
2018b). Each cell has edges, and on each edge we only select one operator out of O (O set of operator candidates). There are |O] unique cells, and for campling-based methods, 10 networks have to be sampled during the search. The ratio 7 can interpreted as the sampling efficiency: method with small 7 can find good architectures faster. However, the search time cost of sampling-base based methods still scales up with the size of the search space, i.c., 1
We tried some weighted summations of the two, and find their equal-weight summation perform the best.
5

---

Published as a conference paper at ICLR 2021
(Lee al. 2018 Wang et al. 2020). propose NAS mechanism to quickly shrink the search possibilities and boost the efficiency further, reducing the cost from [O] to [O] E. Specifically, super-network, No composed of all possible operators and edges. In the outer loop, for every round we prune one operator on each edge. The outer-loop stops when the current supernet Nr is single-pati network i.c., the algorithm will return us the final searched architecture. For the inner-loop, we measure the change of Ky and Rw before and after pruning each individual operator, and assess its importance using the sum of two ranks. We order all currently available operators in terms of their importance, and prune the lowest-importance operator on each edge.
Inspired by recent works on pruming a
start the search with
The whole pruning process extremely fast. As we will demonstrate later, our approach is principled and can be applied to different spaces without making any modifications. This pruning-by- by-importacce mechanism may also be extended to indicators beyond KA and Ry. We summarize our training-free and pruning-batt -bsed NAS framework, TE-NAS, in Algorithm [
Algorithm 1: TE-NAS: Training- free Pruning- based NAS via Ranking of KN and Rx-
Input: supernet No stacked by cells, each cell has E edges, each edge has |O] operators, step = 0.
while NR. is not single-path network do
for each operator 03 in Nr do
D the higher Amt,o; the more likely we will prune of the lower A Ri,o, the more likely we will prune of Get importance by AN: 8n, (0;) index of oy in descendingly sorted list [Ast.o].... .... Antl
AKt,o; KN RN Voy
A Rt.,, R,, RN
Get importance by Rv: an (0;) = index of oy in ascendingly sorted list [A Re.e...... A A
Get importance s(o,) = Sx (0,) + sR (o,)
Ne+1 = =Ne
for each edge ei == L,..,, E do
11
j = arg min, (5(0g) oj E e;}
find the operator with greatest importance each edge.
No+1 Ne+1
13
1=t+1
14 return Pruned single-path network No-
3.2.1
VISUALIZATION OF SEARCH PROCESS
TE-NAS benefits towards better understanding of the search process. We can analyze the trajec- tory of KN and Ry during the search. It is worth noting that our starting point No. the un-pruned supernet, is assumed to be of the highest expressiv- ity (as it is composed of all operators the search space and has the largest number of parameters and ReLU functions). However, it has poor trainability, as people find many engineering techniques are re- quired to effectively training the supernet (Yu et al. 2020alb) b). Therefore, during pruning are expect- ing to strengthen the trainability of the supernet, while retaining its expressivity much as possible.
100
Duc 31aas Bocket
140
As we observe in Figure 5 the supernet N first pruned by quickly reducing Kx,,, i.e., increasing the network's trainability. After that, as the improve- ment of ky is almost plateaued, the method care- fully fine-tunes the architecture without sacrificing too much expressivity RN-
Ru. Aflww Regiens
Figure 5: Pruning trajectory on NAS- MAS-Bench--21 (top) and DART's search space (hottom). Number "O" indicates the supernet No hefore any pruning, which is of high expressivity but poor trainability.
Diifferent search spaces may have different criteria for the single- path network. In
(Dogg
& Yang 2020) each edge only keeps operator at the end of the search, while in DARTS space (Liu al. 2018b) there operators on each edge in the searched network.

---

Published as a conference paper at ICLR 2021
4 EXPERIMENTS
In this section, we evaluate our TE-NAS on two search spaces: 2020) and DARTS (Liu al. 2018b). Search and training protocols are summarized Appendix A Our code is available at: ht htsps: https://cithub. com wttp://////////o/o///I
(Dong & Yang
4.1 RESULTS ON MAS-BENCH-201
(Dong & Yang 2020) provides a standard cell-based search space (containing
15,625 architectures) and a database of architecture's performance evaluated under unified protocol. The network's test accuracy can be directly obtained by querying the database, which facilitates people to focus studying NAS algorithms without network evaluation. three datasets (CIFAR-10 10, CIFAR- 100, ImageNet-16- 16-1t- (Chrabaszez et al., 2017). ). The operation
supports
space contains none (zero), skip connection, conv1 x 1, conv3 x 3 convolution, and average pooling 3 x 3. We refer to their paper for details of the space. Our search is dataset-specific, i.e. the search and evaluation are conducted the same dataset.
Table 1: Comparison with state-of-the-art NAS methods on NAS-Bench-201. Test accuracy with mean and
deviation are reported. "opttial" indicates the best test accuracy achievable in NAS-Bench-201 search space.
Search Cost.
Search Method
Architecture
CIFAR-10
CIFAR-100
ImageNet-16-120
(GPU sec.)
ResNet (He et al 2016
93,97
70.86
43.63
RSPS (L & kar 2020
87.66(1.68 (1.69)
58.33(4.34)
31.14(3.8))
8007. 13
random RL
ENAS Pham el all 2018
54.30(0..0)
15.61(0.00)
16.32(0.00)
13314.51
(IRT) LLu et all
2018b
54..30(0.00)
15.61(0.00)
16.32(0.00)
10889.8 87
gradient
DARTS (2nd)
80186
54.30(0.000
15.61(0.00)
16.32(0.00)
29901.67
gradient
GDAS (Dong & Yang
2019
(3.61(0.00)
70.70(0.30)
(1.84(0.90)
28925.91
gradient
NAS w.o. Training Mellor al. 2020
91.78(1.46) (G.4)
67. (7.05)2289)
(7.07(6.39)
4.8
training- free
TE-NAS (ours)
93.9 93.9(0.47)
71.24(0.56)
42.38 (0.46)
1558
training-free
Optimal
94.37
73.51
47.31
We run TE-NAS for four independent times with different random seeds, and report the mean and standard deviation in Table [ We can see that TE-NAS achieves the best accuracy on all three datasets, and largely reduces the search cost (5x ~ 19x reduction). Although Mcllor et al. (2020) requires even less search time (by only sampling 25 architectures), they suffer from much inferior accuracy performance, with notably larger deviations across different search rounds.
4.2 RESULTS ON CIFAR- 10 WITH DARTS SEARCH SPACE
Architecture Space The DARTs operation space O contains eight choices: none (zero), skip connection, separable convolution 3 and 5 x 5, dilated separable convolution 3 x 3 and
max pooling 3 x 3, average pooling 3 x 3. Following previous works (Liu et al. 2018b Chen et al.. 2019 Xu et al. 2019), for evaluation phases, we stack 20 cells to compose the network and set the
Table 2: Comparison with of-te-of-the-ar NAS methods on CIFAR-10.
Test Error
Params (M)
Search Cost (GPU days)
Search Method
Architecture
(%)
AmochaNet-A Real ct al
2019
3.34(0.06)
3.2
3150
evolution
PNAS
Liu al
2018 2013
3.41(0.09)
3.2
225
SMBO
ENAS
Pham
2.89
4.6
0.5
RI.
NASNo-A (Zoph ot 2018
2.65
3.3
2000
RL
DARTS (Ist) iLiu et al.
8b)
3.00 14)
3.3
0.4
gradient
DARTS (2nd) (Lib al
20186
2.76(0.09]
3.3
1.0
gradicnt
SNAS Xic al 2013)
(0.5().02)
288
1.5
gradient
GDAS Line & Yanu 2019
2,82
255
D.17
gradient
BayesNAS Zhou
21199
(0.04)
3.4
0.2
gradient
ProxylessNAS Ca
2018
2,08
5.7
gradient
PARASS Chen al. A019)
2.50
3.4
0.3
gradient
PC-DARTS Xu 2019)
(0.0(
3.6
gradient
SDARTS-ADV Chen & Hisch 2020
2.61(0.02)
3.3
1.3
gradicnt
TE-NAS (ours)
2. 2.63(0.064)
3.8
0.05
trining-free
No cutout angmentttiio.
Different space: PyramidNet (Han et
2017 the backbone.
Recorded single GTX 10807 GPU.
7

---

Published as a conference paper at ICLR 2021
initial channel number as 36. We place the reduction cells at the 1/3 and 2/3 of the network and each cell consists of six nodes.
Results We run TE-NAS for four independent times with different random seeds, and report the mean and standard deviation. Table summarizes the performance of TE-NAS compared with other popular NAS methods. TE-NAS achieves a test error of 2.63%, ranking among the top of recent NAS results, but meanwhile largely reduces the search cost to only 0.05 GPU-day. ProxylessNAS achieves the lowest test error, but it searches on a different space with a much longer search time and has a larger model size. Besides, |Mellrr al. (2020) did not extend to their lacobian-based framework to DARTs search space for CIFAR- 10 or ImageNet classification.
4.3 RESULTS ON IMAGENET WITH DART' SEARCH SPACE
Architecture Space Following previous works Xu et al. for ImageNet slightly different from that for CIFAR- 10. During retraining evaluation, the network is stacked with 14 cells with the initial channel number set to 48, and we follow the mobile setting to control the FLOPs not exceed 600 MB by adjusting the channel number. The spatial resolution downscaled from 224 x 224 to 28 x 28 with the first three convolution layers of stride 2.
2019 Chen et al., 2019), the architecture
As shown in Table 3 we achieve top- 1/5 test error of 24.5% achieving competitive performance with recent state-of-the-an works in the ImageNet mobile setting. However, TE-NAS only cost four GPU hours with only one 1080Ti. Searching ImageNet takes a longer time than on CIFAR-10 10 due to the larger input size and more network parameters.
Results
Table 3: Comparison with state-of-the-art NAS methods on ImageNet under the mobile setting.
Test Errort %
Params (M)
Search Cost (GPU days)
Search Method
Architecture
top-1
top-5
NASNei-A A (Zoph al.
2018
26.0
8.4
5.3
2000
RL.
AmochuNatt (Keal
2019
24.3
7.6
6.4
3150
evolution
PNAS [Li ot 2018
25.8
8.1
5.1
225
SMBO
MnasNec-V2
8.0
RL
DARTS (2nd) LLi
201
26.7
8.7
4.7
gradicnt
SNAS (mild) (i
2013
27.3
9.2
4.3
1.5
gradient
GDAS [Donu Yanu
2019)
26.0
8.5
5.3
0.21
gradient
BayeaNAS
26.5
8.9
gradient
P-DARTS (CH:AK-10)
Ien et al
2019
24.4
7.4
4.9
0.3
gradient
P-DARTS (CIFAR 100)
hen el
2019
7.5
gradient
PC-DARTS (CTFAR- 10)
of 2119
25.1
7.8
5.3
0.1
gradient
TE-NAS (ours)
26.2
8.3
6.3
0.05
training-free
PC-DARTS (ImageNet) et 2019
24.2
7.3
5.3
3.8
gradient
ProxylesNNAS (CPU) Cal et
2018
24.9
7.5
7.1
8,3
gradient
TE-NAS (ours)
24.5
7.5
5.4
0.17
training-free
The architecture is searched on ImageNet, otherwise it is searched on CIFAR- 10.00mm or CIFAR-100.
CONCLUSION
The key questions in Neural Architecture Search (NAS) are "what are good architectures" and "how to find them". Validation loss or accuracy possible answers but not enough, due to their search bias and heavy evaluation cost. Our work demonstrates that two theoretically inspired indicators, the spectrum of NTK and the number of linear regions, not only strongly correlate with the network's performance, but also benefit the reduced search cost and decoupled analysis of the network's trainability and expressivity. Without involving any training, our TE-NAS achieve competitive NAS performance with minimum search time. We for the first time bridge the gap between the theoretic findings of deep neural networks and real-world NAS applications, and we encourage the community to further explore more meaningful network properties so that we will have better understanding of good architectures and how to search them.
ACKNOWLEDGEMENT
This work is supported in part by the NSF Real- Machine Learning program (Award Number: 2053279), and the US Army Research Office Young Investigator Award (W91 INF2010240) 0240).
8

---

Published as a conference paper at ICLR 2021
REFERENCES
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoe Le. Understanding and simplifying one-shot architecture search. In International Conference on Machine Learning. pp. 549-558, 2018.
Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston. Smash: one-shot model architecture search through hypemetworks. arXiv preprint arXiv:1708.0534. 2017.
Rebekka Burkholz and Alina Dubatovka. Initialization of relus for dynamical isometry. In Advances in Neural Information Processing Systems, pp. 2385-2395, 2019.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint arXiv:1812.00 00332, 2018.
Liang-Chieh Chen, Maxwell Collins, Yukun Zhu, George Papandreou, Barret Zoph, Florian Schroff, Hartwig Adam, and Jon Shlens. Searching for efficient multi-scale architectures for dense image prediction. In Advances in Neural Information Processing Systems, pp. 8699-8710, 2018
Wuyang Chen, Xinyu Gong, Xianming Liu, Qian Zhang, Yuan Li, and Zhangyang Wang. Fasterseg: Searching for faster real-time semantic segmentation. In International Conference on Learning Representations, 2020a.
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. arXiv preprint PrXiv:2002.05283 2020.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1294 1303, 2019.
Xin Chen, Lingxi Xie, Jun Wu, Longhui Wei, Yuhui Xu, and Qi Tian. Fitting the search space of weight-sharing nas with graph convolutional networks. arXiv preprint AXi::2004408423,, 2020b.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2019.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets, 2017.
Xiaoliang Dai, Peizhao Zhang, Bichen Wu, Hongxu Yin, Fei Sun, Yanghan Wang. Marat Dukhan, Yunging Hu, Yiming Wu, Yangqing Jia, et al. Chamnet: Towards efficient network design through platform-aware model adaptation. In Proceedings of the IEEE Conference on computer vision and pattern recognition, pp. 11398-11407, 2019.
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, pp. 1761-1770. 2019.
Xuanyi Dong and Yi Yang. Nas-bench-109 102: Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:2001.00326. 2020.
Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats-bench: Benchmarking nas algorithms for architecture topology and size. arXiv preprint arXiv:2009.00453 2020.
Yonggan Fu, Wuyang Chen, Haotao Wang, Haoran Li, Yingyan Lin, and Zhangyang Wang. Autogan- distiller: Searching to compress generative adversarial networks. International Conference on Machine Learning, pp. 3092-3223330 2303. PMLR, 2020.
Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random gaussian weights: A universal classification strategy? IEEE Transactions on Signal Processing, 64(13): 3454-3457, 2016.
Xinyu Gong, Shiyu Chang, Yifan Jiang, and Zhangyang Wang. Autogan: Neural architecture search for generative adversarial networks. Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3224-3234, 2019.

---

Published as a conference paper at ICLR 2021
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling, arXiv preprint 1rXiv:1904.00420, 2019.
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. In Proceedings of the IEEE conference computer vision and patlern recognition, pp. 5927-5935, 2017.
Boris Hanin and Mihai Nica. Finite depth and width corrections the neural tangent kernel. arXiv preprint 00XXvv:909.05990 2019.
Boris Hanin and David Rolnick. Complexity of linear regions in deep networks. arXiv preprint arXiv:1901.0002/ 2019a.
Boris Hanin and David Rolnick. Deep relu networks have surprisingly few activation patterns. In Advances in Neural Information Processing Systems, pp. 361-370, 2019b.
Soufiane Hayou, Araadd Doucet, and Judith Rousseau. On the impact of the activation functioo on deep neural networks training. arXiv preprint arXiv:1902.06853, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE international conference on computer vision, pp. 1026-10010 1034, 2015.
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, pp. 770-778, 2016.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, al. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366) 1989.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolu- tional neural networks. In Advances in neural information processing systems, pp. 1097-1105. 2012.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pp. 8572-8583, 2019.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint 1rX1v:1810.02340. 2018.
Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem. Sgas: Sequential greedy architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1620-1630, 2020a.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, pp. 367-377. PMLR, 2020.
Yanxi Li, Minjing Dong, Yunhe Wang, and Chang Xu. Neural architecture search in proxy validation loss landscape. In International Conference on Machine Learning, pp. 5853-5862. PMIR, 2020b.
Zhihang Li, Teng Xi, Jiankang Deng, Gang Zhang, Shengzhao Wen, and Ran He. Gp-nas: Gaussian process based neural architecture search. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pp. 11933-11942, 2020c.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv preprint arXiv: 1e09: 2019.
10

---

Published as a conference paper at ICLR 2021
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference Computer Vision (ECCV), pp. 19-34, 2018a.
Chenxi Liu, Liang- Chieh Chen, Florian Schroff, Hartwig Adam, Wei Hua, Alan L Yuille, and Li Fei- Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Proceedings the IEEE conference on computer vision and pattern recognition, pp. 82 82-92, 2019.
Liang-Chieh
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint / 180.009055 2018b.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tin-Yan Liu. Neural architecture optimization. In Advances in neural information processing systems, pp. 7816-7827, 2018.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie-Yan Liu. sumi-vipdr neural architecture search. arXiv preprint arXiv:2002. 2020.
Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. arXiv preprint arXiv:2006. 2044:77006006477,, 04647, 2020.
Guido Montúfar. Notes the number of linear regions of deep neural networks. Sampling Theory Appl, Tallinn, Estonia, Tech. Rep, 2017.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint arXiv:1802.03266. 2018.
Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl- Sohl-DDckstein. On the expressive power of deep neural networks. international conference on machine learning, pp. 2847-2854. PMLR, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence. volume 33, pp. 4780-4789 2019.
Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. International Conference on Machine Learning, pp. 4558 4566. PMLR, 2018
Yeonjong Shin and George Em Karniadakis. Trainability of relu networks and dependet initialization. Journal of Machine Learning for Modeling and Computing. ((1), 2020.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference Learming Representations, 2019.
Julien Siems, Lucas Zimmer, Arber Zela. Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas- bench-301 and the case for surrogate benchmarks for neural architccture search. arXiv preprint arXiv:2008. 09777, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. arXiv preprint 1eXX:v::400... 1556, 2014.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1-9, 2015.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2820-2823 2019.
Mingxing Tan, Ruoming Pang, and Quoc Le. Efficientdet: Scalable and efficient object detection. In Proceedings of the IEEF/CVF Conference Computer Vision and Pattern Recognition, pp- 10781-10790, 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376 2020.

---

Published as a conference paper at ICLR 2021
Wei Wen, Hanxiao Liu, Hai Li, Yiran Chen, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. arXiv preprint arXiv: 2019.
Lechao Xiao, Jeffrey Pennington, and Samuel S Schoenholz. Disentangling trainability and general- ization in deep learning. arXiv preprint arXiv:1912.1305: 2019.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1492-1500, 2017.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arXiv: /812.0992, 2018.
Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. arXiv preprint (rX00:2006.00978, 2020.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang. Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pc-darts: Partial channel connections for memory-efficient architecture search. In International Conference on Learning Representations, 2019.
Ge Yang and Samuel Schoenholz. Mean field residual networks: On the edge of chaos. In Advances in neural information processing systems, pp. 7103-7114, 2017.
Greg Yang. Scaling limits of wide neural networks with weight sharing: Gaussian process behavior, gradient independence, and neural tangent kernel derivation. arXiv preprint 2019.
Zhaohui Yang, Yunhe Wang. Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. Cars: Continuous evolution for efficient neural architecture search. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition (CVPR), June 2020a.
Zhaohui Yang, Yunhe Wang, Dacheng Tao, Xinghao Chen, Jianyuan Guo, Chunjing Xu, Chao Xu, and Chang Xu. Hournas: Extremely fast neural architecture search through an hourglass lens. arXiv preprint 2rXiv:2055.14444 2020b.
Jiahui Yu. Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang, Xiaodan Song, Ruoming Pang, and Quoc Le. Bignas: Scaling up neural architec- ture search with big single-stage models. arXiv preprint arXiv:2003. /42, 2020a.
Kaicheng Yu, Rene Ranftl, and Mathieu Salzmann. How to train your super-net: An analysis of arXiv preprint arXiv:2003.04276, 2020b.
training heuristics in weight-sharing
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In ICLR, 2020c.
Hongpeng Zhou, Minghao Yang, Jun Wang. and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. arXiv preprint arXiv: XX00:9995.04999, 2019.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning, arXiv preprint arXiv:1611.01578, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe 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
12

---

Published as a conference paper at ICLR 2021
A IMPLEMENTATION DETAILS
For RA we sample one mini-batch of size 32 from the training set, and calculate @(xr, x') = J(x) J(x')". For Ry we sample 5000 images, forward them through the network, and collect the activation patterns from all ReLU layers. The calculation of both KN and Rx are repeated three times in all experiments, where each time the network weights are randomly drawn from Kaiming Norm Initialization (He et al. 2015) without involving any training (network weights are fixed).
Our retraining settings (after search) follow previous works (Xu et al. 2019 Chen et al. 2019 Chen & Hsich 2020h. On CIFAR- 10, train the searched network with cutout regularization of length I6. drop-path (Zph et al., 2018) with probability as 0.3, and an auxiliary tower of weight 0.4. On ImageNet, also use label smoothing during training. On both CIFAR-10 and ImageNet, the network is optimized by an SGD optimizer with cosine annealing, with learning rate initialized as 0.025 and 0.5, respectively.
B SEARCHED ARCHITECTURE
We visualize the searched normal and reduction cells in figure and which is directly searched on CIFAR-10 10 and ImageNet respectively.
col_
[b-2]
dB_ccos_Sos
max pool
erp care
c [1-1]
sep cone.
sppuete S65
hip_cconect
(k)
515
sep_coav_5ad
ST5
dil comy
skip cop_connec
2
skp. contect
cony 3
sep_ouvv_5s5
(a) Normal Cell
(b) Reduction Cell
Figure 6: Normal and Reduction cells discovered by TE-NAS on CIFAR-10.
sqy Ju3
spp con Sct
di cony 363
aooo Ja3
c Hell
(a) Normal Cell
(b) Reduction Cell
Figure 7: Normal and Reduction cells discovered by TE-NAS on imageNet.
C DEPTH AND WIDTH PREFERENCE OF KN AND Ry IN DARTS SPACE
To analyze the impact of different architectures trainability and expressivity in DARTs search space, we visualize KN and Ry with different depths and width. Following Shu et al. 2019). the depth of a cell is defined as the number of connections on the longest path from input nodes to the output node, and the width of cell the summation of the edges of the intermediate nodes that are connected to the input nodes. We randomly sample 20,000 architectures in DARTs space, and plot the visualizations Figure X Good architectures should exhibit low ky (good trainability, blue dots in Figure ((a) and high RN (powerful expressivity, red dots in Figure ((b)). Therefore, K. and Ry tell us that in DARTs space shallow but wide cells are preferred to favor both trainability and expressivity. This conclusion matches the findings by Shu et al. (2019): existing NAS algorithms tend to favor architectures with wide and shallow cell structures, which enjoy fast convergence with smooth loss landscape and accurate gradient information.
13

---

Published as a conference paper at ICLR 2021
-2663
Ry *t Lince Regiota Dagher the better
NTX
Width
2305
1.0
1.5
2.0
2.5 Depth
3.0
3.
400
1.0
1.5
2.0
2.5
2.0
3.5
4.0
Depth
(a) KM
(b) Rx
Figure 8: Depth and width preference of (a) KN and (b) Rl DARTs Search Space.
D MORE ABLATION STUDIES
D.1 SEARCH WITH ONLY KN OR RN
As we observed in Table 4 searching with only KN Rx leads to inferior performance, which indicates the importance of maintaining both trainability and expressivity during the search.
Table 4: Search with only KN or Rx on CIFAR-100 in NAS- Bench-201 space.
Methods
CIFAR-100 Test Accuracy
Prune with only RN Prune with only Rx TE-NAS
69.25 (1.29)
70.48 (0.29)
71.24 (0.56)
D.2 DIFFERENT COMBINATION OPTIONS FOR KN AND RN
Pruning by s(o,) sn();) + sR(O;) is not the only option (see Algorithm Here this study we consider more:
1) pruning by s(o;) = min(sx (0;), sn(o;)) i.e., pruning by the worst case.
2) Pruninng by s(o,) = max(s,(o,)) sR(0,)) i.e., pruning by the best case.
3) pruning by summation of changes AKt,o, ARt,oy i... directly use the numerical values of the changes.
As we observed in Table our TE-NAS stands out of all options. This means good trade-off between KN and Rv are important, and also the ranking strategy is better than directly using numerical values.
Table 5: Search with only KN Rx on CIFAR-100 in NAS-Bench-201 space.
Methods
CIFAR- 100 Test Accuracy
Prune by s(o;) = min(s.. (0;) 8R(0;))
70.75 (0.73)
Prune by s(o,) = max(s,, (o;), (R)),)
70.33 (1.09)
Prune by Akt.o, + ARt.,
70.47 (0.68)
Prune s(0;) (0;) sn(0s) (TE-NAS)
71.24 (0.56)
14

---

Published as a conference paper at ICLR 2021
D.3 CORRELATION BETWEEN TEST ACCURACY AND COMBINATION OF RN AND RN
Figure D indicates that by using the sum- mation of the ranking of bothey and
Rv. the combined metric achieves a much higher correlation with the test ac- curacy. The reason can be explained by Figure 4 as RW and Ry prefers different operators in terms of trainability and Ex- pressivity. Their combination can filter out bad architectures in both aspects and strongly correlate with networks' final performance.
Tea Auurayy (CF46-100)
Rentalitte -3.6
Figure 9: Summation of ranking of ey and RN exhibits stronger (negative) correlation with the test accuracy of architec- tures MAS-Bench201 (Dong & Yang 2020).
E GENERALIZATION V.S. TEST ACCURACY
Conceptually, the generalization gap is the difference between a model's performance training data and its performance unseen data drawn from the same distribu- tion (e.g., testing set). In comparison, the two indicators KW (trainability) and Rg (expressiveness) of network determine how well the training set could be fit (i.c., training set accuracy), and do not directly indicate its generalization gap (or test set accuracy). Indeed, probing generalization of an untrained network at its initialization a daunting, open challenge that seems to go beyond the current theory scope.
Konda 0.70
Tax Accusayy (CI-- 200000000
47-
40
10
Train Acturary (CIFAR-100) 100)
Figure 10: The correlation hetween test accuracy and the training accuracy in 1AS-Bench201 (Dong & Yang 2020).
In NAS, we are searching for the architecture with the best test accuracy. As shown in Figure I0 in NAS- AAS-Bench201 the training accuracy strongly correlates with test accuracy. This also seems to be a result the current standard search space design that could have implicitly excluded severe overfitting. This explains why Kv and Rv, which only focuses trainability and expressiveness during training, can still achieve good search results test accuracy.
15


Reviews:
[{"review_id": "k5D2_jGDcoi", "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\nThis paper aims to speed up NAS with a training-free performance estimation strategy, i.e., estimate the performance of an architecture at initialization without training (not necessarily the absolute performance, but the relative ranking of architectures).\n\nThe proposed strategy estimates an architecture’s performance from two perspectives: (1) trainability, and (2) expressivity. The metrics to measure trainability and expressivity are inspired by recent progress on deep learning theory. Specifically, The trainability of an architecture is evaluated by the spectrum of its NTKs, and the expressivity is evaluated by the number of linear regions in its input space.\n\nThe authors also propose a pruning-based search algorithm that relies on the proposed performance estimation strategy. Experiments on two search spaces NAS-Bench-210 and DARTS show that the proposed method can find architectures with reasonable performance while being much faster.\n\n# Strong points\n1. Training-free NAS is conceptually novel and an interesting direction. This could make NAS more accessible and useful in practice if training-free methods can work.\n2. The authors draw inspiration from recent deep learning theory to design the training-free performance estimation metric.\n3. The proposed NAS method can complete the search much faster than previous NAS methods.\n\n# Weak points\n1. The metrics for trainability and expressivity seem to be the direct application/extension of recent deep learning theories (NTK, linear region). This makes the novelty of this work a bit weak.\n2. It’s unclear how the number of linear regions is computed. The authors gave a definition in Equation 4 but didn’t mention how exactly the number of linear regions is computed.\n3. The Kendall tau correlation between NTK/linear region and the test accuracy is actually weak based on the reported value (-0.42 / 0.5). Why would this weak correlation lead to an architecture with good performance? Also, the final method uses a combined relative ranking. What’s the Kendall tau for this combined relative ranking metric?\n4. The most interesting part in this work is the proposed training-free metric. It is important to compare this training-free metric with the typical metric (e.g., validation accuracy after training a limited number of epochs), while keeping other factors unchanged. What will the performance/search efficiency be if we combine the proposed metric with existing search algorithms (e.g., random search, reinforcement learning)? It will be helpful to compare the proposed metric and the typical metric using the same search algorithm and the same number of samples.\n5. It’s unclear how important the pruning mechanism is for the final performance/search efficiency. Having the above analysis/results will also help answer this question.\n6. The absolute performance on ImageNet in DARTS search space is not very strong. Also, for experiments on NAS-Bench-201, the authors only compare to some relatively weak baselines. As shown in Table 5 in the original NAS-Bench-201 paper, random search/REINFORCE perform on par or better than the proposed method, especially on ImageNet-16-120.\n\n# Justification of rating\nThe proposed metric is interesting. My main concern is the lack of analysis as mentioned above. Without those analyses, it’s hard to convince people that this metric is empirically useful. Also, the novelty is a bit limited as the metric seems to be a direct application/extension of recent deep learning theories.\n\n\n\n# Additional feedback\n\n“Training a supernet till convergence is extremely slow” - This sentence is not very accurate. Training a supernet is usually similar to training one architecture on the dataset. Although it’s more expensive than training-free, it’s practically acceptable. The drawback of supernet is more about its inaccurate performance estimation.\n\n“What to select” sounds more like the search space definition in NAS. The objective of NAS is always clear (best accuracy under certain FLOPS/params). I suggest the authors rephrase the text.\n\nFigure 5. The two figures have some overlappings.\n\n# After rebuttal\nI would like to thank the authors for their extensive efforts during the rebuttal. My main concerns are resolved, so I change the rating to borderline accept. I encourage the authors to update the paper with the results provided in the rebuttal, especially the explanation of the novelty and the results for \"Proposed metric with existing search algorithms\".\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "TWaN1RrxU5s", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: Training-free NAS is a promising direction. This work demonstrates that two theoretically inspired indicators: the spectrum of NTK and number of linear regions, strongly correlate with the network’s performance, and can be leveraged to reduce the search cost and decouple the analysis of the network’s trainability and expressivity. The authors thus proposed TE-NAS to rank architectures by analyzing the two indicators. Without involving any training, TE-NAS can achieve competitive NAS performance within minimum search time. \n\nPros:\n\n+ This work bridges between the advances in deep learning theory and the practice of NAS. I think it can become an important starting point towards theoretically inspired NAS and can motivate the discovery of more practically viable deep network performance indicators.\n\n+ The authors made efforts to add interpretability to their method and to understand the search process, e.g. Figure 4 and section 3.2.1. It is very interesting to see that the supernet first is pruned by quickly increasing the network’s trainability, and then fine-tuning the expressivity in a small range. \n\n+ On NAS-Bench-201 and DARTS search spaces, the propose method’s results are extremely promising. For the latter space, the proposed method can search within 30 minutes (on CIFAR-10) and 4 hours (on ImageNet), while the search models’ accuracy remain among the most competitive few. \n\nCons:\n\n- I remain skeptical how much the initial stage expressiveness/trainability would last and be preserved until end of training. Also, the two do not represent the full spectrum of desirable model characteristics. The ultimate goal of NAS is to seek a model of best generalization ability, which cannot be merely or easily from its expressiveness (fitting ability, i.e., achievable training error) and trainability (optimization difficulty). \n\n- Although the authors claimed that the two chosen indicators are strongly correlated with the network’s test accuracies, I’m not sure how true that actually is. In fact, probing the generalization from a trained model is already challenging, not to say from an untrained one. The authors might need to discuss more or to tone down further.\n\n- Figures 1 & 2 leave me with impression that both indicators can filter out some bad outlier architectures; but for many relatively good accuracy architectures, the correlations between the two and the true accuracy are not necessarily high (overall Kendall-tau magnitudes are between 0.4 and 0.5).\n\n- The authors also didn’t specify the computational complexity of computing the two indicators (average per architecture), except just saying they’re very fast. \n\n\n- More NAS works are related to the manuscript, for example [1][2][3].\n[1]SGAS: Sequential Greedy Architecture Search\n[2] GP-NAS: Gaussian Process Based Neural Architecture Search\n[3] HourNAS: Extremely Fast Neural Architecture Search Through an Hourglass Lens\n\n- (minor) The writing quality is in general good; some occasional typos:\ntraining-free AS framework: “AS” -> “NAS”;\nno only -> not only\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KKoqWzeCOPg", "reviewer": "AnonReviewer2", "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": "This paper introduces a searching framework of neural architectures ranking the candidates with two different metrics: the spectrum of NTK and the number of linear regions in the input space. These two metrics do not require the training of neural networks lightening the computational burdensome. Authors support their method by providing results from CIFAR-10, ImageNet, and NAS-Bench-201 benchmark (Dong & Yang).\n\nOverall, this paper proposes new metrics that can be used in the NAS search. Despite the paper well written, the performance of their methodology is incremental improvements (or par) among various existing NAS algorithms. I would recommend a marginally above acceptance threshold for now.\n\nStrength\n1. The author provides two new different metrics: a condition number of NTK and cardinality of linear regions to select good architectures besides the validation loss. \n2. Experiments not only on CIFAR10, ImageNet, but also NAS-Bench 201\n3. Free from the training allows their method to free from computational burdensome allowing to stack an equivalent number of cells for both the search and evaluation phase. \n\nWeakness\n1. The experiment results are par (or worse) to the existing NAS algorithms. By listing the recently published NAS literatures on CIFAR-10: P-DARTs: 2.50%, DATA: 2.59%, SGAS: 2.66%, PC-DARTs: 2.57%, RandomNAS-NSAS: 2.64%. Especially, SGAS and PC-DARTs require 0.25 and 0.1 GPU days respectively. (However, NAS-BENCH-201 results are competitive.)\n2. While no training has a benefit in the computational budget, the performance could be worse than the method with training (less information) as listed in Weakness 1. \n\nQuestions\n1. According to Definition 1, the number of linear regions depends on the fixed set of parameters $\\theta$. How much the number of linear regions affected by the $\\theta$? What happens you use the trained $\\theta$ or draw the network parameters with other initializing methods such as Ha initialization or Xavier initialization?\n2. Figure 5 shows the pruning trajectory based on the author's method. Intuitively randomly pruning the operation will also reduce the $\\kappa$ and the linear regions. Can you support the pruning efficiency based on the proposed metrics by comparing it with the random pruning?\n3. Have you tried weight sum loss such as $\\alpha \\Delta \\kappa + (1-\\alpha) \\Delta R$ where $\\alpha \\in (0, 1)$ be a hyperparameter? Table 4 seems $R$ plays more significant role than $\\kappa$. \n\nReference:\n1. Xu, Y et al. (2019, September). PC-DARTS: Partial Channel Connections for Memory-Efficient Architecture Search. ICLR2020\n2. Chen, X et al. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. ICCV2019\n3. Chang, J et al. DATA: Differentiable ArchiTecture Approximation. Neurips2019\n4. Li, G et al. SGAS: Sequential Greedy Architecture Search. CVPR2020\n5. Zhang, M et al. Overcoming Multi-Model Forgetting in One-Shot NAS with Diversity Maximization. CVPR2020\n6. Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search. ICLR 2020\n\n\n\n \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "H3yihVp5NOe", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "This work studied an interesting topic of training-free Neural Architecture Search (NAS). It utilizes two training-free indicators to measure the performance of a network without training it. The experiments show the proposed approach has improvement in searching time. \n\nHowever,  as the main contribution, the two measurements of the training-free indicators (trainability and expressivity) already be proposed by previous works. The rest contributions of this work are the proposed NAS networks, Instead of using the original loss function to guide the search process, this work simply combined those two measurements as a new ranking identifier of candidate architectures. The contributions not strong enough.\n\nAdvantages:\n1. The writing quality of the paper is good enough\n2. The paper has good descriptions of the related work.\n\nKey weakness:\n1. The major contributions of this work, the two network measurement methods, were proposed by previous works.\nThe first indicator:\n    Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in Neural Information Processing Systems 31. 2018a.\n    Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha SohlDickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in neural information processing systems, pp. 8572–8583, 2019.\n    Yeonjong Shin and George Em Karniadakis. Trainability of relu networks and data-dependent initialization. Journal of Machine Learning for Modeling and Computing, 1(1), 2020.\n    Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. 2019.\n\nThe seconde indicator:\n    Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of convolutional neural networks. arXiv preprint arXiv:2006.00978, 2020.\n\n2. The differences between the proposed pruning-based NAS and previous work are not clear. What is the key novelty of the proposed pruning strategy? \n3. According to Table 3, it seems that the TE-NAS couldn’t find the optimal neural architecture like P-DARTS and PC-DARTS, which confirms the limitation of this training-free search framework.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose training-free neural architecture search using two theoretically inspired heuristics: the condition number of the Neural Tangent Kernel (to measure "trainability" of the architecture), and the number of linear regions in the input space (to measure "expressivity"). These two heuristics are negatively and positively correlated with test accuracy, respectively, allowing for fast, training-free Neural Architecture Search. It is certainly not the first training-free NAS proposal, but achieves competitive results with much more expensive NAS methods.

A few reviewers mentioned limited novelty of the method, a claim with which I agree. The contribution of the paper, however, is something different than how it was presented. The core message seems to be that the two proposed heuristics can greatly speed up NAS, and should be a baseline method against which more expensive methods should test.

I feel like this is a borderline paper, but may be of interest to researchers in the field.
Decision: Accept (Poster)