Generalization Properties of NAS under Activation and Skip Connection Search
Authors: Zhenyu Zhu
Fanghui Liu
Grigorios Chrysos
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: neural architecture search
convergence
generalization
neural tangent kernel

Abstract: Neural Architecture Search (NAS) has fostered the automatic discovery of state-of-the-art neural architectures. Despite the progress achieved with NAS, so far there is little attention to theoretical guarantees on NAS. In this work, we study the generalization properties of NAS under a unifying framework enabling (deep) layer skip connection search and activation function search. To this end, we derive the lower (and upper) bounds of the minimum eigenvalue of the Neural Tangent Kernel (NTK) under the (in)finite-width regime using a certain search space including mixed activation functions, fully connected, and residual neural networks. We use the minimum eigenvalue to establish generalization error bounds of NAS in the stochastic gradient descent training. Importantly, we theoretically and experimentally show how the derived results can guide NAS to select the top-performing architectures, even in the case without training, leading to a train-free algorithm based on our theory. Accordingly, our numerical validation shed light on the design of computationally efficient methods for NAS. Our analysis is non-trivial due to the coupling of various architectures and activation functions under the unifying framework and has its own interest in providing the lower bound of the minimum eigenvalue of NTK in deep learning theory.

Generalization Properties of NAS under Activation and Skip Connection Search
Zhenyu Zhu,
Fanghui Liu,
Grigorios Chrysos,
Volkan Cevher
EPFL, Switzerland
[ffirst name]. [surname]] @aapfammm@@@ppl.....e @epfl.ch
Abstract
Neural Architecture Search (NAS) has fostered the automatic discovery of state- of-the-art neural architectures. Despite the progress achieved with NAS, so far there is little attention to theoretical guarantees NAS. In this work, we study the generalization properties of NAS under a unifying framework enabling (deep) layer skip connection search and activation function search. To this end, we derive the lower (and upper) bounds of the minimum eigenvalue of the Neural Tangent Kernel (NTK) under the (in)finite-width regime using a certain search space including mixed activation functions, fully connected, and residual neural networks. We use the minimum eigenvalue establish generalization error bounds of NAS in the stochastic gradient descent training. Importantly, we theoretically and experimentally show how the derived results can guide NAS to select the pop-performing architectures, even in the case without training, leading to train- free algorithm based on our theory. Accordingly, our numerical validation shed light the design of computationally efficient methods for NAS. Our analysis is non-trivial due to the coupling of various architectures and activation functions under the unifying framework and has its own interest in providing the lower bound of the minimum eigenvalue NTK in deep learning theory.
1 Introduction
Neural Architecture Search (NAS) Zoph and Le 2017 is powerful technique that enables the automatic design of neural architectures. NAS defines set of operations (referred as the search space), that include various activation functions and layer types, or potential connections among layers [Elsken al. 2019 Ren al. 2021]. Optimization over the search space returns the optimal architecture as a subset of the possible combinations of operations. NA. obtains state-of srate-of-thee of-the-art
results image recognition [Liu al. 2019a Ding al. 2020 Zhang al. 2019 Chen al. 2019)
or can be used to further improve architectures defined by a human expert [Tn and Le 2019 The spectacular results obtained by NAS have led significant interest in the community further
improve the NAS algorithms, the search space etc. However, to date little focus has been provided in the following question: Can NAS achieve generalization guarantees similar to a typical neural network?
Neural tangent kernel (NTK) analysis [Jacot et al. 2018 is powerful method for analyzing
the optimization and the generalization deep networks Allen-Zhu et al. 2019 Cao and Gu 2019
Chen et al. 2020a Arora al. 2019a The minimum eigenvalue of NTK has been used in previous
work to demonstrate the global convergence of gradient descent, such as two-layer networks [Du
al. 2019b), and deep networks with polynomially wide layers [Allen-Zhu al. 2019). Besides,
the minimum eigenvalue of NTK is also used to prove generalization bounds Arora et al. 2019a and
In the sequel, we interchangeably refer to NAS as the "architecture obtained from NAS" or the framework design the neural architecture.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

memorization [Montanari and Zhong 2020]. However, previous work mainly focuses on limited set of architectures, e.g., fully-conneetee (FC) neural networks [Allen-Zhu et al. 2018 Bartlett et al.) 2017] or residual neural networks [He et al. 2016 Huang et al. 2020]. in which single activation function is used throughout the network. These off-the-shelf theoretical results cannot be directly applied to analyze the rich search space (of NAS) that is covering various/mixed architectures and
parameters. That makes the non-trivial analysis on NAS worth of study on its own right.
The recent work Of'Oymak et al. [2021] is the first work to provide generalization guarantees on a related problem, ie., activation functions search. The study provides generalization results on two-layer networks relying on the minimum eigenvalue with a strictly larger than zero assumption, ie., Amin (K > for the NTK matrix K.
In this work, we introduce the first theoretical guarantees for multilayer NAS where the search space includes activation functions and skip connections. We study the upper/lower bound of the minimum eigenvalue of NTK (in the (in)finite regime) under mixed activation functions and architectures which evade the minimum eigenvalue assumption Oyyak et al. [202]]. Then, we provide optimization and generalization guarantees of deep neural networks (DNNs) equipped with NAS. Our results indicate that the minimum eigenvalue estimation can act as a powerful metric for NAS. This method, called Eigen-NAS, is train-free, but still effective with experimental validation when compared to Formally, our
recent promising algorithms [Xu et al. 2021 Chen et al. 2021, Mellor et al. 2021 main contribution and findings are summarized below:
i) We build a general theoretical framework based NTK for NAS with search on popular activation functions in each layer, fully-connected, and skip connections. We derive the NTK formula of these architectures in the (in)finite-widrs regime under the unifying framework.
ii) We derive the upper and lower bounds of the minimum eigenvalue of the NTK under the (in)finite- width regime for the considered architectures. We introduce new technique to ensure the probability of concentration inequality remains positive, Our analysis highlights how the upper and lower bounds differs under activation function search and skip connection search and can guide NAS.
iii) We establish a connection between the minimum eigenvalue and generalization of the searched DNN trained by stochastic gradient descent (SGD). Our theoretical results show that the generalization performance largely depends on the minimum eigenvalue of NTK for NAS, which provides theoretical guarantees for the searched architecture
iv) Our theoretical results are supported by thorough experimental validations with the following findings: 1) our upper and lower bounds on the minimum eigenvalue largely depend on the activation function in the first layer rather than the activation functions in deeper layers. 2) The applied NAS algorithm always picks up ReLU (Rectified Linear Unit) and LeakyReLU in the optimal architecture, which coincides with our theory that predicts ReLU and LeakyReLU achieve the largest minimum cigenvalues. 3) The skip connections are required in each layer under our not very large DNNs. Furthermore, our experimental evidence on Eigen-NAS indicates that the minimum eigenvalue is a promising metric to guide NAS (without training) as suggested by our theory.
Technical challenges. The technical challenges of this paper mainly focus how to analyze ac- tivation functions with different properties and skip connections under a unifying framework. This work is non-trivial; previous works mainly focus on the ReLU activation function [Nguyen et al.) 2021 Cao and Gu 2019 Allen-Zhu et al.] 2019] in optimization and generalization of a single fully- connected neural network. Their proofs heavily depend on the properties of ReLU, e.g., homogeneity and (z) = Re)LL((r) which are invalid when other commonly activation functions, e.g.. Tanh, Sigmoid, and Swish, are used. This problem becomes harder when mixed activation functions and residual connections are considered. To tackle these technical challenges, we develop the following techniques: a) to handle the non-homogeneous property of Tanh, Sigmoid, and Swish, we develop a new integral estimation approach for the minimal eigenvalue estimation. b) To establish the connection between the minimum eigenvalues of NTK and generalization errors, we use the Lipschitz continuity avoid the special property of ReLU. More importantly, we introduce new tech- nique (Yaskov 2014] to replace Gershgorin circle theorem for minimum eigenvalue estimation, which avoids concentration inequalities with negative probability in some certain cases (Nguyen et al. 2021
2

---

2 Related work
Network architecture search (NAS): The idea of NAS stems from Zoph and Le [2017], while the
idea of cell search, i.e., searching core building blocks and composing them together, emerged in Zoph et al. [0188]. The earlier literature used discrete optimization techniques for obtaining the architecture. DARTS Liu al. 2019b] considers NAS as a continuous bi-level optimization task. Recent variants of DARTS [Xu et al. 2019 Wu et al. 2019) and several train-free methods [Mellor al. 2021 Chen et al. 2021 Xu al. [021] have demonstrated success reducing the search time or improving the search algorithm. However, the aforementioned works have not provided generalization guarantees for the optimal architecture.
Optimization and generalization of DNNs via NTK: In the NTK framework [Jacot et al. 2018 Du
al. 2019a| Chen et al., 2020b]. the training dynamics of (in)finite-width networks can be exactly
characterized by kernel tools. Leveraging NTK facilitates studies on the global convergence of
GD Allen-Zhhh et al. 2019 Du et al. [2019a] Nguyen [202] in DNNs via the minimum eigenvalue
of NTK. In fact, it also controls the generalization performance of DNNs Du et al. 2019b Cao and
Gu 2019
Allen-Zhu al. 2018), which is further studied in Bietti and Bach 2021
3 Problem Settings
In this section we introduce the problem setting of our NAS framework based on the search space and algorithm (search strategy) for our paper.
Let X C Id be compact metric space and Y C R. We assume that the training set Dir {(x,, yr) 3:)} 1.
drawn from a probability measure on X Y, with its marginal data distribution denoted by Dx. The goal of supervised learning task is to find hypothesis (i.e., a neural network used this work) f -> Y such that (a; W) parameterized by W a good approximation of the label y E Y corresponding to new sample x E X. In this paper, we consider the classification task, evaluated by minimizing the expected risk
min l (W): == E( (lyf(: W)l W
where {[y[(2;; W)] is the classification loss E(-) as a surrogate of the expected 0-1 loss 6 E(x.,)>-(1 [1 (ys (ax; W) < 0}]. In this paper, we employ the cross-entropy loss, which defined as 100 + exp(-xp) -))]-
Notation: For an integer L., we use the shorthand [L.] = 21. L}. The multivariate standard Gaussian distribution is (V Ia) with the zero-mean vector 0 and the identity-variance matrix Ig. We denote the direct sum by @. We follow the standard Bachmann-Landau notation in complexity theory e.g., O, o. Ω2 and θ for order notation.
3.1 Neural Networks and Search Space
In this work, we consider particular parametrization of f as a deep neural network (DNN) with depth T. (I. > which includes the fully-connected (FC) neural networks setting and the residual neural networks setting, and various activation functions in each layer. This enables a quite general NAS setting. Formally, we define a singlc-output DNN with the output fi()) in each layer
{
a Tf (W,x) (l. fi (x)) ta 1 (WL. fz)
1=
1=
f((x)=
(1)
2 1 (= L,
where the weights of the neural networks are W mxdd W. E Rm 1 Wr E RT. The binary parameter aj is for layer search, and the activation function is (1()). The neural network output is f(; W) = (x)
2, ..... L 1 and
Architecture search: A binary vector a [a,, 022 0z 2 2 represents the skip connections,
where the o E (0. 1) in Equation (1) indicates whether there a skip connection in the I-th layer. Notice that we unify FC and residual neural networks under the same framework.
*Our results hold for the L = 2 setting corresponding to one-hidden layer neural network with slight modifications notation, focus L 3 for simplicity.
3

---

Table I: Formula of different activation functions, definitions of relevant constants and some intermediate results.
ReLU
LeakyReI.UU
Sigmoid "I
Tanh ?
Swish
Formula
max(0,
max(na, E (0,
14e-a
40
Ite-
(((
1+ 17
1/8
2
Pa(ar)
1
1+ n)
1/8 (1)
2
1.22
(o))
1
1 + 17
(t)
1/2
We consider the integral fs(y) - v2rg e To f'ssmmoia (z)) dx. We add -1/2 in
dr.
Sigmoid ensure fisigmoid (0) facilitates theoretical analysis. The parameter is t == 3(1 + n7") + +))
)/) 1-3
The definition fr similar to [s by using the Tanh function.
Activation function search: We select five representative activation functions defined by Fo (ReLU, LeaklyReLU, Sigmoid, Tanh, Swish} used in Equation (I). that can be bounded, un- bounded, smooth, non-smooth, monotonic, or non-monotonic, as reported in Table [ We define = |0,, 02 , _L-' with ai Fo for any / E [T. - 1] as the indicator to show which activation function is selected in each layer. Our NAS framework allows for a different activation function in each layer, which enlarges the search space.
In our setting, we conduct the architecture search and the skip connection search independently, and accordingly, our search space is defined as the direct sum of them
W R 4-2
Fl-1 mRaxd x (Rm* R'),
where W : (a. W for skips and selected activation functions for all layers.
...... W,. E W represents the collection of weight matrices and indicator
3.2 Algorithm (Search Strategy)
The search strategy is the core part in NAS to pick up the optimal architecture from the search space. Here we build a general Algorithm| I combining the search strategy for NAS (the first part) and the subsequent neural network training by SGD (the second part).
We firstly utilize a typical NAS algorithm, e-g., random search WS Li and Talwalkar, 2020 or DARTS to search skip connections and activation functions independently, which results in the optimal architecture {oo)) I--1 (a {=²} with the max probability. see sec. 5.1 for details. In particular, Algorithm| [ also allows for the guidance of NAS in train-free strategy via some specific
metrics, c.g., the minimum eigenvalue of NTK (and its variant), see our Eigen-NAS method in sec. 5.2
Then, conduct neural network training the selected architecture by SGD. For ease of theoretical analysis, we employ the constant step-size SGD with one epoch and randomly choose the weight parameters during all the iterations, which is commonly used in deep learning theory [Cao and Gu 2019 Zou et al. 2019].
4 Main result
In this section, we state the main theoretical results. We present the assumptions used in our proof in sec. 4.1 Then sec. 4.2 we provide the recursive form of NTK for DNNs defined by Equation (T) with mixed activation functions and skip connections. The upper and lower bounds of the minimum
eigenvalue of NTK in the infinite and fiite--wddth setting is given in sec. 4.3 and 4.4 respectively.
Finally, in sec. 4.5 we connect the minimum eigenvalue of NTK and the generalization error bound
of DNNs under these search schemes. The proofs our theoretical results presented in this section are deferred to Appendix B C and respectively.
4.1 Assumptions
We make the following assumptions data and activation functions. Our assumptions are frequently employed in the literature as we highlight below.
Assumption 1. We assume that the data satisfy ||0||| = 1.
This algorithm directly outputs the final optimal architecture and optimal parameters.

---

Algorithm 1: SGD for training DNNs by NAS
Input: search space S, data Dr, (1) 1/) 1/) J. step size y and
Flag Fmathdd {EigenNAS, DARTS,
// conduct NAS algorithme
if FlaganaNNs Ei gegNAS then Guide NAS from S by our Eigen-NAS algorithm.
else Flagcuitesss DARTS then
Search neural network architectures from S using the DARTS algorithm. end if
Output the optimal architecture (( (a E 8 with max probability.
do neural network training via SGD
Gaussian initialization: w( ~ (0. E [L]
Construct the neural network ((; W, (1) based on (
for i = 1 to N do
( = W 7 (w((J(x; ( wy))
end for
Output Randomly choose W uniformly from (W().... W(N}.
Assumption 2.
The activation function o IR + R satisfies E L2 x2 L (R, g) denotes the square integrable function.
e- / where
Assumption We further assume that æ is isotropic. i.e. R|xx"] Ta/d, where the coefficient 1 1/d is to satisfy Assumption at the same time.
Remark: The first assumption on normalized data is commonly used in practice and theory on over-
parameterized neural networks [Du et al. 2019b Allen-Zhu et al. 2019 Oymak and Soltanolkotabi
2020 Malach et al. 2020]. The second assumption is general as the studied activation functions in
Table satisfy it The third assumption is standard in statistics and machine learning |Vershynin 2018
Hastie et al. 2022, Klimovsky 2012 Yaskov 2014). covers Gaussian data, and data uniformly
spread on the sphere, commonly used deep learning theory (Mei et al. 2021 Ghosh et al. 2022
4.2 Recursive NTK for DNNs defined by Equation [
Recall that NTK [Jaoot et al. 2018 under the infinite-width setting (m - oo) is:
k(O) (x. = Ew 0f(x: W)
Of(;:W)
aW
aW
where the NTK matrix for residual networks derived by the following regular chain rule. [2, L.). denote
Lemma 1. For any [3, L] and
G = - 12) (2) - 1o Xw)) I oz (V J A (( + a1-2A (1-1)
(0)) 20 1--1
(6) 2 (VA A0-1 (V
Then the NTK for residual networks defined in Equation can be written
k(4) G Σ
G (((+z) (G((+2) o (G(L) +
1=1
Remark: (i) Our NTK formula of ResNet differs from the one of Tirer et al. 2022 Huang et al.
2020). Belfer al. (02T] in two critical ways: 1) each skip-layer our model skips one fully- connected layer and one activation function, as opposed to the two-layer skip of previous works, 2) our formulation does not require every layer have a parallel skip connection, which increases flexibility of the network. Those differences also result in a different NTK matrix. (ii) Our NTK formulation covers different activation functions, and we adopt the same initialization (coefficient) them to ensure fair/equal search in our NAS framework.
5

---

Lemma ! covers both FC and residual neural networks, which facilitates the analysis of minimum eigenvalue of NTK under the unifying framework. If a, 0 for / E [L 1], our NTK formulation for residual neural networks degenerates to that of a fully-connected neural network, and A' and G' become equal.
4.3 Minimum Eigenvalue of NTK for infinite-width
We are ready to state the main result the infinite-width neural network. We provide the upper and lower bounds of minimum eigenvalue of NTK for infinite-width neural network mixed with five different activation functions. The main differences between different activation functions illustrated in T
Theorem 1. For DNN defined by Equation (1) and not very large L, let KLL) be the limiting Then, under Assumptions and 3
NTK recursively defined in Lemmal I. probability at least e 0, we have
when N 2 Q(dd),, with
Amin
A (K(1)) 2 2p1(1))
II p=3
Bs(op-1) + (
1 N
[-1
Amin K
B1(01-1) II (Bi(0p-1) app2)))))pp22))) p=2
II (32lop-1) + p=1+1
1=1
where μn (0) is the 1-st Hermite coefficient of the first layer activation function, and B1, 32, Bo are three constants on various activation ficooonffffiiii functions defined in Table 7
Remark: A not very large depth, c.g., L S. 10, is often sufficient for the search phase in practical implementations [Liu al. 2018 Dong al. 202T]. In addition, existing NAS algorithms such as DARTS tend to have architectures with wide and shallow cell structure as suggested by [Shu et al. [2020] Theorem [ shows the upper and lower bounds the minimum eigenvalue of NTK under the mix of activation functions and skip connections. The following conclusions can be drawn from our result:
1. The bounds of the minimum eigenvalue depend significantly on the depth of the network L, the skip connections via ap, that makes the minimum eigenvalue increasing fast L and the number of skip connections increase. Besides, the minimum eigenvalue is also effected by activation functions via B1, 82, 33. Nevertheless, the lower bound is independent of B1 and 82.
2. Different activation functions lead to different tendency (increase decrease) Amin (K (*)).
As the depth increases, the lower bound Amia (K(4)) under ReLU remains unchanged, increases under LeakyReLU, and decreases when Sigmoid, Tanh or Swish applied, which brings in new findings when compared to the ReLU-network analysis of al. [2021]. For the upper bound for Amin ( ( (K),),
can our results are positively correlated with the depth L.
One can see that μu (a1) only related to the activation function of the first layer, which implies that the activation function in the first layer is very important as Amin Amin((())) (K(L) largely depends on
4.4 Minimum Eigenvalue of NTK for finite-width
To
study the finite-width, we firstly introduce the Jacobian of the network. Let f(x1)...... [(NN) Then, the Jacobian J of F with respect W is J where J have dimension [(((L-2) x))=)))mm+d+))xxxxx The empirical Neural
F
8F OF (vec(W.)
[vec[W]]
Tangent Kernel (NTK) matrix can be defined (D) = JJJ DL. aF or [oeetw))]
[ivec
Accordingly, we generalize Theorem I ffrom the infinite-width finite-width setting below.
Theorem 2. For I--layer network defined by Equation 1 let (L)) JJ be the NTK matrix, and the weights of the network be initialized as [Wiks (1 1/m). ) for all E [T]. Under Assumptions 7 andd when N 2 2(dA), then Amin (JJT) can be bounded by
θ N II (Bs(or) a5-1)) < Amin (JJJ)
N
(Bz(os) + a 1=k42
Σ
θ
II
d
k=2
k=0

---

where the first inequality (lower bound) holds with probability at least 1 - 1e Ets exp(-9(m)) exp(-9((1) and the second inequality (upper bound) holds with proba- biliy at least L-1 exp(- - exp(--(1)) The defimitions of fr, and Br are the same as those in Theorem
Remark: Theorem
2 achieves a similar result as Theorem if jif the width m is large.
4.5
Connection Generalization Error Bound
Based on the aforementioned upper and lower bounds of the minimum eigenvalue of NTK under different settings, here we establish its relationship with the generalization error of DNNs. We provide bound on the expected ()-1 error obtained by Algorithm |
with y = (U1,--. yN) determined by Algo- rithm with the step size of SGD ? xC1 Vy y 1K (onvNN for some small enough absolute constant k. Under Assumptions L and 3 for any E (0, and a not very large I,, if the width m 2 m, where in depends on Amin K k(L)), ),8, N, and L, then with probubility at leust
Theorem 3. Given DNN defined by Equation 1
1 over the randomness of W(),, we obtain the following high probability bound:
(C3))
y Amin (KLLI)N)
log(1/8) N
(W) Sō C2y
+ +0
where C1 VL/ + 1)/--1 and C2 = only on I, and Lipmax is the maximum value of the Lipschitz constants of the all activation functions.
VL(LLppp 1)T-1 are two constants depending
Theorem gives an Agorithm--deeeneee generalization error bound of DNNs defined by Equation (T) trained with SGD with different activation functions and skip connections. If m is large enough, the learning rate is infinitesimal, which means the generalization error bound mainly depends on the NTK matrix, similarly to Cao and Gul (2019), Du et al. [2019a]. Admittedly, our result is in an exponential increasing order the depth. However, in practice, the depth L during
Remark:
the search phrase is smaller than 20, even 10 [Liu et al., 2018 Dong al. 2021] As we detail in Appendix our results extend previously known results.
According to Theorem 3 the generalization performance of DNNs is controlled by the minimum eigenvalue of the NTK matrix, which in turn affected by different activation functions and skip connections, as discussed in Theorem T Apart from the NTK matrix itself, the condition 2 m also effected by different activation functions, which implies that the required minimum width different in these cases.
4.6 Proof sketch
2020 Cao and Gu 2019 beyond ReLU, which is critical for enabling search across activations. The extension to other activation functions and skip connections is non-trivial due to non-linearity, inhomogeneity and nonmonotonicity.
Our work extends the proofs of Nguyen and Mondelli
To derive the upper and lower bounds on the minimum eigenvalue, we start from Lemma I on the NTK formula under the mixed actívation functions and skip connections, and we transform the minimum eigenvalue estimation to the computation (estimation) of the bound G. & (Amin (Gn)n The infinite-width and fiite-widtte are included in Appendix B and resppetively For the upper bound, estimate the diagonal elements of G' and the property that the minimum eigenvalue is less than the mean of the diagonal elements of a matrix to proof. For the lower bound, we use Hermite expansion and Yaskovv 2014 Corollary 3.1]. Combining these results concludes the proof.
To derive the generalization error bounds, we need series of lemmas (see Appendix Dp. the input weights are close, the output of each neuron with any activation function does not change too much (see Lemma 7). If the initilizations are close, the neural network output (æ; W) is almost linear in W (see Lemma 8). and the loss function f/ga/ W)] is almost convex function of W for any E [N] (see Lemma 9). Accordingly, the gradient and loss of the neural network can be upper bounded by Lemmas 10 and II respectively, which concludes the proof when combined with some relevant results [Cao and Gu 2019 Allen -hhu et al. 2019 Further discussion on the differences is deferred to Appendix
7

---

0.2 822 031 32: 021 33
035
92
Probabiles
5:16 0.1
616 0.9 02
0220
0.75
9:20
9:2
121
a2 621 92 0.1 82
0.70
2.
0.7
8:15
015
02
022
02 02 02
01
10
Layer
activation functions a
(h) skip connections a
Figure 1: Architecture search results on activation functions indicated by the probability of in (a) and skip connections indicated by a in (b). We notice that for each layer, ReL.U and LeakyReI.U are selected the higher probability.
Numerical Validation
To validate theoretical results, we conduct series of experiments NAS. Firstly, we simulate the NTK matrices under different depths in Appendix [:4 to verify the relationship between the minimum cigenvalue of NTK and the network depth L in Theorem [ In sec. sec. we use the DARTS algorithm [Liu et al.) 2019b] to conduct experiments on activation function search and skip connection search under the search space of Equation (T). Finally, we use the minimum eigenvalue of NTK to guide the training of NAS on the benchmark MAS-Bench-200 (Dong and Yang 2020), with comparison of recent NAS algorithms. Additional experiments on NAS-Bench- 101 |Ying al.
2019] and transfer learning are deferred to Appendix F5 and F.6
5.1 DARTS experiment
In this section we employ typical NAS algorithm, DARTS [Liu et al., 2019b),
assess our theoretical results on activation functions and skip connections. We select Fashion-MNIST [Xiao]
al. 2017] as a standard benchmark. Details about Fashion-MNIST are shared in Appendix F.
Search space and search strategy: Our search space is defined by Equation (2) on skip connections, activation functions, and weight parameters. We follow the search strategy of et al. [2019b] in two-level scheme, one level is for weight parameter search W and the other level is for architecture search {ar, o)), ). which results in the final optimal architecture {a",, a² W*) }. Different from Liu et al. [2019b], the activation function search and the skip connection search in our setting is independent. To obtain a", we use the softmax function normalize the weights and choose the specific activation function with the highest probability in each layer. To obtain ar", we initialize each entry
1/2 [L- 2)), constrain it to 00, 1] during training, and retain the skip connection when oj > 1/2.
NAS Results: We conduct the experiment via DARTS on a feedforward neural network with L = 10 and 1024, with 5 runs. After training, the probability of these activation functions and skip connections in each layer is reported in Figure I(a) and [(b)] respectively. We have the following Firstly, after the search process, LeakyReLU and ReLU are selected as the activations with the highest probability in each layer. This coincides with our theoretical results in Theorem [ One minor difference is that the probability of LeakyReLU is slightly inferior ReLU in practice.
findings:
The reason behind this could be the sparsity of ReL.U (de Dios and Bruna 2020). Secondly, in the first layer, we observe the largest difference on the probability of various activation functions. As the network becomes deeper, the differences decrease with the last layers having no difference between different activation functions. This phenomenon matches our theory well. To be specific, in Theorem I our result on the minimum eigenvalue largely depend on the first layer and its Hermite coefficint. Besides, this result also provides a justification on omitting the high-order terms while retaining the first layer activation terms. Thirdly. for the skip search result, we find that the skip connections are required
each layer when < 10, as suggested by our theoretical results in Theorem | It also verifies the results of Zhou et al. 22020) We expect that the skip connections might not be required in each layer for deep neural networks, since their capacity can already be enough [He al. 2016); but we defer the related study to future work.
8

---

Table 2: Results CIFAR-10, CIFAR-100 and ImageNet-Ile 16 part of NAS-Bench-201. The best performance is highlighted by bold. The results of NASWOT, TE-NAS and KNAS are reported from the corresponding papers. The results of ResNet, NAS-RL and DARTS are reported in (Xu et al., 2021]. The results illustrate that Eigen-NAS outperforms the prior art in CIFAR-100 and Imagenet- 16. In particular, Eigen-NAS outperforms KNAS in all three cases when the same number of top-k architectures are selected, i.e., k = 20, and still achieves promising performance when used, which we attribute the more precise minimum eigenvalue estimation.
smaller k
Type
Model/Algorithm
CIFAR- 10 (%) CIFAR-100 100 (%) ImageNet-16 16 (%)
w/o Search
ResNet
He et al. 2016
93.97
70.86
42.63
Search
NAS-RL
Zoph and Le,2011 2017
92.83
70.71
44.10
Gradient
DARTS
Liu et al. 2019b
88.32
67.34
33.04
Train-free
NASWOT
Mellor et al.
2021
92.96
70.03
44.43
Train-free
TE-NAS
Chen ct al.
2021
93.90
71.24
42.38
Train-free
KNAS [Xu al. 2021
(A:
20)
93.38
70.78
44.63
Train-free
(T) Shu et al.
2022
93.08 + 0.24
69.51 0.59
40.87 + 0.85
Train-free
NASI (4T) [Shu et
2022
93.55 + 0.10
71.20
44.84
Train-free
Eigen-NAS (Is 20)
93.46 + 0.01
71.42 - 0.63
4
Train-free
Eigen-NAS
93.43 + 0.08
69.92 + 1.82
45.53 + 0.06
Interestingly, the search strategy favors the activation functions and the skip connections with larger minimum eigenvalue of NTK, which enjoy better generalization performance. This result also motivates us to study the following question: can the minimum eigenvalue of NTK guide the search process in NAS? We provide affirmative answer in the next section with experimental validations.
5.2 NAS- BS--Bnnnc-211 Experiment
In this experiment, we use the minimum eigenvalue to guide NAS on NAS-Bench-200) [Dong and Yang 2020 Each experiment is repeated 5 times, while it can run single GPU in a few hours.
Benchmark and baselines: MAS-Bench-2011 [Dong and Yang 2020 is commonly used benchmark for NAS algorithm evaluation, which includes three datasets: a) CIFAR-10 10 (Krizhevsky et al. (2014), b) CIFAR-I00 (Krizhevsky al. (2014) and c) ImageNet-16 [Chrabaszez et al. [001] for image classification. Details on the datasets exist in Appendix F.1 Apart from that, we evaluate the proposed approach with some baselines including ResNet, DARTS, RL based algorithm and some train-free algorithms.
Algorithm procedure: Our algorithm, called Eigen-NAS, also belongs in the train-free category. Eigen-NAS follows KNAS, which leverages the minimum eigenvalue of NTK to guide NAS. However, due to the ((N3) time complexity of computing these eigenvalues, KNAS instead computes ||F.. However, from the expression Amin (K) S - Kü: S ||||| we utilize the first inequality in Eigen-NAS to obtain a tighter (and more computationally efficient) bound to Amin- The computation cost of our method is O(N). which is less than computing the Frobenius norm (O))))) Sequentially, the top-k best candidates architectures Eigen-NAS and then the best architecture chosen by the validation error. Please refer to the results in Table Due the page limit, the algorithm is located in Appendix F
chosen in KNAS and our
The experimental results Table verify that Eigen-NAS guided by the proposed metric above achieves the best performance on both the CIFAR-100 100 and ImageNet-16 16 datasets, and com- petitive performance on CIFAR-1O, outperforming KNAS all three cases when = 20 for both methods. Even when we consider smaller k 5, Eigen-NAS can outperform KNAS, which we attribute to the more precise minimum eigenvalue estimation.
Results:
6 Conclusion
In this work, we explore the relationship between the minimum eigenvalue of NTK and neural architecture search. We derive upper and lower bounds on the minimum eigenvalues of NTK for (in)finite residual networks under different mixtures of activation functions, and establish a connection between minimum eigenvalues and the generalization properties of the special search space: activation function and skip connection search of NAS. Our theoretical results on various activation functions and mixed activation cases can also be a tool for deep learning theory researchers to prove generic results rather than studying single architecture, e.g., ReLU networks. In addition, use

---

the minimum eigenvalue as guide for the training of NAS in a train-free method, which greatly exceeds the efficiency of the classic NAS algorithm. When compared with existing train-fire free methods, our algorithm, called Eigen-NAS, achieves higher accuracy. We posit that this will be useful for studying computationally efficient methods on NAS.
A core limitation is whether our proof framework can cover more general structures in NAS, such as the most commonly used convolutional neural networks (CNNs). Even though this seems possible, this is non-trivial due to the tensors that emerge. To be specific, it requires the element-recursivy form of NTK matrices in Arora al. [2196] be transformed into a global-recursive form (similar to Lemma DT. then analyze its minimum eigenvalue. Besides, the contraction operation of tensors, the locality and boundary effects of convolutional layer in CNNs make the analysis difficult. Therefore, we believe this is a topic on its own right. Another limitation of our work is that it does not analyze the various algorithms proposed for searching through the search space. We believe that a deeper understanding of such algorithms, such as DARTS can provide further insights into how to design improved search spaces. In addition, the upper and lower bounds of the minimum eigenvalues of the NTK matrices for different activation functions given by Theorem [ have some overlaps, which means that our suggestions on activation functions selection based on these bound appear bit vacuous in theory but still coincide with our experimental validations. Maybe, tighter bound without overlap for different activation functions is needed to address this theoretical issue.
Acknowledgements
We also thankful to the reviewers for providing constructive feedback. Research was sponsored by the Army Research Office and was accomplished under Grant Number W91 INF-19-1-0404 This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043). This work was supported by SNF project Deep Optimisation of the Swiss National Science Foundation (SNSF) under grant number 200021 .205011. This work was supported by Zeiss. This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (grant agreement n 725594- time-data). Corresponding authors: Fanghui Liu and Zhenyu Zhu.
10

---

References
Z. Allen-Zhu, Y. Li, and Y. Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In Advances in Neural Information Processing Systems (NewrlPS), 2018.
Z. Allen-Zhu, Li, and Song. convergence theory for deep learning via over-paramettrriatio.. In International Conference on Machine Learning (ICML). 2019.
S. Arora, S. Du, W. Hu, Z. Li, and R. Wang. Fine-grained analysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference on Machine Learning (ICML), 2019a.
S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems (NeurIPS), 2019b.
P. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normaiize margin bounds for neural networks. In Advances Neural Information Processing Systems (NeurIPS), 2017.
Y. Belfer, A. Geifman, M. Galun, and R. Basri. Spectral analysis of the neural tangent kernel for deep residual networks, 2021.
A. Bietti and Bach. Deep equals shallow for relu networks kernel regimes. In International Conference on Leurning Representations (ICLR), 2021.
Y. Cao and Q Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
W. Chen, X. Gong, and Z. Wang. Neural architecture search imagenet in four gpu hours: A theoretically inspired perspective. In International Conference on Learning Representations (ICLR), 2021.
Y. Chen, T. Yang, Zhang, G. Meng, X. Xiao, and Sun, Detnas: Backbone search for object detection. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Z. Chen, Y. Cao, Q Gu, and Zhang, generalized neural tangent kernel analysis for two-layer neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020a.
Z. Chen, Y. Cao, D. Zou, and Q. Gu. How much pve-pparameterizationn is sufficient to learn deep RcLU networks? In International Conference on Learning Representations (ICLR), 2020b.
P. Chrabaszez, I. Loshchilov, and F. Hutter. A downsampled variant of imagenet as an alternative to the cifar datasets, 2017.
J. de Dios and Bruna. On sparsity in overparametrised shallow relu networks, 2020.
J. Deng. W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. Conference on Computer Vision and Pattern Recognition (CVPR), 2009.
S. Ding, T. Chen, X. Gong, W. Zha, and Z. Wang. Autospeech: Neural architecture search for speaker recognition, 2020.
X. Dong and Y. Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
X. Dong, L. Liu, K. Musial, and B. Gabrys. Nats-bench: Benchmarking nas algorithms for architecture topology and size. IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI), 2021.
S. Du, J. Lee, H. Li, L. Wang, and X. Zhai. Gradient descent finds global minima of deep neural networks. In International Conference Machine Learning (ICML), 2019a.
S. S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference Learning Representations (ICLR), 2019b.
11

---

T. Elsken, J. H. Metzen, and F. Hutter. Neural architecture search: A survey. Journal of Machine Learning Research, 2019.
N. Ghosh, S. Mei, and B. Yu. The three stages of learning dynamics in high-dimensional kernel methods. In International Conference on Learning Representations (ICLR), 2022.
G. H. Golub and C. F. Van Loan. Matrix Computations (3rd Ed.). 1996.
T. Hastie, A. Montanari, S. Rosset, and R. J. Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. Annals of Statistics, 2022.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
K. Huang, Wang, M. Tao, and Zhao. Why do deep residual networks generalize better than deep feedforward networks? neural tangent kernel perspective. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
A. Jacot, F, Gabriel, and C. Hongler. Neural tangent kernel: Convergence and generalization neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
A. Klimovsky. figh-dimennionaal gaussian fields with isotropic increments seen through spin glasses. Electronic Communications Probability, 2012.
A. Krizhevsky, V. Nair, and G. Hinton. The cifar-10 dataset. online: hllp://www. cs. toronto. edudkriz/cifar himl, 2014.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 1998.
L. Li and A. Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in Artificial Intelligence, 2020.
C. Liu, L.-C. Chen, F. Schroff, H. Adam, Hua, A. Yuille, and L. Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Conference Computer Vision and Pattern Recognition (CVPR), 2019a.
H. Liu, K. Simonyan, O. Vinyals, C. Fermando, and K. Kavukcuoglu. Hicrarchical representations for efficient architecture search. In International Conference Learning Representations (ICLR), 2018.
H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019b.
E. Malach, G. Yehudai, S. Shaley-Schwartz, and Shamir. Proving the lottery ticket hypothesis: Pruning is all you need. In International Conference on Machine Learning (ICML), 2020.
S. Mei, T. Misiakiewicz, and A. Montanari. Learning with invariances in random features and kernel models. In Conference on Learning Theory (COLTT) 2021.
Mellor, J. Turner, A. Storkey, and E. Crowley. Neural architecture search without training. In International Conference Machine Learning (ICML), 2021.
A. Montanari and Y. Zhong. The interpolation phase transition in neural networks: Memorization and generalization under lazy training, 2020.
Q. Nguyen. On the proof of global convergence of gradient descent for deep relu networks with linear widths. In International Conference on Machine Learning (ICML), 2021.
Q Nguyen, M. Mondelli, and G. F. Montufar. Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning (ICML), 2021.
Q. N. Nguyen and M. Mondelli. Global convergence of deep networks with one wide layer followed by pyramidal topology. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
12

---

S. Oymak and M. Soltanolkotabi. Toward moderate overparameterization:: Global convergence guarantees for training shallow neural networks. IEEE Journal on Selected Areas in Information Theory, 2020.
S. Oymak, M. Li, and M. Soltanolkotabi. Generalization guarantees for neural architecture search with vainnvaliiationn split. International Conference on Machine Learning (ICML), 2021.
I. Radosavovic, J. Johnson, Xie, W.-Y. Lo, and P. Dollár. On network design spaces for visual recognition. In International Conference Computer Vision (ICCV), 2019.
P. Ren, Y. Xiao, X. Chang, P.-Y. Huang, Z. Li, X. Chen, and X. Wang. A comprehensive survey of neural architecture search: Challenges and solutions. ACM Computing Surveys (CSUR), 2021.
Schur. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen veränderlichen. Journal für die reine und angewandte Mathematik, 1911.
Y. Shu, W. Wang, and S. Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
Y. Shu, S. Cai, Z. Dai, B. C. Ooi, and B. K. H. Low. NASI: Label- and data-agnostic neural architecture search at initialization. In International Conference Learning Representations (ICLR), 2022.
M. Tan and Q. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning (ICML), 2019.
Tirer, Bruna, and Giryes. Kernel-based smoothness analysis of residual networks. In Mathematical and Scientific Machine Learning, 2022.
R. Vershynin. High- Diah-Diimnsional Probability: An Introduction with Applications in Data Science. 2018.
B. Wu, X. Dai, P. Zhang, Wang, F. Sun, Y. Wu, Y. Tian, Vajda, Y. Jía, and K. Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
H. Xiao, Rasul, and Vollgraf. Fashion-mnist. a novel image dataset for benchmarking machine learning algorithms, 2017.
J. Xu, L. Zhao, J. Lin, R. Gao, X. Sun, and H. Yang. Knas: Green neural architecture search. In International Conference on Machine Learning (ICML), 2021.
Y. Xu, L. Xie, X. Zhang, X. Chen, G.-J. Qi, Q. Tian, and H. Xiong. Pe-darts: Partial channel connections for memory-effiiien architecture search. In International Conference on Learning Representations (ICLR), 2019.
Yaskov. Lower bounds on the smallest eigenvalue of sample covariance matrix. Electronic Communications Probability, 2014.
Ye, B. Li, Y. Li, T. Chen, Fan, and W. Ouyang. 3-darts: Beta-decay regularization for differentiable architecture search. In Conference on Computer Vision and Pattern Recognition (CVPR), 2022.
C. Ying, A. Klein, E. Christiansen, E. Real, K. Murphy, and F. Hutter. Nas-bench-100 101: Towards reproducible neural architecture search. In International Conference on Machine Learning (ICML), 2019.
Y. Zhang, Z. Qiu, Liu, T. Yao, D. Liu, and T. Mei. Customizable architecture search for semantic segmentation. In Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
P. Zhou, C. Xiong, R. Socher, and S. C. Hoi. Theory-inspired yath-regularized differential network architecture search. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
B. Zoph and Q Le. Neural architecture search with reinforcement learning. In International Conference Learning Representations (ICLR), 2017.
13

---

B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
D. Zou, Y. Cao, D. Zhou, and Q Gu. Gradient descent optimizes over-parameterized deep relu networks, Machine Learning, 2019.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We clearly discuss the limitation
of this work in the conclusion section.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We clearly discuss the societal impact of this work in the Appendix G
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All of the assumptions are clearly stated and are well discussed.
(b) Did you include complete proofs of all theoretical results? [Yes] All of the proofs can be found in the Appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [No] The datasets we in this work are all in the public domain and standard for image-related tasks. Thus, our setup can be reproduced by interested practitioners. The code will be open-sourced upon the acceptance of the paper.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] The data splits and our comparisons follow previous works, e.g. the experiment on sec. follows KNAS code.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] All our experiments are conducted on single GPU in our internal cluster.
4. If you using existing assets (e.g., code, data, models) curating/releusing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cite all the corresponding papers that provide the benchmarks/assets we use.
(b) Did you mention the license of the assets? [Yes] All the datasets used in this work are publicly available datasets; in addition, they quite popular benchmarks for diverse tasks. All the datasets enable their use for research purposes.
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] The datasets we utilize are publicly available and contain tens of thousands of images. We refer to the authors original papers describing the datasets.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] The datasets used do not contain offensive content or personally identifiable information.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "vDNAK89XmqJ", "reviewer": "Reviewer_LWxJ", "summary": "This paper presents theoretical analyses on Neural Architecture Search using the recent theory of NTK. Especially, it has provided the lower and upper bounds of the minimum eigenvalue of the NTK matrix as well as the generalization bound induced by the NTK matrix for the architectures in their pre-defined search space. Finally, based on these theoretical analyses, this paper develops a training-free NAS algorithm, namely Eigen-NAS. Eigen-NAS has shown its competitive performance in training-free NAS, which in turn also supports the theoretical analyses in this paper.", "questions": "1. This paper focuses on the theoretical study of NAS with only skip connection and activation function search mainly due to the non-trivial analysis of other general structures. Interestingly, both [R2] and Shu et al. [2020] have empirically shown that topology will be more important than diverse operations in NAS, and NAS with only topology search can also provide competitive performance compared with standard NAS. I suppose that these results may also serve as a good motivation to support why the theoretical study on only skip connection and activation function will still be attractive in the literature.\n2. In line 98, to my best knowledge, Du et al. [2019] and Nguyen [2021] are studying the convergence of GD instead of SGD.\n3. In the problem setting section of this paper, an explicit representation of the classification task (i.e., the binary classification task) and the possible value of $y$ (i.e., $y \\in \\\\{-1,1\\\\}$) will be more helpful for the readers to understand this section. Similarly, the “cross-entropy loss” in line 111 can more specific, e.g., the cross-entropy loss with a sigmoid function to represent the probability of $y=1$.\n4. In line 134, I suppose it should be “we conduct the skip connection search and activation function search independently”. Besides, I am curious about why skip connection search and activation function search can not be conducted jointly.\n5. The lemma 1 and therefore the results based on Lemma 1 actually do not match the initialization applied in this paper (i.e., the Gaussian initialization with the variance of $1/m$ instead of $2/m$ in Tirer et al. [2021], Huang et al. [2020], Belfer et al. [2021].).\n6. The claim about depth $L$ in line 208 may not be true because whether the minimum eigenvalue will increase or not with larger $L$ highly depends on the activation functions as shown in Figure 3,4. Moreover, I am curious about why the minimum eigenvalue of Tanh does not increase with an increasing $L$ especially when it achieves larger $\\beta_1$ and $\\beta_2$ and hence a larger upper bound of the minimum eigenvalue than ReLU and Sigmoid? \n7. One of the comments about Table 2 is that the search cost can also be included to verify the improved efficiency of Eigen-NAS over KNAS. Another one is that the recent training-free NAS paper [R1] should also be included in the comparison or discussion. Because [R1] exploits the trace norm of the NTK matrix to indicate the performance of different architectures while this paper exploits the Frobious norm in its Eigen-NAS algorithm (line 324). They are similar.\n8. An empirical study of how the number of skip connections layers (i.e., the topology) will affect the performance of neural architectures will be more interesting and related to the NAS area, which can also further verify the impact of the skip connection on the minimum eigenvalue of NTK (Theorem 1, 2) and also the generalization performance of candidate architecture (Theorem 3).\n\n[R1] NASI: Label-and Data-agnostic Neural Architecture Search at Initialization\n\n[R2] Exploring randomly wired neural networks for image recognition", "limitations": "This paper has provided a valuable discussion about limitations and future works.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n\n1. This paper has provided non-trivial theoretical analyses on NAS using the recent theory of NTK, which may inspire more theoretical studies on NAS in the NAS area.\n2. The Eigen-NAS inspired by their theoretical results shows competitive performance on different NAS benchmarks.\n\n*Weaknesses*\n\n1. This paper does not really study the convergence or optimization of NAS as what has been claimed in its title or abstract. Instead, it is mainly focusing on the generalization property of its restricted search space (i.e., a small search space compared with the standard NAS search space).\n2. The motivation for why the minimum eigenvalue of NTK needs to be studied and how it is explicitly related to the generalization bound (i.e., Theorem 3) have not been well clarified. As a result, the study of the minimum eigenvalue of NTK in this paper may be less related. Using the minimum eigenvalue of NTK to bound the generalization performance of DNN in Theorem 3 will make the theoretical results in this paper more coherent.\n3. This paper does not provide a clear or explicit interpretation of how the theoretical results in this paper can help us understand NAS (shown in the title). Instead, from my own perspective, this paper has mainly developed a generalization bound for NAS and then proposed a training-free NAS algorithm (i.e., Eigen-NAS) inspired by their theoretical results. And such a training-free NAS algorithm is similar to the one in [R1] using the trace norm of the NTK matrix.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "GX16Dv7o0D", "reviewer": "Reviewer_h7Bq", "summary": "This paper provides an NTK analysis for a class of residual networks with a mixture of activation functions at different layers. The authors derive bounds on the minimum eigenvalue for both finite and infinite width settings. They also give a generalization bound for this class of network architecture.", "questions": "What is the data used in the simulation of minimum eigenvalues of NTK for different activations and architectures?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main contribution of this work, in my opinion, is a non-trivial derivation of lower and upper bounds on the minimum and for residual networks with a mixture of activation functions. However, analysis and proof techniques are mainly taken from the well-established NTK literature, such as Huang et al., 2020, Oymak and Soltanolkotabi, 2020… Similar generalization bounds are established by Cao and Gu, 2019, and Arora et al., 2019a.\n\nThere is an interesting connection to NAS that the authors observe empirically where NAS always picks up RELU and/or Leaky RELU in the optimal search. That coincides with the fact that RELU and LeakyRELU imply larger minimum eigenvalue in the NTK sense. However, deep neural networks in practice do not generally operate in the NTK regime. \n\nIn short, I see this work purely as an NTK analysis rather than an “unifying framework” for NAS. I don’t see how the work studies “optimization and generalization of NAS” or how the derived results guide NAS.\n\nIn terms of the presentation, the paper is well-written and easy to follow. One thing I would suggest is to instantiate Theorem 1 with a few special cases, such as the standard 2-layer networks with ReLU activation. Illustrating the Hermite coefficients of such cases would help the readers to compare with existing results, e.g., Oymak and Soltanolkotabi, 2020.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "G7iJ-GGJ-ai", "reviewer": "Reviewer_Nckt", "summary": "This paper provides the theoretical analysis of a fully-connected neural network with mixed activation functions in both infinite and finite width schemes. Furthermore, the authors provide analysis on both lower and upper bounds of minimum eigenvalues of NTK and generalization error bounds in SGD. Finally, the authors provide empirical experiments to support their theoretical claims on NAS problems. ", "questions": "1. Why does the theoretical analysis of mixed activation neural networks help the understanding of the NAS problem? NAS algorithms such as DARTS or random search WS have two phases: search and evaluation. The authors show just an analysis of the evaluation phase in the paper, which corresponds to the final architecture. In other words, the paper seems to study NTK and generalization bounds on a particular family of the neural network, which has mixed activation functions. \n2. Continuing from the Q1, how do we know architecture found from DARTS or random search RS are optimal architecture as stated in the line 147? \n3. In lines 295-296, the author mentions that DARTS results coincide with the theoretical results. However, a long line of NAS research has shown DARTS's problems ([3, 4, 5, 6, 7]), especially the overfitting. Will other latest algorithms such as $\\beta$-DARTS or DRNAS find the same results as DARTS? \n4. In Table 2, Eigen-NAS on CIFAR-10 with $k=20$ seems to converge to sub-optimal architecture with a very small standard deviation of 0.01. Since the optimal architecture achieves $94.37\\%$, can we conclude that Eigen-NAS only can find sub-optimal architecture? From 15,625 architecture candidates in NAS-Bench-201, what is the ranking of the architecture Eigen-NAS found? \n5. Can you also verify the numerical results on DARTS Search Space with Eigen-NAS?", "limitations": "The author provides a thorough theoretical analysis of the minimum eigenvalue on NTK and generalization bounds on a neural network with mixed activation functions. However, the analysis is only for a particular family of neural networks (with mixed activation functions and selective skip-connections). Furthermore, the neural network analysis is on the final architecture, assuming that existing NAS algorithms, such as DARTS,  random search WS, or Eigen-NAS, can find the optimal architecture from their search phase. \n\nOverall, I see the authors' theoretical analysis is not closely correlated to understanding the actual NAS problem. Furthermore, the empirical performance is far lower than existing state-of-the-art in NAS literature. Therefore, I give a reject. \n\n1. Cao, Yuan, and Quanquan Gu. \"Generalization bounds of stochastic gradient descent for wide and deep neural networks.\" Advances in neural information processing systems 32 (2019).\n2. Nguyen, Quynh, Marco Mondelli, and Guido F. Montufar. \"Tight bounds on the smallest eigenvalue of the neural tangent kernel for deep relu networks.\" International Conference on Machine Learning. PMLR, 2021.\n3. Ye, Peng, et al. \"b-DARTS: Beta-Decay Regularization for Differentiable Architecture Search.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.\n4. Chen, Xiangning, et al. \"Drnas: Dirichlet neural architecture search.\" arXiv preprint arXiv:2006.10355 (2020).\n5. Liang, Hanwen, et al. \"Darts+: Improved differentiable architecture search with early stopping.\" arXiv preprint arXiv:1909.06035 (2019).\n6. Dong, Xuanyi, and Yi Yang. \"Nas-bench-201: Extending the scope of reproducible neural architecture search.\" arXiv preprint arXiv:2001.00326 (2020).\n7. Yang, Antoine, Pedro M. Esperança, and Fabio M. Carlucci. \"NAS evaluation is frustratingly hard.\" arXiv preprint arXiv:1912.12522 (2019).", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. Building upon Cao et al. and Nguyen et al.'s proof framework, the author provides the theoretical analysis of the minimal eigenvalue of NTK and generalization error on mixed activation neural networks.\n\nWeaknesses\n1. A considerable gap exists between theoretical analysis and the actual NAS problem. Their theoretical results only provide the minimum eigenvalue of NTK and generalization error of a fully-connected neural network with mixed activation functions. I will elaborate on this in more detail in the Question section.\n2. NAS-Bench-201 results in Table 2 are not compelling enough. Latest methods such as $\\beta$-DARTS [3] or DrNAS [4] find the optimal architecture in NAS-Bench-201.\n3. General NAS problems contain a larger degree of freedom in choosing the components of a neural network, not only just activation functions and skip connections. Similar to the first point, there is a considerable discrepancy between the analysis and practice. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A1yQaxuBJXS", "reviewer": "Reviewer_Yjm8", "summary": "This paper extends the Neural Tangent Kernel limit to different (and mixed) activations functions, as well as a varying proportion of skip-connections. Then this paper is able to bound the minimum eigenvalue of the neural tangent kernel matrix, and to link this value to the generalization capability of the model. This allows to guide Neural Architecture search without training.\n\nThe authors validate their methods numerically by first showing that the derived bounds match empirical results, and that using their bounds to guide NAS improves NAS performances.\n\n", "questions": "Can this framework be used to guide NAS through choices more meaningful than choosing between a ReLu and a Sigmoid?\n\nCould the authors investigate how reliable is their criterion to guide NAS? Maybe something like how often their criterion would rank two models in the correct order?", "limitations": "The authors clearly state that a big limitation of their work is that it only works for FC networks, and not more common CNN or Transformers.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Originality\n\nWhile I am not very familiar with the field, this is to my knowledge the first time that an NTK approximation was derived for various and mixed activations functions.\n\n# Quality\n\nThe paper contributions seems sounds, though the empirical validation could be more convincing: how well does the criterion rank different architectures?\n\n# Clarity\n\nThe paper is clearly written. The title and the abstract, while quite clear, appear to be a little misleading: I don't think this paper helps understanding NAS (for instance NAS convergence), rather than providing a criterion which can help guide NAS.\n\n# Significance\n\nWhile the empirical results don't show a huge improvement, being able to guide NAS across different activation functions and skip-connections proportions seems useful. The result would be much more significant if it applied to CNN and Transformers, but this is an interesting progress.\nI wish the authors had tested their approach on more challenging tasks, and with more competitive activation functions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept