NASI: Label- and Data-agnostic Neural Architecture Search at Initialization
Authors: Yao Shu
Shaofeng Cai
Zhongxiang Dai
Beng Chin Ooi
Bryan Kian Hsiang Low
Venue: ICLR 2022 Poster (2022)
Keywords: Neural Architecture Search
Initialization
Label- and Data-agnostic
Transferability
Neural Tangent Kernel

Abstract: Recent years have witnessed a surging interest in Neural Architecture Search (NAS). Various algorithms have been proposed to improve the search efficiency and effectiveness of NAS, i.e., to reduce the search cost and improve the generalization performance of the selected architectures, respectively. However, the search efficiency of these algorithms is severely limited by the need for model training during the search process. To overcome this limitation, we propose a novel NAS algorithm called NAS at Initialization (NASI) that exploits the capability of a Neural Tangent Kernel in being able to characterize the performance of candidate architectures at initialization, hence allowing model training to be completely avoided to boost the search efficiency. Besides the improved search efficiency, NASI also achieves competitive search effectiveness on various datasets like CIFAR-10/100 and ImageNet. Further, NASI is shown to be label- and data-agnostic under mild conditions, which guarantees the transferability of architectures selected by our NASI over different datasets.

Published as a conference paper at ICLR 2022
NASI: LABEL- AND DATA-AGNOSTIC NEURAL ARCHITECTURE SEARCH AT INITIALIZATION
Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Oui & Bryan Kian Hsiang Low Department of Computer Science, National University of Singapore (shuyao, shaoofng da zhongxi ang, oo bc, lowkh comp. nus www.edu.u..eeueeee edu.sg sg
ABSTRACT
Recent years have witnessed a surging interest in Neural Architecture Search (NAS), Various algorithms have been proposed to improve the search efficiency and the search effectiveness of NAS, i.e., to reduce the search cost and improve the general- ization performance of the selected architectures, respectively. However, the search efficiency of these algorithms is severely limited by the need for model training during the search process. To overcome this limitation, we propose a novel NAS al- gorithm called NAS ar Initialization (NASI) that exploits the capability of a Neural Tangent Kernel in being able to characterize the performance of candidate archi- tectures at initialization, hence allowing model training to be completely avoided to boost the search efficiency. Besides the improved search efficiency, NASI also achieves competitive search effectiveness on various datasets like CIFAR-101 10/100 and ImageNet. Further, NASI is shown be label- and data-agnostic under mild conditions, which guarantees the transferability of the architectures selected by our NASI over different datasets.
INTRODUCTION
The past decade has witnessed the wide success of deep neural networks (DNNs) in computer vision and natural language processing. These DNNs. e.g., VGG (Simonyan & Zisserman 2015).
ResNet (He al. (2016). and MobileNet (Howard et al.) 2017). are typically handcrafted by human experts with considerable trials and errors. The human efforts devoting to the design of these DNNs are, however, not affordable nor scalable due an increasing demand of customizing DNNs for different tasks. To reduce such human efforts, Neural Architecture Search (NAS) (Zoph & Le 2017) has recently been introduced to automate the design of DNNs. As summarized in (Elsken et al. 2019).
NAS conventionally consists of search space, search algorithm, and performance evaluation. Specifically, the search algorithm aims to select the best best-performing neural architecture from the search space based on its evaluated performance via the performance evaluation. In the literature, various search algorithms (Luo et al. 2018 Zoph et al. 2018 Real et al.) 2019) have been proposed to search for architectures with comparable or even better performance than the handcrafted ones.
However, these NAS algorithms are inefficient due to the requirement of model training for numerous candidate architectures during the search process. To improve the search inefficiency, one-shot NAS algorithms (Pham et al. 2018 Dong & Yang] [0119] Liu et al., 2019 Xie et al., (019)) have trained single one-shot architecture and then evaluated the performance of candidate architectures with model parameters inherited from this fine-tuned one-shot architecture. So, these algorithms can considerably reduce the cost of model training NAS, but still require the training of the one-shot architecture. This naturally begs the question whether NAS is realizable al initialization such that model training can be completely avoided during the search process? To the best of our knowledge, only few empirical efforts to date have been devoted developing NAS algorithms without model training Meelor et al. 2021 Park et al. 2020; Abdelfattah et al. 2021 Chen et al. 2021).
This paper presents a novel NAS algorithm called NAS at Initialization (NASI) that can completely avoid model training to boost search efficiency. To achieve this, NASI exploits the capability of Neural Tangent Kernel (NTK) (Jacot al.) 2018 Lee et al., 2019a) in being able to formally characterize the performance of infinite-wide DNNs at inittalization, hence allowing the performance of candidate architectures be estimated and realizing NAS at initialization. Specifically, given

---

Published as a conference paper at ICLR 2022
the estimated performance of candidate architectures by NTK, NAS can be reformulated into an optimization problem without model training (Sec. B.I). However, NTK is prohibitively costly to evaluate. Fortunately, we approximate it using similar form to gradient flow (Wang et al. 2020) (Sec. 3.2). This results in a reformulated NAS problem that can be solved efficiently by a gradient-based algorithm via additional relaxation using Gumbel-Softman (Jang et al.) 2017) (Sec. 3.3). Interestingly, NASI is even shown to be label- and data-agnostic under mild conditions, which thus implies the transferability of the architectures selected by NASI over different datasets (Sec. {
We will firstly empirically demonstrate the improved search efficiency and the competitive search effectiveness achieved by NASI in NAS-Bence 1Shotl (Zela et al. 2020b) (Sec. [.I). Compared with other NAS algorithmss, NASI incurs the smallest search cost while preserving the competitive performance of its selected architectures. Meanwhile, the architectures selected by NASI from the DARTS (Liu et al.) 2019) search space over CIFAR- 10 consistently enjoy the competitive or even outperformed performance when evaluated on different benchmark datasets, e-g.. CIFAR- 10/100 and ImageNet (Sec. 5.2). indicating the guaranteed transferability of architectures selected by our NASI. In Sec. [.3] NASI is further demonstrated to be able to select well-performing architectures on CIFAR- 10 even with randomly generated labels or data, which strongly supports the label- and data-agnostic search and therefore the guaranteed transferability achieved by our NASI.
2 RELATED WORKS AND BACKGROUND
2.1 NEURAL ARCHITECTURE SEARCH
A growing body of NAS algorithms have been proposed in the literature Zoph & Le 2017 Liu
ctt al., 2018; Luo et al. 2018 Zoph et al. 2018 Real et al., 2019) to automate the design of neural architectures. However, scaling existing NAS algorithms to large datasets is notoriously hard. Recently, attention has thus been shifted to improving the search efficiency of NAS without sacrificing the generalization performance of its selected architectures. In particular, one-shot architecture is
introduced by Phham et al. (2018) to share model parameters among candidate architectures, thereby reducing the cost of model training substantially. Recent works (Chen al. 2019 Dong & Yang 1019,Liu et al.) 2019 Xie et al. 22119] Chen & Hsich 2020 Chu et al. (2200) along this line have further formulated NAS as a continuous and dilferentiable optimization problem to yield efficient gradient-based solutions. These one-shot NAS algorithms have achieved considerable improvement in search efficiency. However, the model training of the one-shot architecture still needed.
A number of algorithms are recently proposed to estimate the performance of candidate architectures without model training. For example, Mellor et al. (202T) have explored the correlation between the divergence of linear maps induced by data points at initialization and the performance of candidate architectures heuristically. Mcanwhile, Park et al. (020) have approximated the performance of candidate architectures by the performance of their corresponding Neural Network Gaussian Process (NNGP) with only initialized model parameters, which is yet computationally costly. Abdelfattah et al. (021 have investigated several training-free freee proxies to rank candidate architectures in the search space, while Chen et al. (202T) intuitively adopt theoretical aspects in deep networks (e.g.. NTK (Jacot al. 2018) and linear regions of deep networks (Raghu al. 2017)) to select architectures with good trade-off between its trainability and expressivity. Our NASI significantly advances this line of work in (a) providing theoretically grounded performance estimation by NTK (compared with (Mellor et 2021; Abdelfattah et al. 2021: Chen et al., 202T)). (b) guaranteeing the transfcrability of selected architectures with its provable label- and data-agnostic search under mild conditions (compared with (Mellor et al., [ Park et a 2020) Abdelfattah et al.] [021] Chen et 2021 )) and (c) achieving SOTA performance in a large search space over various benchmark datasets (compared with (Mellor et al.] [221]] Park et al. [2020] Abdellattah al., 2021)). Based on our results, (hhu et al.
(2022) recently have provided further improvement on existing training-free NAS algorithms.
2.2 NEURAL TANGENT KERNEL (NTK)
Let a dataset (X,)) denote pair comprising set X' of m no-diiensionall vectors of input features and a vector y |m concatenating the m n-dimensional vectors of output values, respectively.
Mooe precisely, we approximate the trace norm of NTK.
2

---

Published as a conference paper at ICLR 2022
Let DNN be parameteriize by 0, E R" time t and output vector f(X;; 02) R (ab-
breviated to fi) of the predicted values of V. Jacot et al. (2018) have revealed that the training dynamics of DNNs with gradient descent can be characterized by NTK. Formally, define the NTK ( E mm (abbreviated to ④ as
(X), (x, Vo. (x)
(I)
Given a loss function L, at time and a learning rate y, the training dynamics of the DNN can then be characterized as
Vifi = - ( S,
- Vy.C.
(2)
Interestingly, as proven in (Jacot et al. 2018), the NTK stays asymptotically constant during the course of training as the width of DNNs goes to infinity. NTK at initialization (i.e., 2n) can thus characterize the training dynamics and also the performance of infinite-wide DNNs.
Lee ct al. (2119a) have further revealed that, for DNNs with over parameterization, the aforemen- tioned training dynamics can be governed by their first-order Taylor expansion (or linearization) at initialization. In particular, define
flim (æ: 0₂) f(x; Qo) + Vo, (a: 0o) (0, Op)
for all x E X. Then, f(w: .,) and (x; 0,) share similar training dynamics over time, as described formally in Appendix A.2 Besides, following the definition of NTK in ( this linearization flin achieves a constant NIK over time.
Given the mean squared error (MSE) loss defined as L. - m-mmmmm 1J f(X; 02)12 and the constant NTK θ, = Og the loss dynamics in (2) above can be analyzed a closed form while applying gradient descent with learning rate !) (Arora et al. 2019):
L = m Σ
1= mn
722))a( (u, y)2
(4)
where . -
mi A )O)),, u.u. and (, and denote the i-th largest eigenvalue and the corresponding eigenvector of Og respectively.
NEURAL ARCHITECTURE SEARCH AT INITIALIZATION
3.1 REFORMULATING NAS VIA NTK
Given a loss function L and the model parameters (.A) of architecture A,, we denote the training and validation loss Lunin and Lua., respectively. NAS is conventionally formulated as a bi-level
optimization problem (Liu et al. 2019): :
minA Laa (A);
(5)
s.t. (AA) A arg min Cuain (u (A)
Notably, model training is required to evaluate the validation performance of each candidate architec- ture in (5) The search efficiency of NAS algorithms (Real al. 2019 Zoph al. 2018) based on (5) thus severely limited by the cost of model training for each candidate architecture. Though recent works (Pham et al. 2018) have considerably reduced this training cost by introducing one-shot architecture for model parameter sharing, such a one-shot architecture still requires model training and hence incurs training cost.
To completely avoid this training cost, we exploit the capability of a NTK in characterizing the per- formance of DNNs at initialization. Specifically, Sec. 2 has revealed that the training dynamics of an over- parr-aarmattee DNN can be governed by its linearization at initialization. With the MSE loss, the training dynamics of such linearization are further determined by its constant NTK. Therefore. the training dynamics and hence the performance of a DNN can be characterized by the constant NTK of its linearization. However, this constant NTK is computationally costly to evaluate. To this end, we instead characterize the training dynamics (i.e., MSE) of DNNs in Proposition Cepossttioonssinnn Using the trace norm of NTK at initialization, which fortunately can be efficiently approximated. For simplicity, we use this MSE loss in our analysis. Other widely adopted loss functions (e.g., cross entropy with softmax) can also be applied, as supported in our experiments. Note that throughout this paper, the parameterization and initialization of DNNs follow that of Jacot et al. (2018). For L-layer DNN, we denote the output dimension of its hidden layers and the last layer as 71 n, n, respectively.
7 = k: and
3

---

Published as a conference paper at ICLR 2022
Proposition! 1. Suppose that ||0||2 S for X and y E 10, m0 for given dataset (X, of size [ = m. a given L-layer neural architecture A outputs fi E [0, 11mm as predicted labels of y with the corresponding MSE loss Lu Xmin (Go) > 0 for the given NTK O w.r.t ft at initialization, and gradient descent (or gradient flow) is applied with learning rate <. X (o)) Then, for any t 0, there exists a constant co such that as k 00,
L, S mm (nn-n>((0)) +E
(6)
with probability arbitrarily close to where q is set to 2t if < 0.5, and otherwise, X(Oo) (mn) Ei A:)))), and e _ 2coo/n/(mk) (1+ 11 1/k)
Its proof is Appendix A.3 Proposition I implies that NAS can be realizable at initialization.
Specifically, given a fixed and sufficiently large training budget in order to select the best berf-peeno architecture, we can simply minimize the upper bound of L. in (6) over the candidate architectures in the search space. Since both theoretical (Mohri et al. 2018) and empirical (Hardt et al. (016) justifications the literature have shown that training and validation loss are generally highly related, we simply use L, to approximate Lval. Hence, (5) can be reformulated as
A mn² -))T((n(()) +E s.t. x(OO(A)) <,-
Note that the constraint in 7 is derived from the condition < A ( (A)( in Proposition and 7) and c are typically constants during the search process. Following the definition of trace norm, can be further reduced into
max (A))ll
s.t. |@o((Alle < <mnrr)
Notably, (A))) only relies on the initialization of A. So, model training is required in optimizing (8), which achieves our objective of realizing NAS at initialization.
Furthermore, 8 suggests an interesting interpretation of NAS: NAS intends select architectures with good trade-off between their model complexity and the optimization behavior in their model training. Particularly, architectures containing more model parameters will usually achieve larger (A)]lr according to the definition in [ which hence provides an alternative to measuring the complexity of architectures. So, maximizing |Qo(A) ]|r leads architectures with large complexity and therefore strong representation power. On the other hand, the complexity of the selected architec- tures is limited by the constraint in ( ensure well-behaved optimization with a large learning rate 1) in their model training. By combining these two effects, the optimization of (8) naturally trades off between the complexity of the selected architectures and the optimization behavior in their model training for the best performance. Appendix C.I will validate such trade-off. Interestingly, Chen et al. (202T) have revealed a similar insight of NAS us.
3.2 APPROXIMATING THE TRACE NORM OF NTK
The optimization of our reformulated NAS in (8 requires the evaluation of @Go(A)ll for each architecture A in the search space, which can be obtained by
1 (A)ll. ΣnEx (o.(a))(z (A)ai)
(9)
where || ||e denotes the Frobenius norm. However, the Frobenius norn of the Jacobian matrix in (9) is costly to evaluate. So, we propose to approximate this term. Specifically, given a 7-Lischiitz continuous loss functior Cz (i.e., / I y for all X))
7 V Cmll = 1 Vor(A) (ax (o(A)) S \ (o(A))
(10)
The Frobenius norm || / (æc On(A))]l can thus be approximated efficiently using its lower bound (00) through automatic differentiation (Baydin al. 2017).
Meanwhile, the evaluation of [A)r())]kr 1rr in ( requires iterating over the entire dataset of size m, which thus incurs ((m) time. Fortunately, this incurred time can be reduced by parallelization over
The same learning rate is shared among all candidate architectures for their model training during the search process in conventional NAS algorithms such as (Liu et al. 2019)) Notably, the --I-iischizz continuity is well-satished by widely adopted loss functions (see Appendix A.3
4

---

Published as a conference paper at ICLR 2022
mini-batches, Let the set X2 denote the input feature vectors of the j-th randomly sampled mini- of size |xy] = b. By combining 99 and (10).
(O)(l)l 21 EBEX Vo. 22l 2. b- Eeex; Vooca)Coll
(11)
where the last inequality follows from Jensen's inequality. Note that (1T) provides an approximation of [|)r(A)]lrr Irr incurring ((m/b) time because the gradients within mini-batch can be evaluated in parallel. In practice, we further approximate the summation over m/b mini-batches in (II) by using only one single uniformly randomly sampled mini-batch X,. Formally, under the definition of () A 1 [ Veo(a) fan 12 our final approximation of |[@o())]l becomes
( my Oo
(12)
This final approximation incurs only ((1) time and can also characterize the performance of neural architectures effectively, as demonstrated in our experiments. Interestingly, similar form to (I2). called gradient flow (Wang et al. 2020p, has also been applied in network pruning at initialization.
3.3 OPTIMIZATION AND SEARCH ALGORITHM
The approximation of On (A))l tr in Sec. 3.2 engenders an efficient optimization of our reformulated
NAS in (8: Firstly, we apply a penalty method to transform (8) into an unconstrained optimization problem. Given a penalty coefficient and an exterior penalty function F(x)) - max(0, x) with pre-defined constant yn and randomly sampled mini-batch X,, by replacing (.4) lee with the approximation
122.
our reformulated NAS problem (8) can be transformed into
max
||oo(A)ll== (allll--FFF([@@ ==
(13)
Interestingly, [13] implies that the complexity of the final selected architectures limited by not only the constraint v (discussed in 3.1. but also the penalty coefficient μ.: For a fixed constant v, larger μ1 imposes stricter limitation the complexity of architectures (i.e.. [))()) v) in the optimization of (13
The optimization of (3) in the discrete search space, however, is intractable. So, we apply certain optimization tricks to simplify it: Following that Liu et al.] (2019); Xie et al. (2019). we represent the search space one-shot architecture such that candidate architectures in the search space can be represented as the sub-graphs of this one-shot architecture. Next, instead of optimizing (3)) we introduce distribution Por (AA (parameterized by a) the candidate architectures in this search space like that in (Zoph & Le 2017 Pham et al. [2018] Xie et al. (2019) to optimize the expected performance of architectures sampled from Pa (A):
max EArpa (A) [R(A)) S.L. R(A) A (o(A)) / (I) v)
(14)
Then, we apply Gumbel-Softmal (Jang et al. of (14) to be continuous and differentiable using the reparameterization trick. Specifically, for a given ar to sample an architecture A, we simply need to sample from p(g) = Gumbel 1) and then
2017 Maddison et al.) 2017) to relax the optimization
determine A using a and g (more details Appendix B.3
Consequently. (14) can be transformed
into
(15) After that, we approximate 15) based on its first-order Taylor expansion at initialization such that can be optimized efficiently through a gradient- algorithm. In particular, given the first-order approximation within the n-ighboordoood of initialization on (i.e., || 2 < E):
max Egrpla) [R(A(a,g))
Eg p(o) [R(A(a0 + A, R Bg-r(a) [R(A(ao.g)) g)) + Van R(A(ao. (illoo.))) A]]
(16)
the maximum of [6) is achieved when
Vag R(A((x): g))
x
arg max E. Bgg=p()) [Va R(A((a) g) TA] = = E gri(o) ||A||
|Bgpplg) V M(A(co, (ikkoo)))))
(17)
5

---

Published as a conference paper at ICLR 2022
Algorithm NAS at Initialization (NASI)
1: Input: dataset D (X, batch size b, steps T, penalty coefficient μ., constraint constant ini- tialized model parameters 0g for one-shot architecture and distribution Pa,, (AA) with initialization
Cxg = 0, set
2: for step 1
,..., do
3: Sample data DD D of size b
4: Sample 9t ~ p(g) = Gumbel 1) and determine sampled architecture A, based on Otg 9:
5: Evaluate gradient G Va Vont((A ItAAt) with data D3
6: end for
7: Estimate A with 18 and get a' aq + A
8: Select architecture A
arg max A Pa- Pa- (A)
bet
Space
1sh Space
Space
Pulor
Nom Tenden
162
16
143
1nd
Appuo Tree
Asprocet Cata
(a) Label-agnostic
(b) Data-agnostic
Figure 1: Comparison of the approximated ()) following T2) using the three search spaces of TTAS-Bench-ISS 1Shot CIFAR-10 (a) between random true labels, and (b) between random vs. true data. Each pair (z, y) in the plots denotes the approximation for one candidate architecture in the search space with true random labels (or data), respectively. The trends of these approximations are further illustrated by the lines in orange. In addition, Pearson correlation coefficient p of the approximations with random true labels (or data) is given in the corner.
The closed-form solution in 17 follows from the definition of dual norm and requires only one-step optimization, i.e., without the iterative update of A. Similar one-step optimizations have also been adopted in (Goodfellow et al. 2015 Wang et al. 2020).
Unfortunately, the expectation in makes the evaluation of A intractable. Monte Carlo sampling is thus applied to estimate A efficiently: Given T sequentially sampled (i.e., .1.....g1. and let
G A V R(A(oo. A can be approximated as
G
(18)
max m (Grl12)
Note that inspired by AMSGrad (Reddi et al. 2018), the expectation E gg-p(g)) V R(A(ao, ((A(oo,g))]]
in (17) has been approximated using max[]]] -..... ||Gz (2) in (T8) based sample of g at time Interestingly, this approximation non-decreasing
and therefore achieves a similar effect of learning rate decay, which may lead to better-behaved optimization of A". With the optimal A and xx* ar + A+, the final architecture can then be selected as A arg max Po (A), which finally completes our NAS at Initialization (NASI) algorithm detailed in Algorithm [ Interestingly, this simple and efficient solution in (8) can already allow to select architectures with competitive performances, as shown in our experiments (Sec.
4 LABEL- AND DATA-AGNOSTIC SEARCH OF NASI
Besides the improved search efficiency by completely avoiding model training during search, NASI can even guarantee the transferability of its selected architectures with its provable label- and data- agnostic search under mild conditions in Sec. 4.1 and Sec. 4.2 respectively. That is, under this provable label- and data-agnostic search, the final selected architectures on a proxy dataset using NASI are also likely to be selected and hence guaranteed perform well the target datasets. So, the transfcrability of the architectures selected via such label- and data- agnostic search can be naturally guaranteed, which will also be validated in Sec. emppirially

---

Published as a conference paper at ICLR 2022
4.1 LABEL-AGNOSTIC SEARCH
Our reformulated NAS problem ( has explicitly revealed that it can be optimized without the need of the labels from dataset. Though our approximation of [1o((A)l in 12) seemingly depends on the labels dataset, (12) can, however, be derived using random labels. This is because the Lipschitz continuity assumption on the loss function required by (10), which is necessary for the derivation of (12), remains satisfied when random labels are used. So, the approximation in (12) label-agnostic, which hence justifies the label-agnostic nature of NASI. Interestingly. NAS algorithm achieving similar lagnosiii search has also been developed in (Liu et al. 2020 which further implies the reasonableness of such label-agnostic search.
(and hence our optimization objective (13) that is based on this approximation)
The label-agnen -agnosic approximation of ()())]l demonstrated in Fig. Ta using the three search spaces of MAS--Benc-- Shott with randomly selected labels. According to Fig. [h. the large Pearson correlation coefficient (i.c., o x 1) implics a strong correlation between the approximations with random true labels, which consequently validates the label-agnostic approximation of (A)llel Overall, these empirical observations have verified that the approximation of | (A)]l ir and hence NASI based on the optimization over this approximation are label-agnostic, which will be further validated empirically in Sec. 5.3
4.2 DATA-AGNOSTIC SEARCH
Besides being label aabel-agnostic NASI is also guaranteed to be data-agnostic. To justify this, we prove in Proposition 2 (following from the notations in Sec. 3.1) below that [[Oo(A) Ir is data-agnostic under mild conditions.
Proposition Suppose that æ Ro and ||ح|| 1 for all E X given a dataset (X,Y) of size | m, a given L-layer neural architecture A is randomly initialized, and the 7-Lipschitz continuous nonlinearity a satisfies |a(x)] S |z]. Then, for any two data distributions P(x) and (ax)), denote 7 _ [())))) - ((=:)] dr, as ,I....,RR....................... -> oo sequentially,
(mn) -1 @o(A: PI (A: Q) S (D())
with probability arbitrarily close to 1. D(y) is set to L y = 1, and (1 - //1)/ otherwise.
J|arietttureA,l@(o(((.. || ||r is data-agnostic if either one of the following conditions is satisfied: (a) Different datasets achieve small Z or (b) the input dimension no is large. Interestingly, these two conditions required by the data-agnostic (O. (A)llı can be well-satisfied in practice. Firstly, always have Z < 2 according to the property of probability distributions. Moreover, many real-world datasets are indeed of high dimensions such ~00 for CIFAR-10 (Krizhevsky et al. 2209) and 100 for COCO (Lin et al. 2014). Since [A)][r)] under such mild conditions is data-agnostic, NASI using |[o(AA]] |rr as the optimization objective (8) is also data-agnostic.
Its proof is Appendix A.4 Proposition
2 reveals that for any neural architecture A,
While [Oo(A)]lrr is costly to evaluate, we demonstrate in Fig. D that the approximated [@o(AA) ||r in [12 is also data-agnostic by using random data generated with the standard Gaussian distribution. Similar to the results using true vs. random labels in Fig. D the approximated || [)(()]] using random vs. true data are also highly correlated by achieving a large Pearson correlation coefficient (i.e., P > 0.9). Interestingly, the correlation coefficient here is slightly smaller than the one of label-agnostic approximations in Fig. Dp. which implies that our approximated [(Qo()]] is more agnostic to the labels than data. Based on these results, the approximated ||O (A)]lrr is guaranteed to be data-agnostic. So, NASI based on the optimization over such a data-agnostic approximation also agnastg,,,,,,, which will be further validated empirically in Sec. 5.3
EXPERIMENTS
5.1 SEARCH IN NAS-BENCH- SHOT1
We firstly validate the search efficiency and effectiveness of our NASI in the three search spaces of NAS-Bende 1iich-SShott Shottl (Zela al. 2020b) on CIFAR-10. As these three search spaces relatively
7

---

Published as a conference paper at ICLR 2022
Search Space
Search Space 2
Search Space S
0.14
0.14
0.14
Toal Enor (86
0.12
0.12
0.12
0.10
0.10
0.10
0.08
0.00
0.08
0.06
0.06
0.06
Search Budget (epoch)
NASI
Figure 2: Comparison of search efficiency (search budget in x--xiis) and effectiveness (test error evaluated on CIFAR-10 in y-axis) between NASI and other NAS algorithms in the three search spaces of
The test error for each algorithm is reported with the mean and standard error after ten independent searches.
Table 1: Performance comparison among state-of-the-art (SOTA) image classifiers on CIFAR-10/100,
The performance of the final architectures selected by NASI reported with the mean and standard deviation of five independent evaluations. The search costs are evaluated on single Nvidia 1080Ti.
Test Error (%)
Params (M)
Search Cost
Architecture
Search Method
(GPU Hours)
C10
C100
C10
C100
DenseNet-BC (Huang al.
2017
3.46"
17.18"
25.6
25.6
manual
NASNet-A (Zoph 2018
2.65
3.3
48000
RL
AmoehaNet-A (Real et
2019
3.34
18.931
3.2
75600
evolution SMBO
PNAS (Luu et al. 2018
3.4110.09
19.53
3.2
3.2
5400
ENAS Pham al. 2018
2.89
19.43
4.6
4.6
12
RL
NAONeT (Lu et 2018
3,53
3.1
9.6
NAO
DARTS (2nd) (Liu
2019
2.76:1.099
17.54
3.3
24
gradient
GDAS Dong & Yang
2019
2.93
18.38
3,4
3.4
7.2
gradient
NASP Yao el am 2000
2.8310.09
3,3
2.4
gradient
P-DARTS (Chen et al. 2019
2.50
3.4
7.2
gradient
DARTS- (avg) Chu el al. 2020
2.59:10.08
17.51:10.25
3.5
3.3
9.6
gradient
SDARTS-ADV (Chen Hsien 2020
2.61=0.02
3.3
31.2
gradient
R-DARTS (1.2)
7ela ef al. 20208
2.95+0.21
18.01+00.26
38.4
gradient
TE-NAS (Chen et al. 2021
2.83:0.06
17.42+0.56
3.8
3.9
1.2
training-fice
NASI-FIX
2.79+0.07
16. 12--0.88
3.9
4.0
0.24
training- free
NASI-ADA
2.9010.13
16.84:1.400
3.7
3.8
0.24
training- free
Reported by Dong & Yang 2019] with their experimental settings.
Obtained by training corresponding architectures withrat cutout Devries Taylor 2017 augmentation.
Evaluated using our experimental settings in Appendix [B.4]
small, a lower penalty coefficient y and larger constraint (i.e., μ=1 and v-1000) are adopted to encourage the selection of high-complexity architectures the optimization of (13). Here, is determined adaptively as shown in Appendix B.I
Figure shows the results comparing the efficiency and effectiveness between NASI with a one- epoch search budget and other NAS algorithms with maximum search budget of 20 epochs allow sufficient model training during their search process. Figure 2 reveals that among all these three search spaces, NASI consistently selects architectures of better generalization performance than other NAS algorithms with a search budget of only one epoch. Impressively, the architectures selected by our one-epoch NASI can also achieve performances that are comparable the best-performing NAS algorithms with 19x more search budget. Above all, NASI guarantees its benefits of improving the search efficiency of NAS algorithms considerably without sacrificing the generalization performance of its selected architectures.
5.2 SEARCH IN THE DARTS SEARCH SPACE
We then compare NASI with other NAS algorithms in a more complex search space than MAS-Bench- 1hhtt1, i.e., the DARTS (Liu al. 2019) search space (detailed in Appendix B.2). Here, NASI
8

---

Published as a conference paper at ICLR 2022
Table 2: Performance comparison of the architectures selected by NASI with random true labels/data on CIFAR-10. The standard method denotes the search with the true labels and data of CIFAR-I0 10 and each test error in the table reported with the mean and standard deviation of five independent searches.
NAS-Bench-IShott
Method
DARTS
S1
S2
S3
Standard
7.311.1
7.2
7.2.00.6
2.95
Random Label
6.8
7.0=10.4
1.5
2.90=0.12
Random Data
6.6+0.2
0.5
7.3
2.97=0.10
selects the architecture with search budget ''= batch size of b-64 and μ= Besides, two different methods are applied to determine the constraint y during the search process: the adaptive determination with an initial value of 500 and the fixed determination with value of 100. The final selected architectures with adaptive and fixed // are, respectively, called NASI-ADA and NASI-FIX
(visualized in Appendix (C4), which are then evaluated on CIFAR-10/100 (Krizhevsky al. 2009)
and ImageNet (Deng et al. 20099) following Appendix B.4
Table summarizes the generalization performance of the final architectures selected by various NAS algorithms on CIFAR- 10/100. Compared with popular training-based NAS algorithms, NASI achieves a substantial improvement in search efficiency and maintains competitive generalization performance. Even when compared with other training-fre free NAS algorithm (i.e., TE-NAS) NASI is also able to select competitive or even outperformed architectures with a smaller search cost. Besides, NASI-FIX achieves the smallest test error on CIFAR- which also demonstrates the transferability of the architectures selected by NASI over different datasets. Consistent results on ImageNet can be found in Appendix C.S
5.3 LABEL- AND
SEARCH
To further validate the label- and data- agnostic search achieved by our NASI as discussed in Sec. we compare the generalization performance of the final architectures selected by NASI using random labels and data on CIFAR-10. The random labels are randomly selected from all possible categories while the random data is i..dd sampled from the standard Gaussian distribution. Both 1Shotl and the DARTS scarch space are applied in this performance comparison where the same search and training settings in Sec. 5.1 and Sec. 5.2 are adopted.
Table 2 summarizes the performance comparison. Interestingly, among all these four search spaces, comparable generalization performances are obtained on CIFAR-10 for both the architectures selected with random labels (or data) and the ones selected with true labels and data. These results hence confirm the label- and data-agnostic search achieved by NASI, which therefore also further validates the transferability of the architectures selected by NASI over different datasets.
6 CONCLUSION
This paper describes a novel NAS algorithm called NASI that exploits the capability of NTK for estimating the performance of candidate architectures at initialization. Consequently, NASI can completely avoid model training during the search process to achieve higher search efficiency than existing NAS algorithms. NASI can also achieve competitive generalization performance across different search spaces and benchmark datasets. Interestingly, NASI is guaranteed to be label- and data-agnostic under mild conditions, which therefore implies the transferability of the final selected architectures by NASI over different datasets. With all these advantages, NASI can thus be adopted to select well well-performing architectures for unsupervised tasks and larger-scale datasets efficiently, which to date remains challenging other training- based NAS algorithms. Furthermore, NASI can also be integrated into other training- basedd one-shot NAS algorithms to improve their search efficiency while preserving the search effectiveness of these training-based algorithms.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
To guarantee the reproducibility of the theoretical analysis in this paper, we have provided complete proof of our propositions and also the justification of certain assumptions in Appendix [A] Moreover, we have conducted adequate ablation studies to further investigate the impacts of these assumptions as well as the approximations used in our method on the final search results Appendix|C.o Meanwhile, to guarantee the reproducibility of the empirical results in this paper, we have provided our codes in the supplementary materials and detailed experimental settings Appendix B
ACKNOWLEDGMENTS
This research is supported by A under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Funds (Award 120H6b0151).
REFERENCES
Mohamed S. Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D. Lane. Zero-cost proxies for lightweight NAS. In Proc. ICLR, 2021.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Proc. ICML, pp. 322-332, 2019.
Atilim Gunes Baydin, Barak A. Pearlmutter, Alexey Andreyevich Radul, and Jeffrey Mark Siskind. Automatic differentiation in machine learning: A survey. Journal of Machine Learning Research, 18:153:1-153: 2017.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In Proc. ICLR, 2019.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. In Proc. ICLR, 2021.
Xiangning Chen and Cho-Jui Hsich. Stabilizing differentiable architecture search via perturbation- based regularization. In Proc. ICML, pp. 1554-1565, 2020.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proc. ICCV, pp. 1294-1303, 2019.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet as an alternative to the CIFAR datasets. 1eXXv:1707.000 .08899, 2017.
Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. DARTS- Robustly stepping out of performance collapse without indicators. arXiv:2009.0100 2020.
Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proc. CVPR, 2009.
Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv:1708 108 045552, 2017.
Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four GPU hours. In Proc. CVPR, pp. 1761-1770, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-200 Extending the scope of reproducible neural architecture search. In Proc. ICLR, 2020.
Simon S. Du, Xiyu Zhai, Barnabás Póczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In Proc. ICLR, 2019.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 20:55:1-55:21, 2019.
10

---

Published as a conference paper at ICLR 2022
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Proc. ICLR, 2015.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In Proc. ICML, pp. 1225-1234, 2016.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on ImageNet classification. In Proc. ICCV, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proc. CVPR, pp. 770-778, 2016.
Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang, Tobias Weyand, Marco Andrectto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. arxiv: T0N.::1744.4611, 2017.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proc. CVPR, pp. 2261-2269, 2017.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural Tangent Kernel: Convergence and generalization in neural networks. In Proc. NeurIPS, pp. 3580-8589, 2018.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with Gumbel-Softmax. In Proc. ICLR, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Jachoon Lee, Lechao Xiao, Samuel S. 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 Proc. NeurlPS, pp.
2019a.
Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. Torr. Snip: Single-shot network pruning based on connection sensitivity. In Proc. ICLR, 2019b.
Tsung-Y Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C. Lawrence Zitnick. Microsoft COCO: Common objects in context. In Proc. ECCV, pp. 740-755, 2014.
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 Proc. ECCV, pp. 19-35, 2018.
Chenxi Liu, Piotr Dollár, Kaiming He, Ross B. Girshick, Alan L. Yuille, and Saining Xie. Are labels necessary for neural architecture search? In Proc. ECCV, pp. 798-813- 2020.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proc. ICLR, 2019.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Yin Liu. Neural architecture optimization. In Proc. NeurIPS, pp. 7827-7838, 2018.
Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. ShuffleNet V2: Practical guidelines for efficient CNN architecture design. In Proc. ECCV, pp. 122-138, 2018.
Andrew L Maas, Awni Y Hannun, and Andrew Y Ng. Rectifier nonlinearities improve neural network acoustic models. In Proc. ICML, pp. 2013.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The Concrete distribution: A continuous relaxation of discrete random variables. In Proc. ICLR. 2017.
Joseph Mellor, Jack Turner, Amos Storkey, and Elliot Crowley. Neural architecture search without training. In Proc. ICML., 2021.
11

---

Published as a conference paper at ICLR 2022
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
Daniel S. Park, Jaehoon Lee, Daiyi Peng, Yuan Cao, and Jascha Sohl-Dickstein. Towards NNGP- guided neural architecture search. 1xXi:2011.066006 2020.
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proc. ICMI, pp. 4092-4101, 2018.
Maithra Raghu, Ben Poole, Jon M. Kleinberg, Surya Ganguli, and Jaseha Sohl-Dickstein. On the expressive power of deep neural networks. In Proc. ICMI,, pp. 2847-2854, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoe V. Le. Regularized evolution for image classifier architecture search. Proc. AAAI, pp. 4780-4789, 2019.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of Adam and beyond. In Proc. ICLR, 2018.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In Proc. ICLR, 2020.
Yao Shu, Zhongxiang Dai, Zhaoxuan Wu, and Bryan Kian Hsiang Low. Unifying and boosting gradient-based training-free neural architecture search. arXiv:2201009785, 2022.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In Proc. ICLR, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proc. CVPR, 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 Proc. CVPR, pp. 2820-2828, 2019.
Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proc. NeurIPS, 2020.
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In Proc. ICLR, 2020.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search. In Proc. ICLR, 2019.
Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. KNAS: green neural architecture search. In Proc. JCML, pp. 11613-11625, 2021.
Quanming Yao, Ju Xu, Wei-Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In Proc. AAAI, pp. 6664 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In Proc. ICLR, 2020a.
Arber Zela, Julien Siems, and Frank Hutter. NAS-Bench-IShott Benchmarking and dissecting one-shot neural architecture search. In Proc. ICLR, 2020b.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In Proc. ICLR, 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In Proc. CVPR. pp. 8697-8710, 2018.
12

---

Published as a conference paper at ICLR 2022
APPENDIX A THEOREMS AND PROOFS
We firstly introduce the theorems proposed by Jacot et al. (2018): Lee et al. (2019a). which reveal the capability of NTK characterizing the training dynamies of infinite-width DNNs. Note that the these theorems follow the parameterization and initialization of DNNs in (Jacol et al. 2018). Our analysis based on these theorems thus also needs to follow such parameterization and initialization of DNNs.
A.1 NEURAL TANGENT KERNEL AT INITIALIZATION
Jacot et al. 2018) have validated that the outputs of infinite width DNNs at initialization tends to Gaussian process (Theorem 1) and have further revealed the deterministic limit of NTK at initialization (Theorem 2
We denote n as v. X sts. matrix with all elements being 1.
Theorem (Jacot et al. (0188). For a network of depth L at initialization, with a Lipschitz nonlinear- ity and in the limit n1, nL-1 sequentially, the output functions fe. = 1, RL.
tnd (in law) iid centered Gaussian processes of covariance E(L), where E(L is defined recursively
by
(x,x')
TT 1 +32
n10
(2, 10 (o(g(z))o(g(2)))) 3
such that the expectation is with respect to centered Gaussian process with covariance L(L-1), Theorem 2 (Jacot et al. (2018). For network of depth I, at initialization, with Lipschitz nonlin- earity a, and the limit as n1, ,,,"", - 0o sequentially, the NTK ( converges probability deterministic limiting kernel:
(.) O lnn
Kernel + Po + R. is defined recursively by
(1) xx x²) = ()) x').
(L) (x, - (( x > (2) (x, + (x,)
where
(x x¹) = Bo ny ((g(=))d(g(('))
such that the expectation is with respect to a centered Gaussian process with covariance EL-11) and ē denotes the derivative of o.
A.2 TRAINING DYNAMICS OF INFINITE- INFINITE-WIDTH NEURAL NETWORKS
Given Amii A as the minimal eigenvalue of NTK θ and define Meriiical 2(Amin 2 + Amax (0) Lee al. (2119a) have characterized the training dynamics of infinite-wide neural networks below.
Theorem
(Lee et al. (019a)). Let T- = .... = and assume Amin ( > O. Applying gradient descent with learning rate Meritcal (or gradient flow), for every R with |||||| < with probability arbitrarily close to over random initialization,
ft f:1 O(K as 00
sup 1
Remark. For the case of L Du et al. (019) have revealed that if any two input vectors of a dataset are not parallel, then Amin + 0 holds, which fortunately can be well-satisfied for most real-world datasets. Though the training dynamics of DNNs only tend to governed by their linearization initialization when the infinite width is satisfied revealed in Theorem 3 empirical results in (Lee et al. (019a) suggest that such linearization can also govern the training dynamics of practical over-parameterized DNNs.
13

---

Published as a conference paper at ICLR 2022
A.3 PROOF OF PROPOSITION
With aforementioned theorems, especially Theorem our
Proposition
can be proved as below with
an introduced lemma (Lemma I).
Lemma 1. Let loss function & (x(;; 0,).3), abbreviated to L(f)), be --Lisschitz continuous within the domain V. Under the condition in Theorem 3 there exists constant en 0 such that as k oo,
[[((f))) [(f!")) - Cu7
Vk
with probability arbitrarily close to I.
Proof. Since ((f,) is y-Liisscitz continuous, for any v, u E V, we have
[[((v) - [(u)]l2 S 7 ||0 - u1l2
(19)
following the definition of Lipschitz continuity. Besides, under the condition in Theorem reveals that there exists constant cp such that as lt -
Theorem
ft ll2 -
Co
(20)
V
with probability arbitrarily close to 1. Combining
19 and 20
we hence can finish the proof by
[[ C( 1|2 s
[|
f
COT
as k + 0o.
(21)
Remark. The 7-Lipschitz continuity based on ||. ||a commonly satisfied for widely adopted loss functions. For example, given 1-dimensional MSE C m Σ, (z, 31) let Ys E [0, 1] denote the prediction and label respectively, the Lipschitz of MSE with respect Meanwhile, given the n-class Cross Entropy with Softmax L = -m Σ. Ej Vi log(pt,) as the loss function, let Pi,j E (0, 1) and Vi.j E {0, 1} denote the prediction and label correspondingly, with E, Vi. and pi.j - exp(x:,)/ 3; exp(xi,) for input Ti.j E IR, the Lipschitz of Cross Entropy with Softmax with respect to (II,1, Tz.j." Im,n) is then 1.
- (x1. 3mm) is
Proof of Proposition Note that the linearization flin (ar; 0,) achieves constant NTK O = C because its gradient with respect to 02 (i.e., Ve, f(: 0o)) stays constant over time. Given MSE as the loss function, according to the loss decomposition 4 in Sec. 2.2 the training dynamics of flin (2:; 0.) can then be analyzed in a closed form:
ma
[(S!
Σ (1 72, 2t (n. y)2,
(22)
m
where + ΣE
Mi (O,)))),uuu T. and (O,)) and denote the i-th largest eigenvalue and the corresponding eigenvector of Op respectively, With 7) < Amax (0,) and Amin (On) > 0, 17); then under the constraint that
Amax (0) = 0 < (p)) <
0 < (ep)
(23)
Amax (.)
Hence, for the case of L 2 0.5, with 0 < 17)1 < 1 and x(OO) - (mm) (,))))
mn
mn
- ny (
- ()))
(24)
mm(1 - vT((On))
Further, given 0 < < 0.5, the scalar function y the Jensen's inequality on this concave function,
21 is concave for any & E Rgo. Following from
2
mn
m
Σ
(0))) S mn
(),))
mn
(25)
mn 1 1 m
14

---

Published as a conference paper at ICLR 2022
With bounded labels y E [0, mh and the unit norm of eigenvectors |ull22
(u, y)
|1 |2 & 11112 I mn.
(26)
By introducing 24 23 and 26 into 22
the training loss ((ft. can then be bounded by
((f(tm) I (mn)
m
(27)
I m1 (1- x7,)))
where q is set to 2t if0 < 0.5, and otherwise.
Following from Theorem 3 while applying gradient descent (or gradient flow) with learning rate
< Amax < Maritical 2(Amin + Amax) for all x E X with ||>||| S 1, there exists constant co such that as k oc.
f 1l S
co
(28)
Vi
/ mn with f. with probability arbitrarily close Hence, f!nn E 1
[0, 10."""" Within the extended domain fi E 1-Co/I/K + 1/k
for the MSE loss function,
V 2 ||/ - ffll2
(29)
$ 2 n/m (1
cov cov 1/k)
(1+ coc/////// Lipschitz continuous. Hence, the MSE within this extended domain is 2 2///m
Combining with Lemma
C(fi) < C(f()))) + 2co v mn/mm))) (1 (1 11+cov1/1 1/kk
(30)
S mmn² 17 + 200 Veco/n//e (m(m)) (1 (1 (1+cov1/h)
which concludes the proof by denoting L, & C(ft).
Remark. ||>:|| can be well-satisfied for the normalized dataset, which conventionally adopted as data pre-processing in practice.
A.4 PROOF OF PROPOSITION 2
According to Theorem
1 (L) is determined by both E(L) (ar, x) and 5) (xr a:) of all E X. We hence introduce Lemma below regarding 1x) x) and (2)
(x, (xe x) to ease the proof of Proposiiion 2 Particularly, we set 3 0 for the 3 in Theorem I and Theorem throughout our analysis. Note that this condition is usually satisfied by training DNNs without bias.
Lemma 2, For a network of depth at initialization, with the "-Lipschitz continuous nonlinearity o satisfying (x)) < for all x E R. given the input features x E X,
{(L) (x, x)) S no
- x
(1)) (x. x) S 2²
where (x)) (x,, x) and ()) (x, x) are defined in Theorem 1 and Theorem 2 respectively, and
Proof. Following from the definition in Theorem
( (æ, x)
-B--N0. (
By-N((, [g²(x)
(31)
(8) y(4- (x,
15

---

Published as a conference paper at ICLR 2022
in which (a) follows from [x(x)] I |2|| and (b) results from the variance of g ((0,E((-1)) By
following 31 from layer to 1, we get
y (2,x) < (x,
(a) no l x
(32)
where (a) defined in Theorem
Similarly, following from the definition in Theorem
(xx x) Bg (
B
y-NNo, [-]]
(33)
in which (a) results from the y-Lipschitz continuity of nonlinearity and (b) follows from the expecta- tion of constant.
Proof of Proposition 2 Notably, Theorem 2 reveals that in the limit as Mi," 7 + 00
()) @ I,, with probability arbitrarily close 1 random initializations. We therefore only need to focus on this deterministic limiting kernel to simplify our analysis, i.e., let
sequentially, (L) O
O @ (1) @ Ing. Particularly, given input vectors P(x) with covariance matrix Ep and 7,-layer neural architecture of n-dimensional output, For 7 * 1, we have
(mn) (on))_|(Oolle 110oll (mm) '10 & Tng l|rr
(mn)
(4) 1| IT llr
m
0 (L)
||u
( Do (ax x))
E ((m)
(34)
(4)
E P(m)
0 (z, x) (x, (2) + (2))
(e)
R P()))
(20(4-1) + no .. xt
B P(w)
12006-1) m)
no + PEpllrr
in which (a) derives from the property of Kronecker product, (b) follows from the notation ny and (c) results from the property of expectation and trace norm. In addition. (d) follows from the definition of (L) (xe, æ)) in Theorem 2 and (e) is derived by introducing Lemma 2 into (d). Finally, (f) follows from the expectation and variance P(ær). By following (c-f) from layer L to we can get
(mm)-~1)0 S 2((6-11) F (D(2) (xx, a²)
no Eplhr (1 -1- (1122((-1)) -22)
(35)
n. Splle (1 -1-19 2-) (1 (1-22)
Notably, 35
derived under the condition that 7 * For the case of y 1, similarly, we can get
(mm) (mm)-'|[Qolle S 1 E.prr
(36)
Note that with ||0||| S 1, we have
[Epler = Em-P(()
x x
Ena [x]] Em- [x]]
< Egn
(37)
< 1.
16

---

Published as a conference paper at ICLR 2022
Given any two different distributions P(æ:) and Q(x), define Z = f Q(x)] dæ we
construct a special probability density function P(æ)= = 2 --11)(())) Q(x) to further employee
the bounds in (35) and 36.. Specifically, for + 1, by combining (35) and we can get
(mm) (mm)-~11[0(())) (P)) [Q)(
E P(x))
O (2., 2x)
E Q(æ)
+ (x, a
/ || P((x)) - Q((x)110 (L) (x, x.) dx
8
(38)
1 Eplhr (1- (1 -2²)
(4) 1 Z (2- (1-
< no
which (a) follows from (c) (34). (b) results from Cauchy Schwarz inequality and (c) obtained
by introducing inequality (35) and distribution P(x). Finally, (d) is based on (37
Similarly, in the case of 1, we can get
(mm) [|oo(P]] [10o(Q]l S nno t
(39)
which concludes the proof.
Remark. Note that ReLU is widely adopted as the nonlinearity in neural networks, which satisfies
the Lipschitz continuity with y and the inequality [a(()) S [x].. Notably, many other ReLU-type nonlinearities (e.g., Leaky ReLU (Maas et al. 2013) and PReLU (He et al. (0155) can also satisfy these two conditions.
APPENDIX B EXPERIMENTAL SETTINGS
B.1 DETERMINATION OF CONSTRAINT AND PENALTY COEFFICIENT μ
As demonstrated in Sec. 3.1 constraint (derived from [0)(A)]lrr mnnn in introduces trade-off between the complexity final selected architectures and the optimization behavior in their model training. This constraint hence is of great importance to NASI algorithm. Though has already been pre-defined - "ym in Sec. 3.3 still tend to take it as hyper-parameter to be determined for the selection of best-performing architectures in practice. Specifically, this paper, methods adopted determine during the search progress: The fixed and adaptive method shown as below. Notably, the final architectures selected by NASI via the fixed and adaptive method are called NASI-FIX and NASI-ADA, respectively. Note that our experiments in the main text suggest that both methods can select architectures with competitive generalization performance over different tasks.
The fixed determination. We initialize and v with uo during the whole search process. Hence, Vo is required to provide a good trade-off between the complexity of architectures and their optimiza- tion behavior in the search space. Intuitively, the expectation architecture complexity in the search space can help select architectures with medium complexity and hence implicitly achieve good trade-off between the complexity of architectures and their optimization behavior. Specifically, we randomly sample N 50 architectures in the search space (i.e., A1, ,Av),, and then determine vo before the search process by
====
10 = N-1 Σ (A))
(40)
Note that we can further enlarge vi in practice to encourage the selection architectures with larger complexity.
"We abuse this integration ease notations.
17

---

Published as a conference paper at ICLR 2022
The adaptive determination. We initialize with relatively large My and then adaptively update it with the expected (A)o() of sampled architectures during the search process. Specifically, with sampled architectures AI, A in the history, y at time t (i.e., 1/2) during the search process is given by
1 =
Po + Σ (
(41)
We apply a relatively large vo to ensure a loose constraint on the complexity of architectures in the first several steps of the search process. Note that the adaptive determination provides a more accurate approximation of the expected complexity of architectures in the search space than the fixed determination method if more architectures are sampled update v/. i.e., > N.
Note that 1 in Sec. 3.3 further reveals the limitation on the complexity of final selected architectures by the penalty coefficient Jr. Particularly, === indicates limitation on the complexity of architec- tures. Following from the introduced trade-off between the complexity of final selected architectures and the optimization behavior in their model training by the constraint v, for search space with relatively lorger-complextty architectures, a larger penalty coefficient je (i.e., search for architectures with relatively smaller complexity ensure a well-behaved optimization with larger learning rate 17. On the contrary, for search space with relatively smaller-completts architectures, a lower penalty coefficient μ (i.e., w=11 is adopted to ensure the complexity and hence the representation power of the final selected architectures. Appendix C.6 further ablation study on the constraint and the penalty coefficient, js.
2) is preferred to
B.2 THE DARTS SEARCH SPACE
Following from the DARTS (Liu et al. 2019) search space, candidate architecture in our search space comprise a stack of L cells, and each cell can be represented as a directed acyelic graph (DAG) of N nodes denoted by {zo, Z1.... IN..). To select the best-performing architectures, need to select their corresponding cells, including the normal and reduction cell. Specifically, zo and x1 denote the input nodes, which are the output of two preceding cells, and the output NN of cell is the concatenation of all intermediate nodes from 12 to N Following that of SNAS (Xie) al. 2019), by introducing the distribution of architecture in the search space (i.e., Pa (a) in (14), each intermediate nodes I; (2 < < N -1) 1) denotes the output of a single sampled operation 0 ~ (:()) with Eoco (o)
instead
given a single sampled input zz pz(z) with E O,... 1 and P = 1, where O is predefined operation set. After the search process, only operations achieving the t largest (o) and inputs achieving the top-2 largest (zx) for node 2; are retained. Each intermediate node zj hence connects to two preceding nodes with the corresponding selected operations.
Following from DARTS, the candidate operation set includes following operations: x 3 max pooling, 3 x 3 avg pooling, identity, 3 x 3 separable conv, 5 x 5 separable conv, 3 x 3 dilated separable conv, 5 x 5 dilated separable cony. Note that our search space has been modified slightly based on the standard DARTS (Liu et al.) 2019) search space: (a) Operation zero is removed from the candidate operation set in our search space since it can never been selected in the standard DARTS search space, and (b) the inputs of each intermediate node are selected independently from the selection of operations, while DARTS attempts to select the inputs of intermediate nodes by selecting their coupling operations with the largest weights. Notably, following from DARTS, we need to search for two different cells: A normal cell and a reduction cell. Besides, a max mrxx-pooling operation in between normal and reduction cell applied down-sampling intermediate features during the search process inspired by NAS-Bench- Shot1 (Zela et al., 2020b).
B.3 SAMPLING ARCHITECTURE WITH SOFTMAX
Notably, aforementioned p. (o) and (x) for the node x, follow the categorical distributions. To
relax the optimization of (14) with such categorical distributions to be continuous and differentiable.
Gumbel-Softmax (Jang et al. 2017 Maddison et al. 2017) is applied. Specifically, supposing p. (o())
and (z) parameterized by a and ai respectively, with Straight-Through (ST) Gumbel
Estimator (Jang al. 2017). we can sample the single operation and input for the node x; (2 < Kis
18

---

Published as a conference paper at ICLR 2022
N 1) during the search process by
exp((af, + p/gl/T)
j arg max
E, exp((o + p()/TT)
(42)
exp(1af,, + tTtx)/T
k- arg max
Ex exp((affx + )/T)
where Hi and gh,x are sampled from Gumbel(O, 1) and T denotes the softmax temperature, which is conventionally set to be in our experiments. Note that in 42) j E [0, | - and E [0,.... i 1]. which correspond to the |O) operations in the operation set O and the i candidate imputs for the node z;, respectively. Notably, the gradient through ST can be approximated by its continuous counterpart as suggested in (Jang et al.) 2017), thus allowing the continuous and differentiable optimization of (14). By sampling the discrete operation and input with 422 for each nodes in the cells, the final sampled architecture can hence be determined.
B.4 EVALUATION ON CIFAR-10/100 AND IMAGENET
Evaluation on CIFAR-10/100. Following DARTS (Liu et al. 2019), the final selected architectures consist of 20 searched cells: 18 of them are identical normal cell and 2 of them are identical reduction cell. An auxiliary tower with weight 0.4 is located at 13-th cell of the final selected architectures and the number of initial channels is set be 36. The final selected architecture
then trained via
stochastic gradient descent (SGD) of 600 epochs with a learning rate cosine scheduled from 0.025 to O, momentum 0.9, weight decay 3 10-1 and batch size 96 single Nvidia 2080Ti GPU. Cutout (Devries & Taylor 2017), and ScheduledDropPath linearly increased from 0 to 0.2 are also employed for regularization purpose.
Evaluation on ImageNet. evaluate the transfcrability of the selected architectures from CIFAR- 10 to ImageNet. The architecture comprises of 14 cells (12 normal cells and reduction cells). To evaluate in the mobile setting (under 600M multiply-add operations), the number of initial channels set to 46. We adopt conventional training enhancements (Liu et al., 2019: Chen et al., 2019) Chen & Hsieh| (2020) include an auxiliary tower loss of weight 0.4 and label smoothing. Following P-DARTS (Chen et al. 2019) and SDARTS-ADV (Chen & Hsieh 2020). we train the model from scratch for 250 epochs with batch size of 1024 on Nvidia 2080Ti GPUs. The learning rate is warmed up to 0.5 for the first 5 epoch and then decreased to zero linearly. We adopt the SGD optimizer with 0.9 momentum and weight decay x 10 5 for the model training on ImageNet.
APPENDIX C MORE RESULTS
C.I TRADE-OFF BETWEEN MODEL COMPLEXITY AND OPTIMIZATION BEHAVIOUR
In this section, empirically validate the existence of trade-off between model complexity of selected architectures and the optimization behavior in their model training for our reformulated NAS detailed in Sec. 3.
The trade-off in NAS-Bench-IShotL. Specifically, Figure illustrates the relation between test error and approximated |/oo ||r of candidate architectures in the three search spaces of NAS- Bench-1Shotl. Note that with the increasing of the approximated @Qo(A)]l the test error decreases rapidly to a minimum and then increase gradually, which implies that architectures only with certain | [A) (or with desirable complexity instead of the largest complexity) can achieve the best generalization performance. These results hence validate the existence of trade-off between the model complexity and the generalization performance of selected architectures. Note that such trade-off usually results from different optimization behavior in the model training of those selected architectures as demonstrated the following experiments.
The trade-off in the DARTS search space. We then illustrate the optimization behavior of the final selected architecture from the DARTS search space with different constraint and penalty coefficient in Figure 4 to further confirm the existence of such trade-off in reformulated NAS (8) Specifically,
19

---

Published as a conference paper at ICLR 2022
2.0
1e-1
Search Space
2.0
1e-1
Search Space 2
2.0
1e-1
Search Space 3
Test Eroo (99
1.5
1.5
1.5
1.0
1.0
0.5
2
Approximated Trace Norm
Figure 3: The relation between test enror and approximated |@o(A)) of candidate architectures Bench-1Shotl over CIFAR-10. Note that r-axis denotes the approximated (.A()A)] which is averaged over the architectures grouped in the same bin based on their approximated || ( [l))l Correspondingly, y-axis denotes the averaged test with standard deviation (scaled by 0.5) of these grouped architectures. In addition, the red lines demonstrate the smallest test errors achieved by candidate architectures in these three search spaces.
in the three search spaces of
== 010, 2.26
5=
12.5
100. 4.27
12.5
2,p 4.27
Text Eroo (%)
200.p 4.49
3.p 4.13
Test Error
10.0
Whn
10.0
7.5
7.5
5.0
2.5
2.5
0
200
400
600
0
200
400
600
Epoch
Epoch
(a) Constraint
(b) Penalty coefficient μ
Figure 4: The optimization behavior (test error CIFAR-10 in model training) of the final selected architectures with different constraint y and penalty coefficient μ.. The model parameter (MB) denoted by p of each architecture is given in the top-right corner.
we apply NASI with the fixed determination of to select architectures in the the DARTS search space over CIFAR-10, where Vn the fixed determination method introduced in Appendix B. is modified manually for the comparison. Besides, search budget of T 100 and batch size of b 64 are adopted. These final selected architectures are then trained on CIFAR-10 following Appendix 5.2
Note that, in Figure a), with the increasing of v. the final selected architectures by NASI contain more parameters and hence achieve larger complexity. Meanwhile, the final selected architecture with v=10 enjoys faster convergence rate in the first 50 epochs, but poorer generalization performance than the one with == 200. Interestingly, the final selected architecture with == realizes the fastest convergence and the best generalization performance by achieving a proper complexity of final selected architectures. These results validate the existence and also the importance of the trade-off' between the complexity of final selected architectures and the optimization behavior their model training. However, the trade-off introduced by the penalty coefficient shown in Figure is hard to be observed, which indicates that the constraint in terms of the trade-off between the complexity of architectures and their optimization behavior. Interestingly, Figure 4 can still reveal the slower convergence rate and poorer generalization performance caused by the selection of architecture with relatively larger complexity, i.c., μ=1.
of greater importance than the penalty coefficient
C.2 COMPARISON TO OTHER TRAINING-FREE METRICS
We compare our methods with other training-fre free NAS methods using both the Spearman correlation and the Kendall's tau between the training-free ffree metrics and the test accuracy CIFAR-10 10 in the three search spaces of NAS-Bench- Bench--Shotl.. We adopt one uniformly randomly sampled mini-batch data to evaluate these two correlations and apply the same implementations of these training-free
20

---

Published as a conference paper at ICLR 2022
Table 3: Comparison of the Spearman correlation and the Kendall's tau for various training-free metrics in the three search spaces of NAS- Seee-Bnnch--hhee on CIFAR- 10.
Spearman Correlation
Kendall's Tau
Methods
S1
S2
S3
S1
S2
S3
SNIP (Lee et al. 2019b
0.49
0.62
0.79
0.39
-0.99
0.63
GraSP (Wang cl al. 2020
0.41
0.54
0.17
0.33
0.42
0.15
SynFlow (Tanaka et al. 2020
0.52
00.45
-0.53
-0,42
-0.40
-0,47
NASWOT (Mello al. 2021
0.21
0.32
0.54
0.16
0.24
0.44
NASI (conditioned)
0.62
0.74
0.76
0.44
0.53
0.53
Table The comparison among state-of-the-ard (SOTA) NAS algorithms on NAS-Bench-22 The performance of the final architectures selected by NASI is reported with the mean and standard deviation of four independent trials. The search costs are evaluated on a single Nvidia 1080Ti.
Test Accuracy (%)
Search Cost
Architecture
Search Method
(GPU Sec.)
C10
C100
IN-16-120
ResNet (He et
2016
93.97
70.86
43,63
ENAS (Pham
2018
54.30
15.61
16.32
13315
RI. gradient gradient
DARTS (Ist)
2019
54.30
15.61
16.32
10890
DARTS (2nd) LLu ct al. 2019
54,30
15.61
16.32
29902
GDAS (Dong & Yang 2019
93.61++0.09
70.70+0.30
41.84+0.90
28926
gradient
NASWOT (N=10) Mellor et al. NASWOT (N=100)
2021
92.44:
68 68.62.12.04
41.31:4.11
3
training-free
(Mellor et 20
92.81=0.99
1.74
43.1023.16
30
truining-free
NASWOT (N=1000) (Mellor
2021
92.96
1.,9
44.44
306
training- free
TE-NAS (Chen et al. 2021
93.90.10.47
71.24
42.38::0466
1558
truining-fres free
KNAS [Xu et at. 2021
93.05
68.91
34.11
4200
training-free free
NASI (2)
93.08
09.51
40.87-10.85
30
training-free free
NASI (42)
93.5510.10
71.2010.14
44.841141
120
training free
NAS methods (Abdelfattah et al., 2021) for the comparison. Table summarizes the comparison, where the results of our metric are reported under the constraint in ( Interestingly, our metric
generally achieves a higher positive correlation than other training-free metrics, which confirms the reasonableness and also the effectiveness of our training- free metric.
C.3 SEARCH
To further justify the improved search efficiency and competitive search effectiveness of our NASI algorithm, we also compare it with other state-of-the-art NAS algorithms in SAS-Bench--201 (Dong & Yang, (220) on RIFAR-10/100 (C10/100) and ImageNet- comparison. Note that the baselines in Table are obtained from TE-NAS (Chen et al. 2021 paper. Notably, compared with training-basse based NAS algorithms, our NASI algorithm can achieve significantly improved search efficiency while maintaining a competitive or even outperforming test performance. Furthermore, our NASI algorithm is shown to be able to enjoy both improved search efficiency and effectiveness when compared with most other training -free baselines. Although TE-NAS, as the best-performing training- free NAS algorithm on both CIFAR- 10/100, achieves relatively improved test accuracy than our NASI (T), our NASI with a search budget of T 30s is 50x more efficient than TE-NAS and is able achieve compelling test performance datasets. Moreover, by providing a larger search budget, our NASI algorithm (i.e., NASI (4T)) can in fact achieve comparable (on CIFAR- 10/100)) or even better (on ImageNet-166 16-1e0) search results with 12x lower search cost compared with TE-NAS.
(IN- (N-16)2000 Table summarizes
all the three
C.4 ARCHITECTURES SELECTED BY NASI
The final selected cells in the DARTS search space (i.c.. NASI-FIX and NASI-ADA used in Sec. 5.2) are illustrated in Figure 5 where different operations are denoted with different colors for clarification.
-e-----2---10000 ImageNet-111 16-200 is down-sampled variant of ImageNet (1mageNet16x16)
(Chrabaszez et al. 2017
21

---

Published as a conference paper at ICLR 2022
x
Dil- Di-3
Sep-3 Dil-5 Sep-3
Sep-3
Sep-5
Max
Max
Sep-5
Sep-3 Sep-3
Sep-3
D
Sep-3
Sep-3
2
(a) NASI-FIX (Normal)
(b) NASI-FIX (Reduction)
x
Sep-5
Di-5
Dil-3-Di-3 Sep-3
Sep-3
Sep-5
Max
Max Sep-5
Sep-5
Sep-3
Sep-3
Avg
Skip
Sep-3
3
x5
X x_
3
x
x_5
x_6
NASI-ADA (Normal)
(d) NASI-ADA (Reduction)
Figure 5: The final selected normal and reduction cells of NASI-FIX and NASI-ADA in the reduced DARTS search space on CIFAR-10. Note that co 2n denote the input nodes, 22, 2,, 44, 25 denote intermediate nodes and øe denotes the output node as introduced in Appendix B.2
22

---

Published as a conference paper at ICLR 2022
Table 5: Performance comparison among SOTA image classifiers ImageNet. Note that architec- tures followed by C10 are transferred from the CIFAR-10 dataset, while architectures followed by ImageNet are directly selected on ImageNet.
Test Error (%)
Params (M)
+X
Search Cost
Architecture
(M)
(GPU Days)
Top-1
Top-5
Inception-vl (Szegedy al. 2015
30.1
10.1
6.6
1448
MobileNet (Howard ct al. 2017)
29.4
10.5
4.2
569
ShuffleNet (x(v2) Ma al. 2018
25.1
7.6
7.4
591
NASNet-A Zoph et al. 2018
26.0
5.3
564
2000
AmoebaNet-A (Real et al. 2019)
25.5
8.0
5.1
555
3150
PNAS (Liu et al. 2018)
25.8
8.1
5.1
588
225
MnasNet-92 lan et al.
2019)
25.2
8.0
4.4
388
DARTS (Liu et al. 2019)
26.7
8.7
4.7
574
4.0
SNAS (mild) (Xre et al. 2019
27.3
9.2
4.3
522
1.5
GDAS Dong Yang 2019)
26.0
8.5
5.3
581
0.21
ProxylessNAS (Cai et al. 2019)
24.9
7.5
7.1
465
8.3
P-DARTS (Chn
2019
24.4
7.4
4.9
557
0.3
DARTS- (Chu et al. 2020)
23.8
7.0
4.5
467
4.5
SDARTS-ADV (Chen & Hsich
2020
25.2
7.8
5.4
594
1.3
TE-NAS (C10) (Chen et al.
2021
26.2
8.3
5.0
0.05
TE-NAS (ImageNet) (Chen et
2021
24.5
7.5
5.4
0.17
NASI-FIX (C10)
24.3
7.3
5.2
585
0.01
NASI-FIX (ImageNet)
24.4
7.4
5.5
615
0.01
NASI-ADA (C10)
25.0
7.8
4.9
559
0.01
NASI-ADA (ImageNet)
24.8
7.5
5.2
585
0.01
Interestingly, according to the definitions and findings in (Shu et al. 2020), these final selected cells by NASI are relatively deeper and shallower than the ones selected by other NAS algorithms and hence may achieve worse generalization performance. Nonetheless, in experiments, the architectures constructed with these cells (i.e., NASI-FIX and NASI-ADA) achieve competitive or even better generalization performance than the ones selected by other NAS algorithms as shown in Table [ and Table A possible explanation is that our NASI algorithm provides good trade-off between the complexity of architectures and the optimization in their model training, while other NAS algorithms implicitly prefer architectures with smaller complexity and faster convergence rate as revealed (Shu et al., 2020). Note that the final selected cells NASI-FIX and NASI-ADA of great similarity to each other, which hence implies that the adaptive determination and the fixed determination of constraint share similar effects the selection of final architectures.
C.5 EVALUATION ON IMAGENET
We also evaluate the performance of the final architectures selected by NASI on ImageNet and summarize the results in Table 5 Notably, NASI-FIX and NASI-ADA outperform the expert- designed architecture ShuffleNet 2x(x2), NAS-based architecture MnasNet-92 and DARTS by large margin, and are even competitive with best-performing one-shot NAS algorithm DARTS- Notably, while achieving better generalization performance than TE-NAS (ImageNet), NASI (C10) even shown to ImageNet based on its provable transferability in Sec. 4 Meanwhile, by directly searching on ImageNet, NASI-ADA (ImageNet) is able to achieve further improved performance over NASI-ADA (C10) while the performance of NASI-FIX (ImageNet) and NASI-FIX (C10) are quite similar Above all, these results on ImageNet further confirm the good transferability the architectures selected by NASI to larger-scale datasets.
more efficient by directly transferring the architectures selected on CIFAR-10 10
In order to maintain the same initial channels between NASI-FIX (ImageNet) and NASI-FIX (C10), the multiply-add operations of NASI-FIX (ImageNet) has to he larger than 600M by small margin.
23

---

Published as a conference paper at ICLR 2022
Table 6: Search with varying architecture widths N in the three search spaces of
Spaces
=
N = 4
N 8
N = 16
N = 32
S1
7.0:0..6
8.3
8.0=2.2
1.3
6.5
S2
7.3
8.0
7.3=0.6
7.0 6.8+003
7.3
S3
7.6+0.8
7.7+1.1
6.8=0.1
6.4+0.2
Table 7: Pearson correlation between our NTK trace norm approximation and the exact NTK trace norm in the three search spaces of Mini-batch
Spaces
Sum
b
4
8
16
b=
b 64
128
S1
0.74
0.80
0.84
0.83
0.85
0.86
0.88
S2
0.82
0.87
0.90
0.89
0.91
0.91
0.92
S3
0.66
0.74
0.81
0.79
0.82
0.84
0.87
C.6 ABLATION STUDY AND ANALYSIS
The impacts of architecture width. As our theoretically grounded performance estimation of neural architectures relies an infinite width assumption (i.e., л - do in Proposition (T), investigate the impacts of varying architecture width on the generalization performance of final selected architectures by our NASI. We adopt the same search settings in Sec. Bec. with a varying architecture width (i.c., a varying number of initial channels) on CIFAR- 10 for the three search spaces of NAS-Bench- 1 1h Table shows results of the effectiveness of our NASI in NAS-Bench with varying architecture widths N: NASI consistently selects well- well-performing architectures and larger width (N 32) enjoys better search results. Hence, the infinite width assumption for NTK does not cause any empirical issues for our NASI.
shows
Shott
The effectiveness of NTK trace norm approximations. Since the trace norm of NTK is costly to evaluate, have provided our approximation it in Sec. 3.2 In this section, empirically validate the effectiveness of our NTK trace norm approximation. Specifically, we evaluate the Pearson correlation between our approximations (including the approximations using the of sample gradient norm in the first inequality of (II and the approximations using mini-batch gradient norm in (12)) and the exact NTK trace norm under varying batch size in the three search spaces of NAS- Sench-IShot.. The results are summarized in Table 7 The results confirm that our approximation reasonably good to estimate the exact NTK trace norm of different architectures by achieving a high Pearson correlation between our approximations and the exact NTK trace norm. Interestingly, larger batch size of mini-batch gradient norm generally achieves better approximation, and the sum of sample gradient norm achieves the best approximation, which can be explained by the possible approximation errors we introduced when deriving our [1] and
The impacts of batch size. Since we only adopt mini-bate bati-bbtchhh to approximate the NTK trace norm shown in Sec. 3.2 we further examine the impacts of varying batch size on the search results in the three search spaces of MAS-Bench-1Shool in this section. Table summarizes the search results. Interestingly, the results show that our approximation under varying batch sizes achieves comparable search results, further confirming the effectiveness of our approximations in select well-performing architectures.
The impacts of constraint v/ and penalty coefficient j.. Based on the analysis in Sec. 3.3 and the results in Appendix C.T] the choice of constraint y and penalty coefficient fa is thus non-trivial to select best-performing architectures since they trade off the complexity of final selected architectures and the optimization in their model training. In this section, we demonstrate their impacts on the generalization performance of the finally selected architectures and also the effectiveness of our fixed determination the constraint in detail. Notably, we adopt the same settings (including the search and training settings) as those in Appendix C.I on the DARTS search space, where vo in the fixed determination method introduced in Appendix B. is modified manually for the comparison.
24

---

Published as a conference paper at ICLR 2022
Table 8: Search with varying batch sizes in the three search spaces of NAS-Bench-IShone
Spaces b =
8
b b= 16
b b= 64
b = 128
S1
6.8
6.7
6.7=0.1
6.0
7.0=0..3
S2
6.9+-0.2
7.3++0.4
7.1=0.2
7.2+0.3
6.8++0.2
S3
7.0+0.3
6.6+0.2
6.7=0.2
6.6+0.1
7.1+0.2
V/
10
50
100
150
200
3.5
10.11
3.23
3.23
3.09
3.39
$..0
000
4.07
3.27
2.70
3.25
3.48
Test Error
4
4.07
3.16
2.78
3.19
3.20
4.
4
4.07
3.16
2.91
2.94
3.36
00000
3
Test Error (%)
2
2.70
3.30
3.90
4.50
1e2
(a) Joint impacts
(b) Individual impacts
Figure 6: The impacts of constraint v/ and penalty coefficient μ on the generalization performance of the final selected architectures by NASI: (a) their joint impacts, and (b) their individual impacts.
Figure 6 summarizes their impacts into two parts: the joint impacts in Figure a) and the individual impacts Figure Notably, in both plots, with the increasing of y the test error of the final selected architecture by NASI gradually decreases to a minimal and then increase steadily, hence further validating the existence of the trade-off introduced by and μ. Moreover, the final selected architectures with ==100 significantly outperform other selected architectures. This result thus supports the effectiveness of fixed determination method for in NASI. Interestingly, Figure 6(b) reveals a less obvious decreasing trend test error for compared with v, which hence further implies the greater importance of constraint v than penalty coefficient μ in terms of the generalization performance of the final selected architectures. Therefore, in our experiments, we conventionally set penalty coefficient μ=1 for compl-complexity search spaces and μ=2 for large-complexity search spaces as introduced in Appendix B.1
25


Reviews:
[{"review_id": "s6byv9yfPHy", "reviewer": "Reviewer_2dLC", "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": "Strengths:\nTraining-free NAS method is interesting and arouses a lot of interests in NAS field. Based on the unchanged characteristic of NTK, this paper utilizes NTK to evaluate the candidate architectures at initialization. NASI is well-supported by the theorem of NTK and achieves competitive results empirically.\n\nWeakness:\nThe main concern is the approximations in the paper. Since NTK has a certain assumption about the neural network, the unchanged characteristic may not be satisfied for some neural architectures. To calculate the trace norm of NTK and to solve the NAS problem efficiently, the authors both apply approximations here. Since three approximations are applied, the final results may have a large deviation.\n\nBesides, I also have the following questions about the paper\n1. NASI is based on the theory of NTK, which has the infinity-width assumption. Also, there are approximations in Section 3.2 and Section 3.3. Can you discuss the bound of the approximation? Or just verify it empirically?\n2. In Proposition 1, you discuss the upper bound of the training loss. However, when the architecture convergences, we focus on the minimum value of the training loss. I am confused about the claim “we can simply minimize the upper bound of $\\mathcal{L}_t$” below the Proposition 1. \n3. There are some other training-free NAS methods (e.g., [1]). Can you compare NASI with them in a fair manner?\n\n[1] Mellor, Joe, et al. \"Neural architecture search without training.\" International Conference on Machine Learning, 2021.\n", "summary_of_the_paper": "This paper proposes a training-free NAS method called NASI, which exploits the Neural Tangent Kernel (NTK) to characterize the performance of the candidate architectures at initialization. To alleviate the costly evaluation for NTK, the authors apply a similar form to gradient flow to approximate NKT. Moreover, they combined their NTK trick with gradient-based NAS algorithm via Gumbel-Softmax to solve NAS problem efficiently. The experiment results on various benchmarks illustrate the effect of NASI.", "summary_of_the_review": "NASI applies approximations for neural architecture search at initialization based on NTK. However, some of them are not convincing to me (see the main review above). If the authors can provide detailed explanations about that, I would consider raising my score. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WOmRwflE-MR", "reviewer": "Reviewer_iQzj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "+ The proposed method does not require the model training for architecture search, thus it is much more efficient than the previous NAS method.\n+ In addition to the efficiency, the proposed method can adapt to the label- and data-agnostic situations. \n\nConcerns:\n- Although NTK assumes infinite-depth DNNs, the proposed method does not seem to meet the condition. It would be nice to provide the reason why the proposed method can work. Also, I am interested in the lower bound of the network depth where the proposed method can work well.\n\n- The main concern about this method is whether the proposed method finds good architectures. Firstly, recent studies have claimed that NAS methods find architectures showing good performance but the rank of the found architecture is far from the best [Yu+, ICLR'20]. This comes from the fact that many candidates of CNN architectures in the search space can achieve good performance on the benchmark dataset such as CIFAR-10. In that sense, even though the proposed method achieves good performance on the benchmark datasets, I am wondering if the found architectures are really good or not. To check the rank of the architectures, it would be nice to use NAS-Bench-101 [Ying+, ICML'19]. Secondly, a recent study has argued that training protocols (e.g. data augmentation, training epochs) affect more on performance rather than search algorithms [Yang+, ICLR'20]. In fact, the training protocol affects a lot on the performance of DNNs, so I am wondering if the training protocol affects the estimation of the performance of candidate architectures by the proposed method or not.\n\n- The proposed method is inferior to another training-free method according to Table 4 in the appendix but shows better in the main paper. It would be nice to provide its cause and deeper analysis to better understand the proposed method.\n\n- Is it possible to directly apply the proposed method to a large dataset such as ImageNet?\n\n[Yu+, ICLR'20] Evaluating the Search Phase of Neural Architecture Search, ICLR'20.\n\n[Ying+, ICML'19] NAS-Bench-101: Towards Reproducible Neural Architecture Search, ICML'19.\n\n[Yang+, ICLR'20] NAS evaluation is frustratingly hard", "summary_of_the_paper": "This paper proposes a new training-free NAS method, where it is not necessary to optimize the weight parameters of target networks for architecture search. To achieve this, the paper exploits the capability of NTK for estimating the performance of candidate architectures at weight initialization. Thus, the proposed method can avoid network training during the search and achieve a much efficient architecture search. The experimental results show that the proposed method achieves competitive performance with existing methods and also can adapt to the label- and data-agnostic scenarios. ", "summary_of_the_review": "The proposed method shows promising results. My major concern is about the empirical and theoretical analysis (see concerns above). Hopefully, the authors can address my concern in the rebuttal period.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "N_6NaOOYZO0", "reviewer": "Reviewer_PjYZ", "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": "Pros\n++ The idea of using NTK as a network performance predictor for NAS is interesting, and the detailed method is non-trivial and plausible (including the relaxation and sampling to solve intractable optimization).\n++ The paper is well-written and easy to follow.\n++ The paper provides sufficient theoretical proof of its claim, including the assumptions made.\n++ The search costs are very appealing and the performance of the searched architectures are good.\n++ The proposed method can be data-/label-free, which is a good property that most NAS methods do not have.\n\nCons\n-- The performance of NASI is worse than TE-NAS on NAS-Bench-201 (Table 4).\n-- The advantage of NASI on ImageNet is not significant comparing to SOTA (Table 5).\n-- How about the results if NASI is directly applied on ImageNet, instead of transferring the best architectures searched on CIFAR-10?", "summary_of_the_paper": "This paper casts the problem of NAS into a training-free evaluation process by using neural tangent kernel (NTK). Specifically, the paper argues that the training dynamics and the performance of a DNN can be determined by the constant NTK of its linearization. Moreover, to efficiently evaluate the constant NTK of any network architectures, the paper proposes to use  the trac norm of NTK at initialization as an approximation. Using the NAS method proposed in this paper, one can search high-quality architectures with little GPU-hours. Interestigly, the proposed method is robust when applied in a data-/label-free search setting. Extensive experiments show that the searched networks have good performance and can be well-transferred to other datasets.", "summary_of_the_review": "In general, this paper is of good quality and exceed the bar of being accepted by ICLR. Although I have some minor concerns about the performance, I think the paper has great contributions to the NAS community and should be recommended.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5Ncnff6wRNW", "reviewer": "Reviewer_DrxZ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe targeting problem of searching neural architectures at initialization is important and promising.\nThe paper finds that such NASI is guaranteed to be label- and data-agnostic under mild conditions, which demonstrates that the searched architecture can be transferred to different datasets or tasks.\nThe retrained accuracy is promising and comparable or even better than other gradient-based searching methods.\n\n\nWeakness:\nThe authors claim competitive effectiveness on both CIFAR and ImageNet, while I only find CIFAR results in Table 1 and ImageNet-16-200 in Table 4 (also 16 and 200 are not defined).\nHow comparable are the achieved accuracy to other NAS methods, e.g., FBNetv3, EfficientNet?\n", "summary_of_the_paper": "This work proposes to search for good candidate neural architectures at initialization (NASI) so that we can completely avoid model training during the search.", "summary_of_the_review": "This work proposes to search for good candidate neural architectures at initialization (NASI) so that we can completely avoid model training during the search. The theoretical analysis is also provided to analyze the optimization via NTK tools.\n\nThe authors replied my previous major concern with clarity, so I raised my score to 6. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an efficient training-free NAS method, NASI, which exploits Neural Tangent Kernels (NTK)’s ability to estimate the performance of candidate architectures. Specifically, the authors provide a theoretical analysis showing that NAS can be realizable at initialization, and propose an efficient approximation of the trace norm of NTK that has a similar form to gradient flow, to alleviate the prohibitive cost of computing NTK. Since the method is training-free, NASI is also label- and data-agnostic. The experimental validation shows that NASI either outperforms or performs comparably to existing training-based and training-free NAS methods, while being significantly more efficient.

The below is the summary of pros and cons of the paper, after :

Pros
- The idea of using NTK to predict the performance of candidate neural architectures is both novel and promising, and the proposed analysis and efficient approximation are non-trivial.
- The paper provides sufficient theoretical proof of its claims, including the assumptions made.
- The method is highly efficient in terms of search cost, and the searched architectures obtain good performance on benchmark datasets.
- The method is data/label free and thus allows transfer architectures across tasks.
- The paper is well-written.

Cons
- There is no result on ImageNet obtained by directly applying NASI on it. 

The initial reviews were split, due to other concerns regarding whether the proposed method finds good architectures, missing comparison against certain training-free baselines, and some unclear descriptions. However, they were addressed away by the authors during the rebuttal period which led to a consensus to accept the paper. 

In sum, this is a strong paper that proposes a novel idea for training-free NAS, and the proposed method seems to be both effective, efficient, and generalizes well across tasks. One remaining concern is the computational cost of running the method on larger datasets, such as ImageNet, and I suggest the authors report the results and the running time in the final paper.

Another suggestion is to include discussion of, or comparison to other efficient NAS methods based on meta-learning, such as MetaD2A [Lee et al. 21], which is not training-free but is more efficient than the proposed NASI. 

[Lee et al. 21] Rapid Neural Architecture Search by Learning to Generate Graphs from Datasets, ICLR 2021
Decision: Accept (Poster)