Year: 2021

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 labeland data-agnostic under mild conditions, which guarantees the transferability of architectures selected by our NASI over different datasets.

heading: 1 INTRODUCTION
text: 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 et 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 to 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 a search space, a search algorithm, and a performance evaluation. Specifically, the search algorithm aims to select the best-performing neural architecture from the search space based on its evaluated performance via 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 (Dong & Yang, 2019; Pham et al., 2018; Liu et al., 2019; Xie et al., 2019) have trained a 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, but still require the training of the one-shot architecture. This naturally leads to the question whether NAS is realizable at initialization such that model training can be completely avoided during the search process? To the best of our knowledge, only a few efforts to date have been devoted to developing NAS algorithms without model training empirically (Mellor et al., 2020; 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 a Neural Tangent Kernel (NTK) (Jacot et al., 2018; Lee et al., 2019a) in being able to formally characterize the performance of infinite-wide DNNs at initialization, hence allowing the performance of candidate architectures to be estimated and realizing NAS at initialization. Specifically, given the estimated performance of candidate architectures by NTK, NAS can be reformulated into an
optimization problem without model training (Sec. 3.1). However, NTK is prohibitively costly to evaluate. Fortunately, we can approximate it1 with a 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 with Gumbel-Softmax (Jang et al., 2017; Maddison et al., 2017) (Sec. 3.3). Interestingly, NASI is shown to be label- and data-agnostic under mild conditions, which thus implies the transferability of architectures selected by NASI over different datasets (Sec. 4).
We will firstly empirically demonstrate the improved search efficiency and the competitive search effectiveness achieved by NASI in NAS-Bench-1Shot1 (Zela et al., 2020b) (Sec. 5.1). Compared with other NAS algorithms, 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. 5.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 also the guaranteed transferability achieved by our NASI.

heading: 2 RELATED WORKS AND BACKGROUND

heading: 2.1 NEURAL ARCHITECTURE SEARCH
text: A growing body of NAS algorithms have been proposed in the literature (Zoph & Le, 2017; Liu et 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, a one-shot architecture is introduced by Pham et al. (2018) to share model parameters among candidate architectures, thereby reducing the cost of model training substantially. Recent works (Chen et al., 2019; Dong & Yang, 2019; Liu et al., 2019; Xie et al., 2019; Chen & Hsieh, 2020; Chu et al., 2020) along this line have further formulated NAS as a continuous and differentiable 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 is still needed.
More recently, a number of algorithms have been proposed to estimate the performance of candidate architectures without model training. For example, Mellor et al. (2020) have explored the correlation between the divergence of linear maps induced by data points at initialization and the performance of candidate architectures heuristically. Meanwhile, Park et al. (2020) 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. (2021) have investigated several training-free proxies to rank candidate architectures in the search space, while Chen et al. (2021) intuitively adopt theoretical aspects in deep networks (e.g., NTK (Jacot et al., 2018) and linear regions of deep networks (Raghu et al., 2017)) to select architectures with a 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 al., 2020; Abdelfattah et al., 2021; Chen et al., 2021)), (b) guaranteeing the transferability of its selected architectures with its provable label- and data-agnostic search under mild conditions (compared with (Mellor et al., 2020; Park et al., 2020; Abdelfattah et al., 2021; Chen et al., 2021))) and (c) achieving SOTA performance in a large search space over various benchmark datasets (compared with (Mellor et al., 2020; Park et al., 2020; Abdelfattah et al., 2021)).

heading: 2.2 NEURAL TANGENT KERNEL (NTK)
text: Let a dataset (X ,Y) denote a pair comprising a set X of m n0-dimensional vectors of input features and a vector Y ∈ Rmn×1 concatenating the m n-dimensional vectors of corresponding output values, respectively. Let a DNN be parameterized by θt ∈ Rp at time t and output a vector
1More precisely, we approximate the trace norm of NTK.
f(X ;θt) ∈ Rmn×1 (abbreviated to ft) of the predicted values of Y . Jacot et al. (2018) have revealed that the training dynamics of DNNs with gradient descent can be characterized by an NTK. Formally, define the NTK Θt(X ,X ) ∈ Rmn×mn (abbreviated to Θt) as
Θt(X ,X ) , ∇θtf(X ;θt)∇θtf(X ;θt)> . (1) Given a loss function Lt at time t and a learning rate η, the training dynamics of the DNN can then be characterized as
∇tft = −η Θt(X ,X )∇ftLt, ∇tLt = −η ∇ftL>t Θt(X ,X )∇ftLt . (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., Θ0) can thus characterize the training dynamics and also the performance of infinite-width DNNs.
Lee et al. (2019a) have further revealed that, for DNNs with over-parameterization, the aforementioned training dynamics can be governed by their first-order Taylor expansion (or linearization) at initialization. In particular, define
f lin(x;θt) , f(x;θ0) +∇θ0f(x;θ0)>(θt − θ0) (3) for all x ∈ X . Then, f(x;θt) and f lin(x;θt) share similar training dynamics over time, as described formally in Appendix A.2. Besides, following the definition of NTK in (1), this linearization f lin achieves a constant NTK over time.
Given the mean squared error (MSE) loss defined as Lt , m−1 ‖Y − f(X ;θt)‖22 and the constant NTK Θt = Θ0, the loss dynamics in (2) above can be analyzed in a closed form while applying gradient descent with learning rate η (Arora et al., 2019):
Lt = m−1 ∑mn i=1(1− ηλi)2t(u>i Y)2 , (4)
where Θ0 = ∑mn i=1 λi(Θ0)uiu > i , and λi(Θ0) and ui denote the i-th largest eigenvalue and the corresponding eigenvector of Θ0, respectively.

heading: 3 NEURAL ARCHITECTURE SEARCH AT INITIALIZATION

heading: 3.1 REFORMULATING NAS VIA NTK
text: Given a loss function L and model parameters θ(A) of architecture A, we denote the training and validation loss as Ltrain and Lval, respectively. NAS is conventionally formulated as a bi-level optimization problem (Liu et al., 2019):
minA Lval(θ∗(A);A) s.t. θ∗(A) , arg minθ(A) Ltrain(θ(A);A) .
(5)
Notably, model training is required to evaluate the validation performance of each candidate architecture in (5). The search efficiency of NAS algorithms (Real et al., 2019; Zoph et al., 2018) based on (5) is 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 a one-shot architecture for model parameter sharing, such a one-shot architecture requires training and hence incurs the training cost.
To completely avoid this training cost, we exploit the capability of NTK for characterizing the performance of DNNs at initialization. Specifically, Sec. 2.2 has revealed that the training dynamics of an over-parameterized 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 1 using the trace norm of NTK at initialization, which 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 a L-layer DNN, we denote the output dimension of its hidden layers and the last layer as n1 = · · · = nL−1 = k and nL = n, respectively.
Proposition 1. Suppose that ‖x‖2 ≤ 1 for all x ∈ X and Y ∈ [0, 1]mn for a given dataset (X ,Y) of size |X | = m, a given L-layer neural architecture A outputs ft ∈ [0, 1]mn as predicted labels of Y with the corresponding MSE loss Lt, λmin(Θ0) > 0 for the given NTK Θ0 w.r.t. ft at initialization, and gradient descent (or gradient flow) is applied with learning rate η < λ−1max(Θ0). Then, for any t ≥ 0, there exists a constant c0 > 0 such that as k →∞,
Lt ≤ mn2(1− ηλ(Θ0))q + (6)
with probability arbitrarily close to 1 where q is set to 2t if t < 0.5, and 1 otherwise, λ(Θ0) , (mn)−1 ∑mn i=1 λi(Θ0), and , 2c0 √ n/(mk) ( 1 + c0 √ 1/k ) .
Its proof is in Appendix A.3. Proposition 1 implies that NAS can be realizable at initialization. Specifically, given a fixed and sufficiently large training budget t, in order to select the best-performing architecture, we can simply minimize the upper bound of Lt in (6) over all the candidate architectures in the search space. Here, Lt can be applied to approximated Lval since both strong theoretical (Mohri et al., 2018) and empirical (Hardt et al., 2016) justifications in the literature have shown that training and validation loss are generally highly related. Hence, (5) can be reformulated as
minA mn 2(1− ηλ(Θ0(A))) + s.t. λ(Θ0(A)) < η−1. (7)
Note that the constraint in (7) is derived from the condition η < λ−1max(Θ0(A)) in Proposition 1, and η and are typically constants2 during the search process. Following the definition of trace norm, (7) can be further reduced into
maxA ‖Θ0(A)‖tr s.t. ‖Θ0(A)‖tr < mnη−1 . (8)
Notably, Θ0(A) only relies on the initialization of A. So, no 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 to select architectures with a good trade-off between their model complexity and the optimization behavior in their model training. Particularly, architectures containing more model parameters will usually achieve a larger ‖Θ0(A)‖tr according to the definition in (1), which hence provides an alternative to measuring the complexity of architectures. So, maximizing ‖Θ0(A)‖tr leads to architectures with large complexity and therefore strong representation power. On the other hand, the complexity of the selected architectures is limited by the constraint in (8) to ensure a well-behaved optimization with a large learning rate η 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.1 will validate such trade-off. Interestingly, Chen et al. (2021) have revealed a similar insight of NAS to us.

heading: 3.2 APPROXIMATING THE TRACE NORM OF NTK
text: The optimization of our reformulated NAS in (8) requires the evaluation of ‖Θ0(A)‖tr for each architecture A in the search space, which can be obtained by
‖Θ0(A)‖tr = ∑ x∈X ∥∥∇θ0(A)f(x,θ0(A))∥∥2F , (9) where ‖ · ‖F denotes the Frobenius norm. However, the Frobenius norm of the Jacobian matrix in (9) is costly to evaluate. So, we propose to approximate this term. Specifically, given a γ-Lipschitz continuous loss function3 Lx (i.e., ‖∇fLx‖2 ≤ γ for all x ∈ X ),
γ−1 ∥∥∇θ0(A)Lx∥∥2 = γ−1 ∥∥∇fL>x ∇θ0(A)f(x,θ0(A))∥∥2 ≤ ∥∥∇θ0(A)f(x,θ0(A))∥∥F . (10)
The Frobenius norm ∥∥∇θ0(A)f(x,θ0(A))∥∥F can therefore be approximated efficiently by its lower bound given in (10) through automatic differentiation (Baydin et al., 2017).
Meanwhile, the evaluation of ‖Θ0(A)‖tr in (9) requires iterating over the entire dataset of size m, which incurs O(m) time. Fortunately, this incurred time can be reduced by parallelization over
2The same learning rate is shared among all candidate architectures in the search space for their model training during the search process in conventional NAS algorithms such as in (Liu et al., 2019).
3The γ-Lipschitz continuity is satisfied by widely adopted loss functions, as explained in Appendix A.3.
mini-batches. Let the set Xj denote the input feature vectors of the j-th randomly sampled mini-batch of size |Xj | = b. By combining (9) and (10),
‖Θ0(A)‖tr ≥ γ −1∑ x∈X ∥∥∇θ0(A)Lx∥∥22 ≥ bγ−1∑m/bj=1 ∥∥∥b−1∑x∈Xj ∇θ0(A)Lx∥∥∥22 , (11)
where the last inequality follows from Jensen’s inequality. Note that (11) provides an approximation of ‖Θ0(A)‖tr incurring O(m/b) time because the gradients within a mini-batch can be evaluated in parallel. Moreover, we further approximate the summation over m/b mini-batches in (11) by one single uniformly randomly sampled mini-batch Xj . Formally, under the definition of ‖Θ̃0(A)‖tr , ‖b−1 ∑ x∈Xj ∇θ0(A)Lx‖ 2 2 , our final approximation of ‖Θ0(A)‖tr becomes
‖Θ0(A)‖tr ≈ mγ−1‖Θ̃0(A)‖tr . (12)
This final approximation incurs only O(1) time and can effectively characterize the performance of neural architectures, as demonstrated in our experiments. Interestingly, a similar form called gradient flow (Wang et al., 2020) has also been applied in network pruning at initialization.

heading: 3.3 OPTIMIZATION AND SEARCH ALGORITHM
text: The approximation of ‖Θ0(A)‖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 a pre-defined constant ν , γnη−1, and a randomly sampled mini-batch Xj , by replacing ‖Θ0(A)‖tr with the approximation in (12), our reformulated NAS problem (8) can be transformed into
maxA [ ‖Θ̃0(A)‖tr − µF (‖Θ̃0(A)‖tr − ν) ] . (13)
Interestingly, (13) implies that the complexity of the final selected architectures is limited by not only the constraint ν (discussed in Sec. 3.1) but also the penalty coefficient µ: For a fixed constant ν, a larger µ imposes a stricter limitation on the complexity of architectures (i.e., ‖Θ̃0(A)‖tr < ν) in the optimization of (13).
The optimization of (13) in the discrete search space, however, is intractable. So, we apply some optimization tricks to simplify it: Following that of Pham et al. (2018); Liu et al. (2019); Xie et al. (2019), we represent the search space as a one-shot architecture such that the candidate architectures are subgraphs of this one-shot architecture. Next, instead of optimizing (13), we introduce a distribution pα(A) (parameterized by α) over the candidate architectures in this search space like that in (Zoph & Le, 2017; Pham et al., 2018; Xie et al., 2019), and optimize the expected performance of architectures sampled from pα(A):
maxα EA∼pα(A) [R(A)] s.t.R(A) , ‖Θ̃0(A)‖tr − µF (‖Θ̃0(A)‖tr − ν) . (14)
Then, we apply Gumbel-Softmax (Jang et al., 2017; Maddison et al., 2017) to relax the optimization of (14) to be continuous and differentiable using the reparameterization trick. Specifically, for a given α, to sample an architecture A, we simply have to sample g from p(g) = Gumbel(0,1) and then determine A using α and g (more details in Appendix B.3). Consequently, (14) can be transformed into maxα Eg∼p(g) [R(A(α, g))] . (15) After that, we approximate (15) based on its first-order Taylor expansion at initialization such that it can be optimized efficiently through a gradient-based algorithm. In particular, given the first-order approximation within the ξ-neighborhood of initialization α0 (i.e., ‖∆‖2 ≤ ξ):
Eg∼p(g) [R(A(α0 + ∆, g))] ≈ Eg∼p(g) [ R(A(α0, g)) +∇α0R(A(α0, g))>∆ ] , (16)
the maximum of (16) is achieved when
∆∗ = arg max ‖∆‖2≤ξ
Eg∼p(g) [ ∇α0R(A(α0, g))>∆ ] = ξ Eg∼p(g) [ ∇α0R(A(α0, g))∥∥Eg∼p(g)[∇α0R(A(α0, g))]∥∥2 ] .
(17)
Algorithm 1 NAS at Initialization (NASI) 1: Input: datasetD , (X ,Y), batch size b, steps T , penalty coefficient µ, constraint constant ν, ini-
The closed-form solution in (17) follows from the definition of dual norm and requires only a one-step optimization, i.e., without the iterative update of ∆. Similar one-step optimizations have also been adopted by other works (Goodfellow et al., 2015; Wang et al., 2020).
Unfortunately, the expectation in (17) makes the evaluation of ∆∗ intractable. Monte Carlo sampling is thus applied to estimate ∆∗ efficiently: Given T sequentially sampled g (i.e., g1, . . . , gT ) and let Gi , ∇α0R(A(α0, gi)), ∆∗ can be approximated as
∆∗ ≈ ξ T T∑ t=1 Gt max(‖G1‖2, . . . , ‖Gt‖2) . (18)
Note that the expectation ∥∥Eg∼p(g)[∇α0R(A(α0, g))]∥∥2 in (17) has been approximated by max(‖G1‖2, . . . , ‖Gt‖2) in (18) for the sample of g at time t, which is somehow inspired by AMSGrad (Reddi et al., 2018). Interestingly, this approximation is non-decreasing in t and therefore achieves a similar effect of learning rate decay, which may lead to a better-behaved optimization of ∆∗. With the optimal ∆∗ and α∗ = α0 + ∆∗, the final architecture can then be selected as A∗ , arg maxA pα∗(A), which completes our NAS at Initialization (NASI) algorithm detailed in Algorithm 1. Interestingly, this simple and efficient solution in (18) can already allow us to select architectures with competitive performances, as shown in our experiments (Sec. 5).

heading: 4 LABEL- AND DATA-AGNOSTIC SEARCH OF NASI
text: Besides the improved search efficiency by completely avoiding model training during the search, NASI can even guarantee the transferability of its selected architectures with its provable label- and data-agnostic search under mild conditions shown in Sec. 4.1 and Sec. 4.2, respectively. Particularly, with such provable label- and data-agnostic search, the final selected architectures by NASI on a proxy dataset are also likely to be selected and hence guaranteed to perform well on the target datasets under aforementioned mild conditions. So, the transferability of architectures selected via such labeland data-agnostic search can be guaranteed, as validated in Sec. 5 empirically.

heading: 4.1 LABEL-AGNOSTIC SEARCH
text: Our reformulated NAS problem (8) explicitly reveals that it can be optimized without the need of the labels from a dataset. Though the approximation of ‖Θ0(A)‖tr in (12) seemingly depends on the labels, (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) (and hence our optimization objective (13) that is based on this approximation) is label-agnostic, which justifies the label-agnostic nature of NASI. Interestingly, NAS algorithms with a similar label-agnostic search have already been developed in (Liu et al., 2020), which further implies the reasonableness of such label-agnostic search.
The label-agnostic approximation of ‖Θ0(A)‖tr is demonstrated in Fig. 1a using the three search spaces of NAS-Bench-1Shot1 with randomly selected labels. According to Fig. 1a, the large Pearson correlation coefficient (i.e., ρ ≈ 1) implies a strong correlation between the approximations with random vs. true labels, which consequently validates the label-agnostic approximation of ‖Θ0(A)‖tr. Overall, these empirical observations have verified that the approximation of ‖Θ0(A)‖tr and hence NASI based on the optimization over this approximation are label-agnostic, which will be further validated empirically in Sec. 5.3.

heading: 4.2 DATA-AGNOSTIC SEARCH
text: Besides being label-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 ‖Θ0(A)‖tr is data-agnostic under mild conditions. Proposition 2. Suppose that x ∈ Rn0 and ‖x‖2 ≤ 1 for all x ∈ X given a dataset (X ,Y) of size |X | = m, a given L-layer neural architecture A is randomly initialized, and the γ-Lipschitz continuous nonlinearity σ satisfies |σ(x)| ≤ |x|. Then, for any two data distributions P (x) and Q(x), denote Z , ∫ ‖P (x)−Q(x)‖ dx, as n1, . . . , nL−1 →∞ sequentially,
(mn)−1 ∣∣∣ ‖Θ0(A;P )‖tr − ‖Θ0(A;Q)‖tr ∣∣∣ ≤ n−10 ZD(γ)
with probability arbitrarily close to 1. D(γ) is set to L if γ = 1, and (1− γ2L)/(1− γ2) otherwise.
Its proof is in Appendix A.4. Proposition 2 reveals that for any neural architecture A, ‖Θ0(A)‖tr is data-agnostic if either one of the following conditions is satisfied: (a) Different datasets achieve a small Z or (b) the input dimension n0 is large. Interestingly, these two conditions required by the data-agnostic ‖Θ0(A)‖tr can be well-satisfied in practice. Firstly, we always have Z < 2 according to the property of probability distributions. Moreover, many real-world datasets are of high dimensions such as ∼103 for CIFAR-10 (Krizhevsky et al., 2009) and ∼105 for COCO (Lin et al., 2014). Since ‖Θ0(A)‖tr under such mild conditions is data-agnostic, NASI using ‖Θ0(A)‖tr as the optimization objective in (8) is also data-agnostic.
While ‖Θ0(A)‖tr is costly to evaluate, we demonstrate in Fig. 1b that the approximated ‖Θ0(A)‖tr in (12) is also data-agnostic using random data following the standard Gaussian distribution. Similar to the results using true vs. random labels in Fig. 1a, the approximated ‖Θ0(A)‖tr using random vs. true data are also highly correlated with a large Pearson correlation coefficient (i.e., ρ > 0.9). Interestingly, the correlation here is slightly smaller than the label-agnostic approximations in Fig. 1a, which implies that the approximated ‖Θ0(A)‖tr is more agnostic to the labels than data. Based on these results, the approximated ‖Θ0(A)‖tr is guaranteed to be data-agnostic. So, NASI based on the optimization over such a data-agnostic approximation is also data-agnostic, which will be further validated empirically in Sec. 5.3.

heading: 5 EXPERIMENTS

heading: 5.1 SEARCH IN NAS-BENCH-1SHOT1
text: We firstly validate the search efficiency and effectiveness of NASI in the three search spaces of NAS-Bench-1Shot1 (Zela et al., 2020b) on CIFAR-10. As the three search spaces are relatively

heading: Architecture Test Error (%) Params (M) Search Cost(GPU Hours) Search MethodC10 C100 C10 C100
text: small, a lower penalty coefficient µ and a larger constraint ν (i.e., µ=1 and ν=1000) are adopted to encourage the selection of high-complexity architectures in the optimization of (13). Here, ν is determined adaptively as shown in Appendix B.1.
Figure 2 shows the results comparing the efficiency and effectiveness between NASI with a oneepoch search budget and other NAS algorithms with a maximum search budget of 20 epochs to 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. Interestingly, the selected architectures by the one-epoch NASI achieve performances that are comparable to the best-performing NAS algorithms with 19× 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.

heading: 5.2 SEARCH IN THE DARTS SEARCH SPACE
text: We then compare NASI with other NAS algorithms in a more complex search space than NAS-Bench1Shot1, i.e., the DARTS (Liu et al., 2019) search space (detailed in Appendix B.2). Here, NASI
selects the architecture with a search budget of T=100, batch size of b=64 and µ=2. Besides, two different methods are applied to determine the constraint ν during the search process: the adaptive determination with an initial value of 500 and the fixed determination with a value of 100. The final selected architectures with adaptive and fixed ν are, respectively, called NASI-ADA and NASI-FIX (visualized in Appendix C.4), which are then evaluated on CIFAR-10/100 (Krizhevsky et al., 2009) and ImageNet (Deng et al., 2009) following Appendix B.4.
Table 1 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 a competitive generalization performance. Even when compared with the training-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-100, which demonstrates the transferability of the architectures selected by NASI over different datasets. Consistent results on ImageNet can be found in Appendix C.5.

heading: 5.3 LABEL- AND DATA-AGNOSTIC SEARCH
text: To further validate the label- and data-agnostic search achieved by our NASI as discussed in Sec. 4, 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.i.d. sampled from the standard Gaussian distribution. Both NAS-Bench1Shot1 and the DARTS search 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 the 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.

heading: 6 CONCLUSION
text: 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 implies the transferability of the final architectures selected by NASI over different datasets. With all these advantages, NASI can thus be adopted to select well-performing architectures for unsupervised tasks and larger-scale datasets efficiently, which to date remains challenging to other training-based NAS algorithms. Furthermore, NASI can also be integrated into other training-based one-shot NAS algorithms to improve their search efficiency while preserving the search effectiveness of these training-based algorithms.

heading: REPRODUCIBILITY STATEMENT
text: In order to guarantee the reproducibility of the theoretical analysis in our 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 and also the approximations used in our method on the final search results in Appendix C.6. To guarantee the reproducibility of the empirical results in our paper, we have provided our codes in the supplementary materials and detailed experimental settings in Appendix B.

heading: APPENDIX A THEOREMS AND PROOFS
text: We firstly introduce the theorems proposed by Jacot et al. (2018); Lee et al. (2019a), which reveal the capability of NTK in characterizing the training dynamics of infinite-width DNNs. Note that the these theorems follow the parameterization and initialization of DNNs in (Jacot et al., 2018). Our analysis based on these theorems thus also needs to follow such parameterization and initialization of DNNs.

heading: A.1 NEURAL TANGENT KERNEL AT INITIALIZATION
text: 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 InL as a nL × nL matrix with all elements being 1. Theorem 1 (Jacot et al. (2018)). For a network of depth L at initialization, with a Lipschitz nonlinearity σ, and in the limit as n1, · · · , nL−1 →∞ sequentially, the output functions fθ,i for i = 1, · · · , nL, tend (in law) to iid centered Gaussian processes of covariance Σ(L), where Σ(L) is defined recursively by
Σ(1)(x,x′) = 1
n0 x>x′ + β2 ,
Σ(L)(x,x′) = Eg∼N (0,Σ(L−1)) [σ(g(x))σ(g(x′))] + β2
such that the expectation is with respect to a centered Gaussian process f with covariance Σ(L−1). Theorem 2 (Jacot et al. (2018)). For a network of depth L at initialization, with a Lipschitz nonlinearity σ, and in the limit as n1, · · · , nL−1 →∞ sequentially, the NTK Θ(L) converges in probability to a deterministic limiting kernel:
Θ(L) → Θ(L)∞ ⊗ InL .

heading: Kernel Θ(L)∞ : Rn0×n0 → R is defined recursively by
text: Θ(1)∞ (x,x ′) = Σ(1)(x,x′) , Θ(L)∞ (x,x ′) = Θ(L−1)∞ (x,x ′)Σ̇(L)(x,x′) + Σ(L)(x,x′) ,
where
Σ̇(L)(x,x′) = Eg∼N (0,Σ(L−1)) [σ̇(g(x))σ̇(g(x′))]
such that the expectation is with respect to a centered Gaussian process f with covariance Σ(L−1) and σ̇ denotes the derivative of σ.

heading: A.2 TRAINING DYNAMICS OF INFINITE-WIDTH NEURAL NETWORKS
text: Given λmin(Θ) as the minimal eigenvalue of NTK Θ and define ηcritical , 2(λmin(Θ)+λmax(Θ))−1, Lee et al. (2019a) have characterized the training dynamics of infinite-wide neural networks as below.
Theorem 3 (Lee et al. (2019a)). Let n1 = · · · = nL−1 = k and assume λmin(Θ) > 0. Applying gradient descent with learning rate η < ηcritical (or gradient flow), for every x ∈ Rn0 with ‖x‖ ≤ 1, with probability arbitrarily close to 1 over random initialization,
sup t≥0 ∥∥ft − f lint ∥∥2 = O(k− 12 ) as k →∞ . Remark. For the case of L = 2, Du et al. (2019) have revealed that if any two input vectors of a dataset are not parallel, then λmin(Θ) > 0 holds, which fortunately can be well-satisfied for most real-world datasets. Though the training dynamics of DNNs only tend to be governed by their linearization at initialization when the infinite width is satisfied as revealed in Theorem 3, empirical results in (Lee et al., 2019a) suggest that such linearization can also govern the training dynamics of practical over-parameterized DNNs.

heading: A.3 PROOF OF PROPOSITION 1
text: With aforementioned theorems, especially Theorem 3, our Proposition 1 can be proved as below with an introduced lemma (Lemma 1). Lemma 1. Let loss function L (f(X ;θt),Y), abbreviated to L(ft), be γ-Lipschitz continuous within the domain V . Under the condition in Theorem 3, there exists a constant c0 > 0 such that as k →∞,∥∥L(ft)− L(f lint )∥∥2 ≤ c0γ√k with probability arbitrarily close to 1.
Proof. Since L(ft) is γ-Lipschitz continuous, for any v,u ∈ V , we have ‖L(v)− L(u)‖2 ≤ γ ‖v − u‖2 (19)
following the definition of Lipschitz continuity. Besides, under the condition in Theorem 3, Theorem 3 reveals that there exists a constant c0 such that as k →∞,∥∥ft − f lint ∥∥2 ≤ c0√k (20) with probability arbitrarily close to 1. Combining (19) and (20), we hence can finish the proof by∥∥L(ft)− L(f lint )∥∥2 ≤ γ ∥∥ft − f lint ∥∥2 ≤ c0γ√k as k →∞ . (21) Remark. The γ-Lipschitz continuity based on ‖ · ‖2 is commonly satisfied for widely adopted loss functions. For example, given 1-dimensional MSE L = m−1 ∑m i (xi−yi)2, let xi, yi ∈ [0, 1] denote the prediction and label respectively, the Lipschitz of MSE with respect to x , (x1, · · · , xm)> is 2. Meanwhile, given the n-class Cross Entropy with Softmax L = −m−1 ∑m i ∑n j yi,j log(pi,j) as the loss function, let pi,j ∈ (0, 1) and yi,j ∈ {0, 1} denote the prediction and label correspondingly, with∑ j yi,j = 1 and pi,j , exp(xi,j)/ ∑ j exp(xi,j) for input xi,j ∈ R, the Lipschitz of Cross Entropy with Softmax with respect to x , (x1,1, · · · , xi,j , · · · , xm,n)> is then 1.
Proof of Proposition 1. Note that the linearization f lin(x;θt) achieves a constant NTK Θt = Θ0 because its gradient with respect to θt (i.e., ∇θ0f(x;θ0)) stays constant over time. Given MSE as the loss function, according to the loss decomposition (4) in Sec. 2.2, the training dynamics of f lin(x;θt) can then be analyzed in a closed form:
L(f lint ) = 1
m mn∑ i=1 (1− ηλi)2t(u>i Y)2 , (22)
where Θ0 = ∑mn i=1 λi(Θ0)uiu > i , and λi(Θ0) and ui denote the i-th largest eigenvalue and the corresponding eigenvector of Θ0, respectively. With η < λmax(Θ0)−1 and λmin(Θ0) > 0, ηλi(Θ0) is then under the constraint that
0 < ηλi(Θ0) < λmax(Θ0)
λmax(Θ0) ⇒ 0 < ηλi(Θ0) < 1 . (23)
Hence, for the case of t ≥ 0.5, with 0 < 1− ηλi(Θ0) < 1 and λ(Θ0) , (mn)−1 ∑mn i=1 λi(Θ0),
mn∑ i=1 (1− ηλi(Θ0))2t ≤ mn∑ i=1 (1− ηλi(Θ0))
= mn(1− ηλ(Θ0)) . (24)
Further, given 0 ≤ t < 0.5, the scalar function y = x2t is concave for any x ∈ R≥0. Following from the Jensen’s inequality on this concave function,
mn∑ i=1 (1− ηλi(Θ0))2t ≤ mn
[ 1
mn mn∑ i=1 (1− ηλi(Θ0)) ]2t = mn(1− ηλ(Θ0))2t .
(25)
With bounded labels Y ∈ [0, 1]mn and the unit norm of eigenvectors ‖ui‖2 = 1,
(u>i Y)2 ≤ ‖ui‖22‖Y‖22 ≤ ‖Y‖22 ≤ mn . (26)
By introducing (24), (25) and (26) into (22), the training loss L(f lint ) can then be bounded by
L(f lint ) ≤ (mn) · 1
m mn∑ i=1 (1− λi(Θ0))2t
≤ mn2(1− ηλ(Θ0))q , (27)
where q is set to be 2t if 0 ≤ t < 0.5, and 1 otherwise. Following from Theorem 3, while applying gradient descent (or gradient flow) with learning rate η < λ−1max < ηcritical , 2(λmin + λmax)
−1, for all x ∈ X with ‖x‖ ≤ 1, there exists a constant c0 such that as k →∞, ∥∥ft − f lint ∥∥2 ≤ c0√k (28) with probability arbitrarily close to 1. Hence, f lint ∈ [ −c0 √ 1/k, 1 + c0 √ 1/k ]mn with ft ∈
[0, 1] mn. Within the extended domain ft ∈ [ −c0 √ 1/k, 1 + c0 √ 1/k ]mn for the MSE loss function,
‖∇ftL‖2 = 2
m ‖Y − ft‖2 ≤ 2 √ n/m ( 1 + c0 √ 1/k ) .
(29)
Hence, the MSE within this extended domain is 2 √ n/m ( 1 + c0 √ 1/k ) -Lipschitz continuous.
Combining with Lemma 1, L(ft) ≤ L(f lint ) + 2c0 √ n/(mk) ( 1 + c0 √ 1/k )
≤ mn2(1− ηλ)q + 2c0 √ n/(mk) ( 1 + c0 √ 1/k ) ,
(30)
which concludes the proof by denoting Lt , L(ft). Remark. ‖x‖2 ≤ 1 can be well-satisfied for the normalized dataset, which is conventionally adopted as data pre-processing in practice.

heading: A.4 PROOF OF PROPOSITION 2
text: According to Theorem 2, Θ0 , Θ(L) is determined by both Σ(L)(x,x) and Σ̇(L)(x,x) of all x ∈ X . We hence introduce Lemma 2 below regarding Σ(L)(x,x) and Σ̇(L)(x,x) to ease the proof of Proposition 2. Particularly, we set β = 0 for the β in Theorem 1 and Theorem 2 throughout our analysis. Note that this condition is usually satisfied by training DNNs without bias. Lemma 2. For a network of depth L at initialization, with the γ-Lipschitz continuous nonlinearity σ satisfying |σ(x)| ≤ |x| for all x ∈ R, given the input features x ∈ X ,
Σ(L)(x,x) ≤ n−10 x>x , Σ̇(L)(x,x) ≤ γ2 , where Σ(L)(x,x) and Σ̇(L)(x,x) are defined in Theorem 1 and Theorem 2, respectively, and β = 0.
Proof. Following from the definition in Theorem 1, Σ(L)(x,x) = Eg∼N (0,Σ(L−1)) [σ(g(x))σ(g(x))]
(a) ≤ Eg∼N (0,Σ(L−1)) [ g2(x) ] (b) = Σ(L−1)(x,x) ,
(31)
in which (a) follows from |σ(x)| ≤ |x| and (b) results from the variance of g ∼ N (0,Σ(L−1)). By following (31) from layer L to 1, we get
Σ(L)(x,x) ≤ Σ(1)(x,x) (a)= n−10 x>x , (32) where (a) is defined in Theorem 1.
Similarly, following from the definition in Theorem 2, Σ̇(L)(x,x) = Eg∼N (0,Σ(L−1)) [σ̇(g(x))σ̇(g(x))]
(a) ≤ Eg∼N (0,Σ(L−1)) [ γ2 ]
(b) = γ2 ,
(33)
in which (a) results from the γ-Lipschitz continuity of nonlinearity and (b) follows from the expectation of a constant.
Proof of Proposition 2. Notably, Theorem 2 reveals that in the limit as n1, · · · , nL−1 → ∞ sequentially, Θ(L) → Θ(L)∞ ⊗ InL with probability arbitrarily close to 1 over random initializations. We therefore only need to focus on this deterministic limiting kernel to simplify our analysis, i.e., let Θ0 = Θ (L) ∞ ⊗ InL . Particularly, given m input vectors x ∼ P (x) with covariance matrix ΣP and a L-layer neural architecture of n-dimensional output, For γ 6= 1, we have
(mn)−1‖Θ0‖tr = (mn)−1‖Θ(L)∞ ⊗ InL‖tr (a) = (mn)−1‖Θ(L)∞ ‖tr‖InL‖tr (b) = m−1‖Θ(L)∞ ‖tr (c) = Ex∼P (x) [ Θ(L)∞ (x,x)
] (d) = Ex∼P (x) [ Θ(L−1)∞ (x,x)Σ̇ (L)(x,x) + Σ(L)(x,x) ]
(e) ≤ Ex∼P (x) [ γ2Θ(L−1)∞ (x,x) + n −1 0 x >x ]
(f) = Ex∼P (x) [ γ2Θ(L−1)∞ (x,x) ] + n−10 ‖ΣP ‖tr ,
(34)
in which (a) derives from the property of Kronecker product, (b) follows from the notation nL = n and (c) results from the property of expectation and trace norm. In addition, (d) follows from the definition of Θ(L)∞ (x,x) in Theorem 2 and (e) is derived by introducing Lemma 2 into (d). Finally, (f) follows from the expectation and variance of P (x). By following (c-f) from layer L to 1, we can get
(mn)−1‖Θ0‖tr ≤ γ2(L−1)Ex∼P (x) [ Σ(1)(x,x) ] +
n−10 ‖ΣP ‖tr ( 1− γ2(L−1) ) ( 1− γ2 )−1
= n−10 ‖ΣP ‖tr ( 1− γ2L ) ( 1− γ2 )−1 .
(35)
Notably, (35) is derived under the condition that γ 6= 1. For the case of γ = 1, similarly, we can get (mn)−1‖Θ0‖tr ≤ n−10 L‖ΣP ‖tr . (36)
Note that with ‖x‖2 ≤ 1, we have ‖ΣP ‖tr = Ex∼P (x) [ x>x ] − Ex∼P (x) [x]
> Ex∼P (x) [x] ≤ Ex∼P (x) [ x>x ] ≤ 1 .
(37)
Given any two different distributions P (x) and Q(x), define Z = ∫ ‖P (x)−Q(x)‖ dx,4 we can construct a special probability density function P̃ (x) = Z−1‖P (x)−Q(x)‖ to further employee the bounds in (35) and (36). Specifically, for γ 6= 1, by combining (35) and (37), we can get
(mn)−1 ∣∣‖Θ0(P )‖tr − ‖Θ0(Q)‖tr∣∣ (a)= ∣∣∣∣∣Ex∼P (x) [Θ(L)∞ (x,x)]− Ex∼Q(x) [Θ(L)∞ (x,x)] ∣∣∣∣∣
(b) ≤ ∫ ‖P (x)−Q(x)‖Θ(L)∞ (x,x) dx
(c) ≤ n−10 Z‖ΣP ‖tr ( 1− γ2L ) ( 1− γ2 )−1 (d)
≤ n−10 Z ( 1− γ2L ) ( 1− γ2 )−1 ,
(38)
in which (a) follows from (c) in (34), (b) results from Cauchy Schwarz inequality and (c) is obtained by introducing inequality (35) and distribution P̃ (x). Finally, (d) is based on (37).
4We abuse this integration to ease notations.
Similarly, in the case of γ = 1, we can get (mn)−1 ∣∣∣ ‖Θ0(P )‖tr − ‖Θ0(Q)‖tr ∣∣∣ ≤ n−10 ZL , (39)
which concludes the proof. Remark. Note that ReLU is widely adopted as the nonlinearity in neural networks, which satisfies the Lipschitz continuity with γ = 1 and the inequality |σ(x)| ≤ |x|. Notably, many other ReLU-type nonlinearities (e.g., Leaky ReLU (Maas et al., 2013) and PReLU (He et al., 2015)) can also satisfy these two conditions.

heading: APPENDIX B EXPERIMENTAL SETTINGS
text: B.1 DETERMINATION OF CONSTRAINT ν AND PENALTY COEFFICIENT µ
As demonstrated in Sec. 3.1, constraint ν (derived from ‖Θ0(A)‖tr < mnη−1 in (8)) introduces a trade-off between the complexity of final selected architectures and the optimization behavior in their model training. This constraint ν hence is of great importance to our NASI algorithm. Though ν has already been pre-defined as ν , γnη−1 in Sec. 3.3, we still tend to take it as a hyper-parameter to be determined for the selection of best-performing architectures in practice. Specifically, in this paper, two methods are adopted to 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 fix ν with ν0 during the whole search process. Hence, ν0 is required to provide a good trade-off between the complexity of architectures and their optimization behavior in the search space. Intuitively, the expectation of architecture complexity in the search space can help to select architectures with medium complexity and hence implicitly achieve a 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, · · · ,AN ), and then determine ν0 before the search process by
ν = ν0 = N −1 N∑ i ‖Θ̃0(Ai)‖tr . (40)
Note that we can further enlarge ν0 in practice to encourage the selection of architectures with larger complexity.
The adaptive determination. We initialize ν with a relatively large ν0 and then adaptively update it with the expected ‖Θ̃0(A)‖tr of sampled architectures during the search process. Specifically, with sampled architectures A1, · · · ,At in the history, ν at time t (i.e., νt) during the search process is given by
νt = t −1 ( ν0 +
t−1∑ τ=1 ‖Θ̃0(Aτ )‖tr
) . (41)
We apply a relatively large ν0 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 to update νt, i.e., t > N .
Note that (13) in Sec. 3.3 further reveals the limitation on the complexity of final selected architectures by the penalty coefficient µ. Particularly, µ=0 indicates no limitation on the complexity of architectures. Following from the introduced trade-off between the complexity of final selected architectures and the optimization behavior in their model training by the constraint ν, for a search space with relatively larger-complexity architectures, a larger penalty coefficient µ (i.e., µ = 2) is preferred to search for architectures with relatively smaller complexity to ensure a well-behaved optimization with a larger learning rate η. On the contrary, for a search space with relatively smaller-complexity
architectures, a lower penalty coefficient µ (i.e., µ=1) is adopted to ensure the complexity and hence the representation power of the final selected architectures. Appendix C.6 provides further ablation study on the constraint ν and the penalty coefficient µ.

heading: B.2 THE DARTS SEARCH SPACE
text: 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 acyclic graph (DAG) of N nodes denoted by {x0, x1, . . . , xN−1}. To select the best-performing architectures, we instead need to select their corresponding cells, including the normal and reduction cell. Specifically, x0 and x1 denote the input nodes, which are the output of two preceding cells, and the output xN of a cell is the concatenation of all intermediate nodes from x2 to xN−1. Following that of SNAS (Xie et al., 2019), by introducing the distribution of architecture in the search space (i.e., pα(A) in (14)), each intermediate nodes xi (2 ≤ i ≤ N − 1) denotes the output of a single sampled operation oi ∼ pi(o) with
∑ o∈O pi(o) = 1 given a single sampled input xj ∼ pi(x) with j ∈ 0, · · · , i− 1 and∑i−1
j=0 pi(xj) = 1, where O is a predefined operation set. After the search process, only operations achieving the top-2 largest pi(o) and inputs achieving the top-2 largest pi(x) for node xi are retained. Each intermediate node xj hence connects to two preceding nodes with the corresponding selected operations.
Following from DARTS, the candidate operation set O includes following operations: 3 × 3 max pooling, 3×3 avg pooling, identity, 3×3 separable conv, 5×5 separable conv, 3×3 dilated separable conv, 5× 5 dilated separable conv. 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-pooling operation in between normal and reduction cell is applied to down-sampling intermediate features during the search process inspired by NAS-Bench-1Shot1 (Zela et al., 2020b).

heading: B.3 SAMPLING ARCHITECTURE WITH GUMBEL-SOFTMAX
text: Notably, aforementioned pi(o) and pi(x) for the node xi 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 pi(o) and pi(x) are parameterized by αoi,j and α x i,k respectively, with Straight-Through (ST) Gumbel Estimator (Jang et al., 2017), we can sample the single operation and input for the node xi (2 ≤ i ≤ N − 1) during the search process by
j∗ = arg max j
exp((αoi,j + g o i,j)/τ)∑
j exp((α o i,j + g o i,j)/τ)
k∗ = arg max k
exp((αxi,k + g x i,k)/τ)∑
k exp((α x i,k + g x i,k)/τ)
,
(42)
where goi,j and g x i,k are sampled from Gumbel(0, 1) and τ denotes the softmax temperature, which is conventionally set to be 1 in our experiments. Note that in (42), j ∈ [0, · · · , |O| − 1] and k ∈ [0, · · · , i− 1], which correspond to the |O| operations in the operation set O and the i candidate inputs for the node xi, 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 (42) for each nodes in the cells, the final sampled architecture can hence be determined.

heading: B.4 EVALUATION ON CIFAR-10/100 AND IMAGENET
text: 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 4 is located at 13-th cell of the final selected architectures and the number of initial channels is set to be 36. The final selected architecture are then trained via stochastic gradient descent (SGD) of 600 epochs with a learning rate cosine scheduled from 0.025 to 0, momentum 0.9, weight decay 3 × 10−4 and batch size 96 on a single Nvidia 2080Ti GPU. Cutout (Devries & Taylor, 2017), and ScheduledDropPath linearly decayed from 0.2 to 0 are also employed for regularization purpose.
Evaluation on ImageNet. We evaluate the transferability of the selected architectures from CIFAR10 to ImageNet. The architecture comprises of 14 cells (12 normal cells and 2 reduction cells). To evaluate in the mobile setting (under 600M multiply-add operations), the number of initial channels is 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 a batch size of 1024 on 8 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 a weight decay of 3× 10−5.

heading: APPENDIX C MORE RESULTS

heading: C.1 TRADE-OFF BETWEEN MODEL COMPLEXITY AND OPTIMIZATION BEHAVIOUR
text: In this section, we 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.1.
The trade-off in NAS-Bench-1Shot1. Specifically, Figure 3 illustrates the relation between test error and approximated ‖Θ0(A)‖tr of candidate architectures in the three search spaces of NASBench-1Shot1. Note that with the increasing of the approximated ‖Θ0(A)‖tr, the test error decreases rapidly to a minimum and then increase gradually, which implies that architectures only with certain ‖Θ0(A)‖tr (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 in 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 our reformulated NAS (8). Specifically, we apply NASI with the fixed determination of ν to select architectures in the the DARTS search
space over CIFAR-10, where ν0 in the fixed determination method introduced in Appendix B.1 is modified manually for the comparison. Besides, a 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 4(a), with the increasing of ν, the final selected architectures by NASI contain more parameters and hence achieve larger complexity. Meanwhile, the final selected architecture with ν=10 enjoys a faster convergence rate in the first 50 epochs, but a poorer generalization performance than the one with ν= 200. Interestingly, the final selected architecture with ν=100 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 in their model training. However, the trade-off introduced by the penalty coefficient µ shown in Figure 4(b) is hard to be observed, which indicates that the constraint ν is of greater importance than the penalty coefficient µ in terms of the trade-off between the complexity of architectures and their optimization behavior. Interestingly, Figure 4(b) can still reveal the slower convergence rate and poorer generalization performance caused by the selection of architecture with relatively larger complexity, i.e., µ=1.

heading: C.2 COMPARISON TO OTHER TRAINING-FREE METRICS
text: We compare our methods with other training-free NAS methods using both the Spearman correlation and the Kendall’s tau between the training-free metrics and the test accuracy on CIFAR-10 in the three search spaces of NAS-Bench-1Shot1. We adopt one uniformly randomly sampled mini-batch data to evaluate these two correlations and apply the same implementations of these training-free NAS methods in (Abdelfattah et al., 2021) for the comparison. Table 3 summarizes the comparison, where the results of our metric are reported under the constraint in (8). 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.

heading: Architecture Test Accuracy (%) Search Cost(GPU Sec.) Search MethodC10 C100 IN-16-120

heading: C.3 SEARCH IN NAS-BENCH-201
text: 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 NAS-Bench-201 (Dong & Yang, 2020) on CIFAR-10/100 (C10/100) and ImageNet-16-200 (IN-16-200) 5. Table 4 summarizes the comparison. Note that the baselines in Table 4 are obtained from TE-NAS (Chen et al., 2021) paper. Notably, compared with training-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, achieves a relatively improved test accuracy than our NASI (T ), our NASI with a search budget of T = 30s is 50× more efficient than TE-NAS and is able to achieve compelling test performance on all the three 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-16-120) search results with 12× lower search cost compared with TE-NAS.

heading: C.4 ARCHITECTURES SELECTED BY NASI
text: The final selected cells in the DARTS search space (i.e., 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. 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 our 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 1 and Table 5. A possible explanation is that our NASI algorithm provides a 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 in (Shu et al., 2020). Note that the final selected cells in NASI-FIX and NASI-ADA are of great similarity to each other, which hence implies that the adaptive determination and the fixed determination of constraint ν share similar effects on the selection of final architectures.

heading: C.5 EVALUATION ON IMAGENET
text: 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 expertdesigned architecture ShuffleNet 2×(v2), NAS-based architecture MnasNet-92 and DARTS by a large margin, and are even competitive with best-performing one-shot NAS algorithm DARTS-.
5ImageNet-16-200 is a down-sampled variant of ImageNet (ImageNet16×16) (Chrabaszcz et al., 2017).
Notably, while achieving comparable generalization performance, NASI is more efficient than TENAS (ImageNet) by directly transferring the architectures selected on CIFAR-10 to ImageNet based on its provable transferability in Sec. 4. Above all, the results on ImageNet further confirm the transferability of the architectures selected by NASI to larger-scale datasets.

heading: C.6 ABLATION STUDY AND ANALYSIS
text: The impacts of architecture width. As our theoretically grounded performance estimation of neural architectures relies on an infinite width assumption (i.e., n → ∞ in Proposition 1), we 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. 5.1 but with a varying architecture width (i.e., a varying number of initial channels) on CIFAR-10 for the three search spaces of NAS-Bench-1Shot1. Table 6 shows results of the effectiveness of our NASI in NAS-Bench-1Shot1 with varying architecture widths N : NASI consistently selects well-performing architectures and a larger width (N = 32) enjoys better search results. Hence, the infinite width assumption for NTK does not cause any empirical issues for our NASI.
The effectiveness of NTK trace norm approximations. Since the trace norm of NTK is costly to evaluate, we have provided our approximation to it in Sec. 3.2. In this section, we empirically validate the effectiveness of our NTK trace norm approximation. Specifically, we evaluate the Pearson correlation between our approximations (including the approximations using the sum of sample gradient norm in the first inequality of (11) 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 NASBench-1Shot1. The results are summarized in Table 7. The results confirm that our approximation

heading: Spaces Mini-batch Sum

heading: S1 0.74 0.80 0.84 0.83 0.85 0.86 0.88

heading: S2 0.82 0.87 0.90 0.89 0.91 0.91 0.92

heading: S3 0.66 0.74 0.81 0.79 0.82 0.84 0.87
text: is 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, a larger batch size of mini-batch gradient norm generally achieves a 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 (11) and (12).
The impacts of batch size. Since we only adopt a mini-batch 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 NAS-Bench-1Shot1 in this section. Table 8 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 ν and penalty coefficient µ. Based on the analysis in Sec. 3.3 and the results in Appendix C.1, the choice of constraint ν and penalty coefficient µ 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 on the constraint ν in detail. Notably, we adopt the same settings (including the search and training settings) as those in Appendix C.1 on the DARTS search space, where ν0 in the fixed determination method introduced in Appendix B.1 is modified manually for the comparison.
Figure 6 summarizes their impacts into two parts: the joint impacts in Figure 6(a) and the individual impacts in Figure 6(b). Notably, in both plots, with the increasing of ν or µ, 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 our fixed determination method for ν in NASI. Interestingly, Figure 6(b) reveals a less obvious decreasing trend of test error for µ compared with ν, which hence further implies the greater importance of constraint ν 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 small-complexity search spaces and µ=2 for large-complexity search spaces as introduced in Appendix B.1.

Review summaries:
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. 

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.

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.