Unifying and Boosting Gradient-Based Training-Free Neural Architecture Search
Authors: Yao Shu
Zhongxiang Dai
Zhaoxuan Wu
Bryan Kian Hsiang Low
Venue: NeurIPS 2022 Accept (2022)
Keywords: Neural Architecture Search
Training-free
Neural Tangent Kernel
Hybrid
Bayesian Optimization

Abstract: Neural architecture search (NAS) has gained immense popularity owing to its ability to automate neural architecture design. A number of training-free metrics are recently proposed to realize NAS without training, hence making NAS more scalable. Despite their competitive empirical performances, a unified theoretical understanding of these training-free metrics is lacking. As a consequence, (a) the relationships among these metrics are unclear, (b) there is no theoretical interpretation for their empirical performances, and (c) there may exist untapped potential in existing training-free NAS, which probably can be unveiled through a unified theoretical understanding. To this end, this paper presents a unified theoretical analysis of gradient-based training-free NAS, which allows us to (a) theoretically study their relationships, (b) theoretically guarantee their generalization performances, and (c) exploit our unified theoretical understanding to develop a novel framework named hybrid NAS (HNAS) which consistently boosts training-free NAS in a principled way. Remarkably, HNAS can enjoy the advantages of both training-free (i.e., the superior search efficiency) and training-based (i.e., the remarkable search effectiveness) NAS, which we have demonstrated through extensive experiments.

Unifying and Boosting Gradient-Based Training-Free Neural Architecture Search
Yao Shu Zhongxiang Dail, Zhaoxuan Wu Bryan Kian Hsiang Lowi Dept. of Computer Science, National University of Singapore, Republic of Singapore! Institute of Data Science, National University of Singapore, Republic of Singapore Integrative Sciences and Engineering Programme, NUSGS, Republic of Singapore {shuyao, daizhongxiaag, 1owkh wow.llookhheoc &comp nus. edu.sg wu wu.zhaoxuan@u, nus. edu
Abstract
Neural architecture search (NAS) has gained immense popularity owing to its ability automate neural architecture design. A number of training-free metrics are recently proposed to realize NAS without training, hence making NAS more scalable. Despite their competitive empirical performances, unified theoretical understanding of these training-fre free metrics is lacking, As consequence, (a) the relationships among these metrics are unclear, (b) there is theoretical interpreta- tion for their empirical performances, and (c) there may exist untapped potential in existing training-free free NAS, which probably can be unveiled through a unified theoretical understanding. To this end, this paper presents a unified theoretical anal- ysis of gradient- training-free NAS, which allows us to (a) theoretically study their relationships, (b) theoretically guarantee their generalization performances, and (c) exploit our unified theoretical understanding to develop a novel framework named hybrid NAS (HNAS) which consistently boosts training-free NAS in prin- cipled way. Remarkably, HNAS can enjoy the advantages of both training- (i.e., the superior search efficiency) and training-based (i.e., the remarkable search effectiveness) NAS, which we have demonstrated through extensive experiments. Our codes are available at https: // thub. www hamm/huyyo95/HHNA
1 Introduction
Recent years have witnessed surging interest in applying deep neural networks (DNNs) in real-world applications, e.g., machine translation [1] object detection [2]. among others. To achieve compelling performances in these applications. many Nomain-specifh neural architectures have been handcrafted by human experts with considerable efforts. However, these efforts have gradually become unaf- fordable due to the growing demand for customizing neural architectures for different tasks. To this end, neural architecture search (NAS) (3) has been proposed to design neural architectures auto- matically. While many training-based NAS algorithms 4 [5] have achieved state-of-the thettrr art (SOTA) performances in various tasks, their search costs usually are unaffordable in resource-constraing scenarios mainly due to their requirement for training DNNs during search. As result, a number of training-free metrics have been developed to realize training-fre NAS 7]. Surprisingly, these training free NAS algorithms are able achieve competitive empirical performances even compared with other training-baat based NAS algorithms while incurring significantly reduced search costs. More- over, the architectures selected by these training- free NAS algorithms have been empirically found to transfer well to different tasks
Correspondence to: Zhongxiang Dai <caizhonngriagg@Comm wwt.:/cwmmmmmmmmuag....
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Despite the impressive empirical performances of the NAS algorithms using training-free frre metrics, unified theoretical analysis of these training-free metrics is still lacking the literature, leading to a few significant implications. Firstly, the theoretical relationships of these training-free metrics are unclear, making it challenging to explain why they usually lead to comparable empirical results [9]. Secondly, there is no theoretical guarantee for the empirically observed compelling performances of the architectures selected by NAS algorithms using these training-free free metrics. As a consequence. the reason why NAS using these training-free metrics works well is still not well understood, and hence there lacks theoretical assurances for NAS practitioners when deploying these algorithms. To the best of our knowledge, the theoretical aspect of NAS with training- -ree metrics has only been preliminarily studied by Shu et al. [8]. However, their analyses are only based on the training rather than generalization performances of different architectures and are restricted to single training- free metric. Thirdly, there may exist untapped potential in existing training-free free NAS algorithms, which probably can be unveiled through a unified theoretical understanding of their training- free metrics.
To this end, we perform a unified theoretical analysis of gradient-based training- NAS to resolve all the three problems discussed above in this paper. Firstly, we theoretically prove the connections among different gradient-basee -aaed training-free metrics in Sec. 4.1 Secondly, based on these provable connections, we derive a unified generalization bound for DNNs with these metrics and then use it to provide principled interpretations for the compelling empirical performances of existing training-fite free NAS algorithms (Secs. (4.2 and 4.3). Moreover, we demonstrate that our theoretical interpretation for training-foe free NAS algorithms, surprisingly. displays the same preference of architecture topology (i.e., wide or deep) as training- based NAS algorithms under certain conditions (See. 4.4), which helps to justify the practicality of our theoretical interpretations. Thirdly, by exploiting our unified theoretical analysis, we develop a novel NAS framework named hybrid NAS (HNAS) to consistently boost existing training-fret frre NAS algorithms (Sec. 55 in a principled way. Remarkably, through a theory- inspired combination with Bayesian optimization (BO), our HNAS framework enjoys the advantages of both training-basse (i.e., remarkable search effectiveness) and training-free (i.e., superior search efficiency) NAS simultaneously, making it more advanced than existing training-free and training- based NAS algorithms. Lastly, we use extensive experiments to verify the insights derived from our unified theoretical analysis, as well as the search effectiveness and efficiency of our non-trivial HNAS framework (Sec. ().
2 Related Works
Recently, a number of training-free metrics have been proposed to estimate the generalization perfor- mances of neural architectures, allowing the model training in NAS to be completely avoided. For instance, Mellor et al. 66 have developed heuristic metric using the correlation of activations in an initialized DNN. Mcanwhile, Abdelfattah et al. [9] have empirically revealed a large correlation between training-Fie free metrics that were formerly applied in network pruning, c.g., SNIP [10] and GraSP M and the generalization performances of candidate architectures in the search space. These results hence indicate the feasibility of using training-fret ffree metrics estimate the performances of candidate architectures in NAS. Chen et al. 7 have proposed a heuristic metric to trade off the trainability and expressibility of neural architectures in order find well- perfforrfon architectures in various NAS benchmarks. Xu et al. [1] have applied the mean of the Gram matrix of gradients to quickly estimate the performances of architectures. More recently, Shu et al. g have employed the theory of Neural Tangent Kernel (NTK) [33 to formally derive a performance estimator using the trace norm of the NTK matrix with initialized model parameters, which, surprisingly, is shown to be data- and label-agnostic. Though these existing works have demonstrated the fcasibility of training-free free NAS through their compelling empirical results, the reason as to why training- NAS performs well in practice and the answer to the question of how training- -ree NAS can be further boosted remain mysteries in the literature. This paper aims to provide theoretically grounded answers to these two questions through unified analysis of existing gradient- based training-free free metrics.
3 Notations and Backgrounds
3.1 Neural Tangent Kernel
To simplify the analysis in this paper, we consider a I.-layer DNN with identical widths nn = nL-1 n and scalar output (i.c., nt= 1) based the formulation of DNNs in [3]. Let f(x, 0)
2

---

be the output of a DNN with input a E I and parameters O E R that are initialized using the standard normal distribution, the NTK matrix O Rm over dataset of size is defined as
(a, x':0) Vef(æ, (a, 0) Vef(x',0) 0).
(I)
Jacot et al. [3] have shown that this NTK matrix O will finally converge deterministic form O oc the infinitely wide DNN model. Meanwhile, Arora et al. [14], Allen-Zhu et al. (15) have further proven that a similar result, i.e C R oo can also be achieved in over aver-parameterized DNNs of finite width. Besides, Arora et al. 14,, Lee et al. [16] have revealed that the training dynamics of DNNs can be well-characterrzed using this NTK matrix initialization (i.e., Og based on the initialized model parameters 0₂) under certain conditions. More recently, Yang and Littwin [77] have further demonstrated that these conclusions about NTK matrix shall also hold for DNNs with any reasonable architecture, even including recurrent neural networks (RNNs) and graph neural networks (GNNs). Therefore, the conclusions drawn based on the formulation above in this paper expected to be applicable to the NAS search spaces with complex architectures, which we will validate empirically,
3.2 Gradient-Baser Training-Free Metries for NAS
In this paper, we mainly focus on the study of those gradient-basee training-free metrics, i.e., the training-free ffree metrics that are derived from the gradients of initialized model parameters, which we introduce below. Previous works have empirically shown that better model performances usually associated with larger values these training-free -free metrics in practice
Gradient norm of initialized model parameters. While Abdelfattah et al. 9 were the first to employ the gradient norm initialized model parameters to estimate the generalization performance of candidate architectures, the same form has also been derived by Shu et al. [8] to approximate their training-frr free metric efficiently. Following the notations in Sec. 3.1 let ((.,)) be the loss function, we define the gradient norm over dataset S {(x,, 3:)
1 _
MGrad A
Vol(((x,,0)))
(2)
SNIP and GraSP. SNIP [10] and GraSP were originally proposed for training-free network pruning, and Abdelfattah et al. [9] have applied them in training-free NAS to estimate the perfor-
mances of candidate architectures without model training. Following the notations in Sec. [31 let
H; dddxd denote the hessian matrix induced by input æ; the metrics of SNIP and GraSP on dataset
S (( y4) )
can be defined
1 Σ
1 > oo (o
MSNIP
Vol(f (o) MGrasP
(3)
Of note, we use the scaled (i.e, by 1/m) absolute value of the original GraSP metric in throughout this paper to match the mathematical form of other training-free metrics.
Trace norm of NTK matrix at initialization. Recently, Shu et al. g have reformulated NAS into constrained optimization problem maximize the trace of the NTK matrix at initialization. In addition, Shu et al. 8 have empirically shown that this trace norm is highly correlated with the generalization performance of candidate architectures under their derived constraint. Let Op be the NTK matrix based on initialized model parameters On of a DNN, then without considering the constraint in [8], frame this training-fie metric dataset S {(x), ]m
M
@ollu/m.
(4)
4 Theoretical Analyses of Training-Free NAS
4.1 Connections among Training-Fres Free Metrics
Notably, though the gradient-based training-free metrics introduced Sec. 3.2 seem to have distinct mathematical forms, most of them will actually achieve similar empirical performances in practice 19].
3

---

More interestingly, these metrics in fact share the similarity of using the gradients of initialized model parameters in their calculations. Based on these facts, we propose the following hypothesis to explain the similar performances achieved by different training- frreing--reeeeee metrics in Sec. S.c. The training-free metrics in Sec. [.2 may be theoretically connected and hence could provide similar characterization for the generalization performances of neural architectures. We validate this hypothesis affirmatively and use the following theorem to establish the theoretical connections among these metries.
Theorem 1. Let the loss function e(.--) in gradient-based training-free metrics be B-Lipschitz con- tinuous and 7- L-piscchizz smooth in the first argument. There exist the constant C1. C2 C3 > 0 such that the following holds with a high probability,
Mara S CiAreece MSNIP S C2aMrece: MGraP S OyMrrace.
The proof of Theorem I are given in Appendix A.1 Notably, our Theorem I Jimplies that with high probability, architectures of larger MGrad MMsIP or MMerad will also achieve a larger Minse given the inequalities above. That is, the value of MGrad MASIIP and MMra for different architectures in the NAS search space should be highly correlated with the value of .Mrraee. As a consequence, these training-free metrics should be able to provide similar estimation of the generalization performances of architectures (validated in Sec. (..2 and hence similar performances can be achieved when using these metrics (validated in Sec. (..4). Overall, the training-free NAS metrics from Sec. 3.2 can all be theoretically connected with MTrae despite their distinct mathematical forms. Note that though our Theorem [ is only able to establish the theoretical connections between MTrace and other training-free metrics, our empirical results in Appendix [. fürther reveal that any two training-free metrics from Sec. 3.2 will also be highly correlated. Interestingly, these results also serve as principled justifications for the similar performances achieved by these training-fie free metrics in [9].
4.2 A Generalization Bound Induced by Training-free Metries
Let dataset (a;; y/:) } be randomly sampled from a data distribution D, we denote C.(-) as the training error on S and (-).) as the corresponding generalization error on D. Intuitively, smaller generalization error indicates a better generalization performance. Thanks to the common theoretical underpinnings of gradient- basee training- free metrics formalized by Theorem [] can perform unified generalization analysis for DNNs in terms of these metrics by making use of the NTK theory
[3]. Define E(F, y) A ( (f- /2 and 170 & min min(2n - "(Amin ( ) + Ammxmma- (max((xx)) (0x)) m> (Op)
with Amin (.), Amax (-) being the minimum and maximum eigenvalue of a matrix respectively, we derive the following theorem:
Theorem 2. Assume || l S and f(x;, 0o), Amin (00), ys E [0, 1] for any (æi, y1) E S. There exists a constant N E N such that for any n >> N. when applying gradient descent with learning rate r) < Yo, the generalization error of Jt at time t. >> O can be bounded as below with a high probability,
fD( S (s(s)) + O(s/M).
Here, M can be any metric in Sec. 3.2 and K. A Amax (0o) Amii @o) is the condition number of Oo-
Its proof is in Appendix and and the second term (ssM)) in Theorem 2 represents the generalization gap of DNN models. Notably, our Theorem 2 provides an explicit theoretical connection between the gradient- training- -free metrics from (.22 and the generalization gap of DNNs, which later serves the foundation to theoretically interpret the compelling performances achieved by existing training-free NAS algorithms (Sec. [.3)). Compared to the traditional Rademacher complexity [18] these training-free metrics provide alternative methods to measure the complexity of DNNs when estimating the generalization gap of DNNs.
4.3 Concrete Generalization Guarantees for Training-Fres NAS
Since the Ls(:) in our Theorem may also depend on the training- free metric M, it also needs to be taken into account when analyzing the generalization performance (or the generalization error
(D(()) for training-free NAS methods. To this end, in this section, we derive concrete generalization guarantees for NAS methods using training-free metrics by considering two different scenarios (i.e., the realizable and non- non-realizable scenarios) for the training error term Ls(.) in Theorem 2 which finally give rise to principled interpretations for different training- free NAS methods 779

---

The realizable scenario. Similar to [8 we assume that zero training error (i.e., (f() - 0 when is sufficiently large) can be achieved in the realizable scenario. By further assuming that the condition number in Theorem is bounded by Ko for all candidate architectures in the search space, we can then derive the following generalization guarantee (Corollary I for the realizable scenario.
Corollary 1. Under the conditions in Theorem [ for Se convergence (i.e., + oo) in the realizable scenario and for any mraining-free metric M from Sec. 3.2 the following holds with a high probability,
CD(ft) - OL1MM)
Importantly, Corol- lary suggesss that in the realizable scenario, the generalization error of DNNs is negatively correlated with the metrics from Sec. 3.2 That is, an architecture with a larger value of training-fie ffree metric M generally achieves an improved generalization performance. This implies that in order to select can simply maximize .M to find A arg max (MA) where A denotes any architecture in the search space. Interestingly, this formulation aligns with the training- free NAS method from [9), which has made use of the metrics Monad MSNIP and Momsp to achieve good empirical performances. Therefore, our Corollary provides a valid generalization guarantee and also principled justification for the method from
Corollary is obtained by introducing (f( = 0 and K I No into Theorem 2
well-performing architectures,
The non-realizalle scenario. In practice, different candidate architectures in a NAS search space typically have diverse non-zero training errors 8 and 77) Therefore, the assumptions of the zero training error and the bounded k in the realizable scenario above may be impractical. In light of this, we drop these two assumptions and derive the following generalization guarantee (Corollary (2) for the noa-realizable scenario, which, interestingly, facilitates theoretically grounded interpretations for the training-free free NAS methods from [8 7
Corollary 2. Under the conditions in Theorem 2 for any fe at time > O and any training traeeing-free metric M from Sec. 3.2 in the non-realizable scenario. there exists a constant >> O such that with a high probability,
Co(fi) - nM// O(sMM).
Its proof is given in Appendix A.3 Notably, our Corollary 2 suggests that when M E [0, /mC/n an architecture with a larger value of the metric M will lead to a better generalization performance because such a model has both faster convergence (i.e., the first term decreases faster w.r.t time t) and a smaller generalization gap (i.e., the second term smaller). Interestingly, Shu et al. (8 have leveraged this insight to introduce the training-fir free metric of Mizaee with constraint, which has achieved a higher correlation with the generalization performance of architectures than the metrics from (9. This therefore implies that our Corollary followed by [8] provides a better characterization of the generalization performance of architectures than Corollary followed by 9 since the non- realizable scenario we have considered will be more realistic than the realizable scenario as explained above. Meanwhile, Corollary 2 also suggests that there exists a trade-off in terms of M between the model convergence (i.e., the first term) and the generalization gap (i.e., the second term) when M VmC/n, which surprisingly is similar the empirically motivated trainability and expressivity trade-off in [7]. In addition, Corollary also indicates that for architectures achieving similar values of MM, the ones with smaller condition numbers generally achieve better generalization performance. Interestingly. such a result also aligns with the conclusion from 77. Therefore, our Corollary 2 also provides a principled justification for the training-fre free NAS method in [7].
4.4 Connection to Architecture Topology
Interestingly, we can prove that the condition number x in our Corollary 2 is theoretically related to the architecture topology, i.e., whether the architecture is wide (and shallow) or deep (and narrow), to further support the practicality and the superiority of our Corollary 2 In particular, inspired by the theoretical analysis from [19, we firstly analyze the eigenvalues of the NTK matrices of two different architecture topologies (i.c., wide vs. deep architectures), which gives us an insight into the difference between their corresponding k. We mainly consider the following wide (i.e., f) and deep (i.e., f') architecture illustrated in Figure respectively:
f(x) 1 ΣL_ W f((x) 1 1 w()x
(5)
5

---

where W E R for any i E (1, .L. using the standard normal distribution. Here, denotes an n-dimensional vector with every element being one. Let O and @ be the NTK matrices of and f' that are evaluated on the finite dataset
} and every element of W is independently initialized
= (ax,, yi) 1 respectively, we derive the following theorem:
Theorem 3. Let dataset S be normalized using its statistical mean and covariance such that B|x] 0
and X X = I given X _ 12 Lmm. we have
O Ln I, E [[O]] Ln I.
Its proof is in Appendix A.4 Notably, Theorem 3 shows that the NTK matrix of the wide architecture in (5) is guaranteed to be a scaled identity matrix, whereas the NTK matrix of the deep architecture in (5) scaled identity matrix only in expectation over random initialization. Consequently, we always have K = 1 for the initialized wide architecture, while K > with high probability for the initialized deep architecture. Also note that as we have discussed in Sec.
our Corollary 2 shows that (given similar values of .M) an architecture with smaller x. is likely to generalize better. Therefore, this implies that wide architectures generally achieve better generalization performance than deep architectures (given similar values of M). This, surprisingly, aligns with the findings from 19 which shows that wide architectures are preferred in training- -haiiigd- NAS due to their competitive performances in practice, thus further implying that our Corollary [ more practical and superior to our Corollary [ More interestingly, based on the definition of Miraee 4 Theorem also indicates that deep architectures are expected to have larger values of MTrane (due to the larger scale of IE [O]] for deep architectures) and hence achieve larger model complexities than wide architectures.
Hybrid Neural Architecture Search
5.1 A Unified Objective for Training-Free NAS
Our theoretical understanding of training-free NAS in Sec. finallly allows us to address the following question in a principled way: How can consistently boost existing training-free NAS algorithms? Specifically, to realize this target, we propose to select well-performing architectures by minimizing the upper bound on the generalization error in Corollary given any training-free metric from Sec. 3.2
We expect this choice to lead to improved performances over the method from [9] because Corollary 2 provides more practical generalization guarantee for training- free NAS than Corollary followeed by
[9] (Sec. 4.3) Formally, let A be any architecture in the search space and let M be any training- free
metric from Sec. 3.2 then NAS problem can be formulated below in a unified manner:
min (m (A)/0) + (x(A))/M(A))
(6)
We further reformulate 6 into the following form:
min (inx((A)(M))) + (M) -
where F(x) A 222 and μ and are hyperparameters we introduced to absorb the impact of all other parameters in (6). Coompared with the diverse form of NAS objectives in 77 our 7 presents non-trivial unified form of NAS objectives for all the training-free metrics from Sec. 3.2 making
easier for practitioners to deploy NAS with different types of evaluated training-free metrics. Our
NAS objective in (7) is a natural consequence of our generalization guarantee in Corollary 2 and therefore will be more theoretically grounded, in contrast to the heuristic objective in [7]. Moreover, our (7) advances the training-free free NAS method based on M from [8) because our 7 (a) is derived from the generalization error instead of the training error (that is followed by (8)) of DNNs, which therefore will be more sound and practical, (b) have unified all the gradient-
training-fic ffree metrics from Sec. [3.2] and (c) have considered the impact of condition number which is shown to be critical in practice (see our Appendix C.2). Above all, our unified NAS objective in ( is expected to be able to lead improved performances over other existing training-free NAS methods.
5.2 Optimization and Search Algorithm
Our theoretically motivated NAS objective in 7 has unified all training-fres metrics from Sec. 3.2 and improved over existing training-free free NAS methods. However, its practical deployment requires

---

Algorithm 1: Hybrid Neural Architecture Search (HNAS)
1: Input: Training and validation dataset, metric M evaluated on architecture pool P, F()) for
evaluation history Ho = Ø, a BO algorithm B, number of iterations/queries K
2: for iteration i 1..... K do
3: Choose μk,, Ms using the BO algorithm B
4: Obtain the optimal candidate A in P by solving 77)
5: Evaluate the validation performance of Ai. e.g., (Aa)) after training A
6: Update the GP surrogate in the BO algorithm using the evaluation history
H/.- H U {((Me) vk), Lval (Aa)))
7: end for
8: Select the final A with the best validation performance, e.g., A arg min AE (A)
0:go
rng
0277
6-
0.0
5.0
Modi
Maur
Mover
Mosi
Macer
(a) MAS-Bench--11
(b) NAS-Bench-200
Figure 1: Spearman correlation between MTrwe and other training- free metrics from Sec. 3.2 which are evaluated in NAS-Bench- 101/201. The correlation coefficient r is given in the corner of each plot.
the determination of the hyperparameters μl and v which can be non-trivial in practice. To this end, further introduce Bayesian optimization (BO) 20 to optimize the hyperparameters μ and in order to maximize the true validation performance of the architectures selected by different j and v. In particular, BO uses Gaussian process (GP) as surrogate model the objective function (i.e., the validation performance here) in order to sequentially choose the queried inputs (i.e., the values of μ and v). This finally completes our theoretically grounded NAS framework called hybrid NAS (HNAS), which not only novelly unifies all training-free metries from Sec. 3.2 but also boosts NAS algorithms based on these training-free metries in a principled way (Algorithm
Specifically, in every iteration & of HNAS, we firstly select the optimal candidate Ag by maximizing our training-free free NAS objective in 7 using the values of μ and queried by the BO algorithm in the current iteration (line 3-4 of Algorithm D. Next, we evaluate the validation performance of A (e.g., validation error (Ai)) and then use it to update the GP surrogate that is applied in the BÔ algorithm (line 5-6 of Algorithm[]] T). which then will be used to choose the values of μs and v in the next iteration. After HNAS completes, the final selected architecture is chosen as the one achieving the best validation performance among all the optimal candidates, c.g., A' = arg min (AE))_ (-A) (see Appendix B.I for more optimization details of Algorithm D.. Thanks to the utilization of validation performance as the objective for BO, our HNAS is expected be able enjoy the advantages of both training-free (i.e., the superior search efficiency) and training- basedd NAS (i.c., the remarkable search effectiveness) as supported by our extensive empirical results Sec. 6.4 In addition, by novelly introducing BO to optimize the low-dimensional continuous hyperparameters y and rather than the high-dimensional discrete architectural hyperparameters the NAS search space, HNAS is able to avoid the issues of high-dimensional discrete optimization that standard BO algorithms usually attain when they are directly applied for NAS [2]), allowing HNAS to be more efficient and effective in practice as empirically supported in our Sec. 6.4
6 Experiments
6.1
Connections among Training-Fres Metrics
We firstly validate the theoretical connections between Mirace and other training-free metries from Sec. 3.2 by examining their Spearman correlations for all architectures in MAS-Bench. 101 22 and
Of note, we usually fix = 1, which is already reasonably good for F(-). So, the practical deployment of will mainly be affected by the choice of μ and
7
7

---

Table 1: Correlation coefficients between the test Table 2: Comparison of topology, M & K of errors evaluated on CIFAR-10 and the generaliza- different architectures. The topology width/depth tion guarantees in Sec. for the architectures in of each architecture is followed by the maximum value in the search space (separated by a slash).
NAS-Bench-10 10--2e0ch--00/01..
Metric
MAS-Bench-100
NAS-Bench-201
Architecture
Topology
MYnas
PC
Spearman
Kendall's
Spearman
Kendall's Tau
Width
Depth
Realizable scenario
NASNet
5.0/5.0
2/6
3112
118141
Mari
-025
0.64
MaxP
0.21
0.15
0.64
0.47
AmoebaNet
4.0/5.0
4/6
36422
1104:39
Monse
-0.55
0.57
ENAS
5.0/5.0
2/6
36#22
98+333
Monss
-0.30
0.21
0.54
0.39
DARTS
3.5/4.0
3/5
33++2
122+-58
Non-realizable scenario
SÑAS
4.0/4.0
2/5
31+22
126++47
Mons
0,35
0.23
0.75
0.56
WIDE
4.0/4.0
2/5
27:11
141::36
Masar
0,37
0.25
0.75
0.56
DEEP
1.5/4.0
5/5
131:16
209=107
Mause 0.46
0.32
0.69
0.50
Munsee
0.33
0.23
0.70
0.51
NAS-Bench-201 [23] with CIFAR-10 24 Figure T illustrates the result where all these training-free metrics are evaluated using batch (with size 64) of sampled data following that of [9]. Of note, will follow the same approach to evaluate these training-five metrics in our following sections. The results in Figure show that MTrace and other training-fiee free metrics from Sec. 3.2 are indeed highly correlated since they consistently achieve high positive correlations in different search spaces. These empirical results actually align with the interpretation of our Theorem T (Sec. 4.1). Moreover, the correlation between any two training-fres metrics from Sec. 3.2 is in Appendix which further verifies the connection among all these training-free metrics. Above all, in addition to the theoretical justification in our Theorem our empirical results have also supported the connections among all the training-free metrics from Sec. 3.2
6.2 Generalization Guarantees for Training-Free NAS
We then demonstrate the validity of our generalization guarantees for training-free NAS (Sec. by examining the correlation between the generalization bound in the realizable (Corollary realizable (Corollary 2 scenario and the test errors of architectures in SesS--Bncc-100 101/201. Similar HNAS (Algorithm D). we employ BO with sufficiently large number of iterations (e.g., hundreds of iterations) to determine the non-trivial parameters in Corollary Table [ summarizes the results on CIFAR-I0 where a higher positive correlation implies better agreement between our generalization guarantee and the generalization performance of architectures. Notably, the generalization bound in the realizable scenario performs a compelling characterization of the test errors in NAS-Bench-201 with relatively high positive correlations, whereas it fails to provide precise characterization in 101. Remarkably, our generalization bound in the non-realizable
I or non-
larger search space, i.e., scenario is able to perform consistent improvement over it by obtaining higher positive correlations. These results imply that the Corollary I may only provide a good characterization for training- -free NAS in certain cases (c.g.. in the small-scale search space NAS- DeS--Bench-20- whereas our Corollary 2 generally is more valid and robust in practice. As a consequence, our (6) following Corollary should be able improve Interestingly, the comparable results achieved by all training-free metrics from Sec. 3.2 again validate the connections among these metrics (Theorem []. Moreover, our additional results in Appendix C.2
the NAS objective following Corollary aas we have justified in Sec.
further confirm the validity and practicality of our generalization guarantees for training-free NAS.
6.3 Connection to Architecture Topology
To support the theoretical connections between architecture topology (wide vs. deep) and the value of training-free metric MTrace as well as the condition number K shown in Sec. [4.4 we compare the
topology width/depth, Mirace and of the architectures selected by different SOTA training-based
NAS algorithms in the DARTS search space, including NASNet [25). AmoebaNet (26). ENAS [4] DARTS (5), and SNAS [27]. Table summarizes the results where we apply the same definition of topology width/depth in [19 (refer to 19 for more details). We also include the widest (called WIDE) and the deepest (called DEEP) architecture the DARTS search space into this comparison. As shown in our Table wide architectures (i.e., all architectures except DEEP) consistently achieve lower condition number x and smaller values of M than deep architecture (i.e., DEEP), which aligns with our theoretical insights in Sec. 4.4
8

---

Table 3: Comparison of NAS algorithms in WAS-Bench-221. The result of HNAS is reported with the mean and standard deviation of 5 independent searches and its search costs are evaluated on a Nvidia 1080Ti. C & D in the last column denote continuous and discrete search space, respectively.
Test Accuracy (%)
Algorithm
Cost (GPU Sec.)
Method
Applicable Space
C10
C100
IN-16
ResNet 28
93.97
70.86
43.63
manual evolution random RI.
REAT
93.92-+0.30
71.84+0.99
45.15++0.89
12000
C& D
RS (w/o s
03.70-10.36
71.04=1.07
44.57:11.25
12000
C& D
REINFORCE
93.85++0.37
71.71+1.099
45.24+1.118
12000
C& D
BOHB
93.61
1..85
14.42:11.49
12000
BO+bandit
C& D
ENAS 4
93.76=00.00
71.11=0.00
41.44+0.00
15120
RI gradient
C
DARTS (1st)²
5
54.30=0.00
15.61=0.00
16.32+0.00
16281
C
DARTS (2nd)
54.30.10.00
15.61=0.000
16.32:10.00
43277
gradient
GDAS 29
03.44+0.06
70.61+0.21
42.23+0025
8640
gradient
DrNAS 30
93.98
1..31
44.02.13.24
14887
gradient
NASWOT 6
92.96=00.11
6..98+1122
44,44
306
training-free training-free
C& D
TE-NAS 7
93.90-1047
7..24
42.38:40.46
1558
C
KNAS 12
93.05
68.91
34.11
4200
training-free
C D
NASI 3
93.55=0.10
71.20-0.14
44.84111.11
120
training free
GradSign 31
93.31+0.47
70.33+1.28
42.42+2.81
training-fri freen
C D)
HNAS (Moma))
94,0410.21
7..75-1.044
45.91
3010
hybrid
C& D
HNAS (MMsIPP)
93.94=0002
71.49=0.11
46.07=0.14
2976
hybrid
C& D
HNAS (MMmsp))
94.13
7..59
46.24.10.38
3148
hybrid
C& D
HNAS (Mrace)
94.07=10.10
7..30
45.93
3006
hybrid C& D
Optimal
94.37
73,51
47.31
1 Reported by Dong and Yang [23]
: Re-evaluated using the codes provided by Dong and Yang 23
Re-evaluated under comparable search budget as other training-based NAS algorithms with first-order optimization, egg., FNAS and DARTS (Ist). Note that this search hudget is smaller than the one reported in its original paper and hence will lead to decreased search performances.
6.4 Effectiveness and Efficiency of HNAS
To justify that our theoretically motivated HNAS is able to enjoy the advantages of both training- -free (i.e., the superior search efficiency) and training-based (i.e., the remarkable search effectiveness) NAS, we compare it with other baselines in NAS-Bench-201 (Table We refer to Appendix B.22 for our experimental details. As summarized in Table 3 HNAS, surprisingly, advances both training-based based and training-fre frre baselines by consistently selecting architectures achieving the best performances, leading to smaller gaps toward the optimal test errors in the search space. Meanwhile, HNAS requires at most 13x lower search costs than training-base NAS algorithms, which is even smaller than the training-frre free baseline KNAS. Moreover, thanks to the superior evaluation efficiency of training- free metrics, HNAS can be deployed efficiently in not only continuous (where search space is represented as a supernet) but also discrete search space. As for NAS under limited search budgets (Figure ( HNAS also advances all other baselines by achieving improved search efficiency and effectiveness. Appendix C.5 further includes the impressive search results achieved by HNAS on CIFAR- and NetgeNet in the DARTS search space. Overall, our HNAS is indeed able to enjoy the advantages of both training-free (i.e., the superior search efficiency) and training- based NAS (i.e., the remarkable search effecttivnness), which consistently boosts existing training- free NAS methods.
Conclusion & Discussion
This paper performs a unified theoretical analysis of NAS algorithms using gradient- cradient-based training- free metrics, which allows us to (a) theoretically unveil the connections among these training-free ffee metries, (b) provide theoretical guarantees for the empirically observed compelling performance of these training- free NAS algorithms, and (c) exploit these theoretical understandings to develop novel framework called HNAS that can consistently boost existing training-free NAS. We expect that our theoretical understanding to provide valuable prior knowledge for the design of training- free

---

C10
C100
IN-16
8.0
60
Test Error (%)
58
30
56
28
6.0
54
Opt
Opt
Opt
5000
10000
15000
5000
10000
15000
5000
10000
15000
Search Budget (seconds)
BOHB
RANDOM * REA * REINFORCE
GDAS
ZERO-COST HNAS
Figure 2: Comparison between HNAS (MTrace) and other NAS baselines
under
varying search budgets. Here, the ZERO-COST method is borrowed from [ by using M Note that each algorithm is reported with the mean and standard error of ten independent searches, and the black dashed line in each plot denotes the the minimal (optimal) test error that can be achieved by the architectures in MAS-Bench-201 201 on the corresponding dataset.
metrics and NAS search space in the future. Moreover, we expect our theoretical analyses for DNNs be capable of inspiring more theoretical understanding and improvement over existing machine learning algorithms that are based on DNNs, e.g., the recent training- taining-free free data valuation algorithm [32] In addition, the impressive performance achieved by our HNAS framework expected be able to encourage more attention to the integration of training-free free and training-based approaches in other fields in order to enjoy the advantages of these two types of methods simultaneously.
Acknowledgments and Disclosure of Funding
This rescarch/project is supported by the National Research Foundation Singapore and DSO National Laboratories under the Al Singapore Programme (AISG Award No: AISG2-RP-2020-00 and by STAA under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Funds (Award A20H6b0151).
10

---

References
[1] Felix Stahlberg. Neural machine translation: A review and survey. 2020.
[2] Zhong-Qiu Zhao, Peng Zheng, Shou-tao Xu, and Xindong Wu. Object detection with deep learning: A review. IEEE Trans. Neural Networks Learn. Syst. 30:3212-3232, 2019.
[3] Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In Proc. ICLR, 2017.
[4] Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In Proc. ICML, 2018.
[5] Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In Proc. ICLR, 2019.
[6] Joseph Mellor, Jack Turner, Amos J. Storkey, and Elliot Crowley. Neural architecture search without training. In Proc. ICMI., 2021.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: theoretically inspired perspective. In Proc. ICLR, 2021.
[8] Yao Shu, Shaofeng Cai, Zhongxiang Dai, Beng Chin Ooi, and Bryan Kian Hsiang Low. NASI: Label- and data-agnostic neural architecture search at initialization. In Proc. ICLR, 2022.
[9] Mohamed S. Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas D. Lane. Zero-cost proxies for lightweight NAS. In Proc. ICLR, 2021.
[10] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip H. S. Tomr SNIP: Single-shot network pruning based on connection sensitivity. Proc. ICLR, 2019.
[11] Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In Proc. ICLR, 2020.
[12] Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. KNAS: Green neural architecture search. In Proc. ICML, 2021.
[13] Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural Tangent Kernel: Convergence and generalization in neural networks. In Proc. NeurIPS, 2018.
[14] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Proc. NeurIPS, 2019.
[15] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over-paramettrizztion. In Proc. ICML. 2019.
[16] Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Proc. NeurlPS, 2019.
[17] Greg Yang and Etai Littwin. Tensor programs Пb:: Architectural universality of neural tangent kernel training dynamics. In Proc. ICML, 2021.
[18] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press, 2012.
[19] Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In Proc. ICLR, 2020.
[20] Jasper Snock, Hugo Larochelle, and Ryan Adams. Practical Bayesian optimization of machine learning algorithms. In Proc. NIPS, 2012.
[21] Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample- and one-shot neural architecture search with BONAS. In Proc. NeurIPS, 2020.
11

---

[22] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS-Bench-101: Towards reproducible neural architecture search. In Proc. ICML, 2019.
[23] Xuanyi Dong and Yi Yang. MAS-Bench-201: Extending the scope of reproducible neural architecture search. In Proc. ICLR, 2020.
[24] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
[25] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V. Le. Learning transferable architectures for scalable image recognition. In Proc. CVPR, 2018.
[26] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In Proc. AAAI, 2019.
[27] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: Stochastic neural architecture search. In Proc. ICLR, 2019.
[28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proc. CVPR, 2016.
[29] Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four GPU hours. In Proc. CVPR, 2019.
[30] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. DrNAS: Dirichlet neural architecture search. In Proc. ICLR, 2021.
[31] Zhihao Zhang and Zhihao Jia. Gradsign: Model performance inference with theoretical insights. In Proc. ICLR, 2022.
[32] Zhaoxuan Wu, Yao Shu, and Bryan Kian Hsiang Low. DAVINZ: Data valuation using deep
neural networks at initialization. In Proc. ICML, 2022.
[33] Beatrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model selection. Annals of Statistics, pages 3332-138, 2000.
[34] Pranjal Awasthi, Natalie Frank, and Mehryar Mohri. On the rademacher complexity of linear hypothesis sets. arXiv:2007.1 1045, 2020.
[35] Zhongxiang Dai, Yao Shu, and Bryan Kian Hsiang Low. Sample-then-optimizze batch neural thompson sampling. In Proc. NeurlPS, 2022.
[36] Sebastian Shenghong Tay, Chuan Sheng Foo, Daisuke Urano, Richalynn Chiu Xian Leong, and Bryan Kian Hsiang Low. Efficient distributionally robust Bayesian optimization with worst-case sensitivity. In Proc. ICML, 2022.
[37] Zhongxiang Dai, Yizhou Chen, Haibin Yu, Bryan Kian Hsiang Low, and Patrick Jaillet. On provably robust meta- -Byyesia optimization. In Proc. UAI, 2022.
[38] Quoc Phong Nguyen, Sebastian Tay, Bryan Kian Hsiang Low, and Patrick Jaillet. Top-k ranking bayesian optimization. In Proc. AAAI, 2021.
[39] Quoc Phong Nguyen, Zhaoxuan Wu, Bryan Kian Hsiang Low, and Patrick Jaillet. Trusted- maximizers entropy search for efficient bayesian optimization. In Proc. UAI, 2021.
[40] Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Federated Bayesian optimization via Thompson sampling. In Proc. NeurIPS, 2020.
[41] Zhongxiang Dai, Bryan Kian Hsiang Low, and Patrick Jaillet. Differentially private federated Bayesian optimization with distributed exploration. In Proc. NewrIPS, 2021.
[42] Sreejith Balakrishnan, Quoe Phong Nguyen, Bryan Kian Hsiang Low, and Harold Soh. Efficient exploration of reward functions in inverse reinforcement learning via Bayesian optimization. In Proc. NeurIPS, 2020.
12

---

[43] Rachael Hwee Ling Sim, Yehong Zhang, Bryan Kian Hsiang Low, and Patrick Jaillet. Collabo- rative Bayesian optimization with fair regret. Proc. ICML, 2021.
[44] Yehong Zhang, Zhongxiang Dai, and Bryan Kian Hsiang Low. Bayesian optimization with binary auxiliary information. In Proc. UAI, 2019.
[45] Zhongxiang Dai, Haibin Yu, Bryan Kian Hsiang Low, and Patrick Jaillet. Bayesian optimization meets Bayesian optimal stopping. In Proc. ICML, 2019.
[46] Zhongxiang Dai, Yizhou Chen, Bryan Kian Hsiang Low, Patrick Jaillet, and Teck-Hua Ho. R2-B2: recursive reasoning-base based Bayesian optimization for no-regret learning in games. In Proc. ICML, 2020.
[47] Arun Verma, Zhongxiang Dai, and Bryan Kian Hsiang Low. Bayesian optimization under stochastic delayed feedback. In Proc. ICML, 2022.
[48] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proc. ICML, 2010.
[49] Donald R Jones, Matthias Schonlau, and William Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(45):55-492, 1998.
[50] Fernando Nogueira. Bayesian Optimization: Open source constrained global optimization tool for Python, 2014-. URL htt.ttts//giccbbbccmm////// http:///.........//aaaaaaaaattaa
[51] Jack Turner, Elliot Crowley, Michael F. O'Boyle, Amos Storkey, and Gavin Gray, BlockSwap: Fisher-guides block substitution for network compression on a budget. In Proc. ICLR, 2020.
[52] Hidenori Tanaka, Daniel Kunin, Daniel L. Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. In Proc. NeurIPS, 2020.
[53] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative to the CIFAR datasets. arXiv: 1iii:11770008199 2017.
[54] Deng, W. Dong, R. Socher, L.-. Li, K. Li, and L. Fei-Fei. ImageNet: A large-scale hierarchical image database. In Proc. CVPR, 2009.
[55] Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv: 700.00452, 2017.
[56] Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In Proc. CVPR, 2017.
[57] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan L. Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proc. ECCV, 2018.
[58] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimiza- tion. In Proc. NeurIPS, 2018.
[59] Quanming Yao, Ju Xu, Wei-Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In Proc. AAAI, 2020.
[60] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proc. ICCV, 2019.
[61] Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. D Robustly stepping out of performance collapse without indicators. arXiv:2009.01027 2020.
[62] Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation-basee based regularization. In Proc. ICML, 2020.
13

---

[63] Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. Proc. ICLR, 2020.
[64] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proc. CVPR, 2015.
[65] Andrew G. Howard, Menglong Zhu, Bo Chen, Dmitry Kalenichenko, Weijun Wang. Tobias Weyand, Marco Andreetto, and Hartwig Adam. MobileNets: Efficient convolutional neural networks for mobile vision applications. 17Xiv:17040046.11 2017.
[66] Ningning Ma. Xiangyu Zhang, Hai-Tao Tao Zheng, and Jian Sun. ShuffleNet V2: Practical guidelines for efficient CNN architecture design. In Proc. ECCV, 2018.
[67] Mingxing Tan, Bo Chen, Ruoming Pang. Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V. Le. MnasNet: Platform-aware neural architecture search for mobile. In Proc. CVPR, 2019.
[68] Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In Proc. ICLR, 2019.
[69] Yann LeCun, Léon Bottou, Genevieve B. Orr, and KlaustRobert Müller. Efficient backprop. In Neural Networks: Tricks of the Trade (2nd ed.), Lecture Notes in Computer Science pages
9-48. 2012.
[70] Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proc. AISTATS, 2010.
[71] Kaiming He, Xiangyu Zhang. Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proc. ICCV, 2015.
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] See Sec 3.1 i.e., the simplified
analysis on the fully connected neural networks with scalar output.
(c) Did you discuss any potential negative societal impacts of your work? [No] I do not
see any potential negative societal impacts of this paper.
(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 of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect 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]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [No] All assets have used are public.
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "wenRCC9Rrvc", "reviewer": "Reviewer_TdLx", "summary": "This paper came up with the lower bound of generalization error for several gradient based training-free nas methods. They were able to relate training-free metrics such as $M_{Grad}$, $M_{SNIP}$,  $M_{Grasp}$ with the trace of the the NTK-Matrix. The generalization bound for the scenarios where training error is not zero is proportional k/M where $k$ is the ratio of the largest and the smallest eigen values of the NTK matrik and $M$ is the training-free metric. So they came up with a formulation for generalization error based on $k$ and $M$ involving hyperparameters $\\mu$ and $v$\n\nFurther they devised a BO-based NAS algorithm, that searches the hyper parameters for the above formulation. The architecture minimizing the generalization error formulation is found and is trained to obtain its validation performance. The BO's surrogate model is then updated with the validation performance. This is continued and the architecture with the best validation accuracy is returned", "questions": "Instead of training-free and training based hybrid NAS, can we come up with a completely training-free algorithm based on what we know so far? for example what if we just use k/$M_{Trace}$ as the metric?", "limitations": "None", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\nThis is the first paper that is able to relate several gradient based training-free metrics and formulate a generalization bound.\nThe experiments also show that $M_{Grad}$, $M_{SNIP}$ and  $M_{Grasp}$ are highly correlated with $M_{Trace}$\nTheir search algorithm is sample-efficient and is only searching for 2 hyper parameters rather than the entire architecture. ", "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": "cNVnI4f7dju", "reviewer": "Reviewer_VFc4", "summary": "This paper aims to understand the training-free NAS metrics from a theoretical perspective and build a unified theoretical framework to analyze the relationships of gradient-based training-free NAS metrics. Based on the theoretical results, the authors further propose a hybrid NAS (HNAS) method which can enjoy the advantages of both training-free (i.e., superior search efficiency) and training-based (i.e., remarkable search effectiveness) NAS. Experimental results demonstrate the effectiveness of the proposed method.", "questions": "1. In Table 3, could the authors also provide the comparison of query numbers (query of training-free metrics and training-based metrics) of different methods, rather than only the total search costs of GPU time?. In addition, more SOTA methods on NAS-Bench-201 such as DrNAS (DrNAS: Dirichlet Neural Architecture Search, ICLR 2021) are recommended to be included in Table 3. These help to evaluate the proposed HNAS more thoroughly.\n\n2. Could the authors provide the Spearman/K’Tau results between the unified objective in Equation (7)/(6) and Ground truth accuracies? which helps to further show the superiority of HNAS. If this is suitable for evaluating HNAS?", "limitations": "No limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "++The proposed HNAS is well-motivated, technical sound, and theoretically guaranteed. The paper is well-written and easy to follow.\n\n--The experimental results are a bit weak since the authors only conduct experiments on NAS-Bench-201. For better evaluation, results on ImageNet would be more convincing.", "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": "ZV6qJ1KvuGC", "reviewer": "Reviewer_syT9", "summary": "The submission aims to put a stronger theoretical foundation under a set of surrogate metrics that are used in training-free network architecture search and then derive a new method with theoretical and empirical improvement over prior art. \"Surrogate\"  in this context means \"not using data, but only initialized weight parameters\", where an increase in the metric is demonstrated empirically to correlate with better model performance. The authors observe that prior art lacks a common explanation of why these metrics work well in practice and they endeavor to provide a common, explanatory model and subsequently a theoretical and empirical improvement motivated from the proposed explanatory model.\n\nThe new model essentially comes in two steps: (a) deriving an upper bound for the model generalization error as sum of the training error and a function that is related to the inverse ratio of any such surrogate metric (the latter term being a form of generalization gap and the inverse ratio conforming with the empirical observation that larger surrogate metrics correlate with better model performance), and (b) replacing the training error (first term in the upper bound) by an upper bound as function of only the surrogate metric and the number of samples (but not the samples themselves). These two steps lead to an upper bound of the generalization error that is not a function of the samples themselves, but only the surrogate metric (which is assumed to be a function not of the samples itself) and a set of nuisance parameters (some relating to the initialized model weights). Finally, the paper suggest to aggregate the free nuisance parameters (ones that are not a function of the model/weight) into two generic hyperparameters, reducing the upper bound on the generalization error to a function of only two variables and the model structure and weights. The paper goes on to propose optimizing these hyperparameters via Bayesian optimization using Gaussian processes in an iterative two-step process, where the first step is training-free and optimizes the chosen training free metric over the set of possible networks, and the second step updates the Bayesian optimization with the true validation loss of the chosen network.\n\nThe submission exposes several further theoretical connections: (a) demonstrating that one specific metric is an upper bound to the others, (b) relating the condition number of the initial neural tangent kernel to depth and width of networks (under simplifying assumptions), resulting in interpretations that are consistent with earlier empirical results.\n\n", "questions": "Summarizing the above points that would help clarify the exposure better:\n\n1. How is (7) solved in Algorithm 1?\n2. How many iterations K in Algorithm 1 do the presented experiment require? I understand that this is the number of times that an actual training on data is performed in the hybrid setting.\n3. Could you please share more details on the BO in section 5.2? The presented material leaves questions open: What are the open parameters in this optimization, how do the choices influence the optimizations? I feel that this part is important to gauge the overall quality and significance of the paper and it is a bit glanced over.\n\nAs it is I am rating the paper as borderline accept, primarily as I feel that some of the aspects in the questions (1), and (3) are missing to value the full contribution of the submission.\n\n[Update post-rebuttal] I feel that my questions from the review have been addressed well and I am increasing my soundness score (to \"good\") as well as the rating (to \"weak accept\") respectively.", "limitations": "The submission highlights limitations sufficiently.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses an interesting problem (improved bounds and methods for metrics in training-free architecture search). The authors highlight their contributions and put them in the context of prior work reasonably well. I appreciate the novel combination of training free metrics and training-derived performance, both from a theoretical as well as practical perspective.\n\nIt appears that the main contribution of the paper lies in deriving Corollary 2 and subsequently the practical procedure in Sec 5.1. This result appears to generalize several prior art (unified view on training-free metric) as well as bound the generalization performance more tightly than previous models (by making the more realistic assumption of a non-zero achievable training error). To my knowledge this is a substantial, original result and including the subsequent optimization scheme appears to demonstrate favorable results. The empirical results (mainly Table 3) when taken out of context of the theoretical foundation could be seen as not sufficiently convincing: the achieved accuracy is generally slightly better than the compared methods, but the runtime is significantly worse when compared to some. Admittedly, the acceptable tradeoff between run-time and accuracy may be domain-specific (\"train fast or well\"), thus both priorities have their value. The slight accuracy improvement, most prominent on the IN-16 dataset, is consistent with the presented theoretical perspective and thus good substantiation of the former. From an empirical perspective, it may perhaps be insightful to test the method in a NAS regimen where the current state of the art is still far worse than the true best accuracy to highlight a different, valuable trade off between accuracy and training time.\n\nI had some issues with the clarity and coherence of the paper:\n- There are two parts that on first reading appear disjoint with the rest of the paper. First, the relation between the metrics in theorem 1 does not appear to have a bearing on the subsequent deductions. Only after following the proof in appendix A3 the importance becomes clearer. This is a minor point and could be improved by explicitly stating the relation of Theorem 1 to Corollary 2 in the main paper. Secondly, and also very minor by itself, Section 4.4 does not seem to serve a purpose in the main paper except for highlighting speculative connections based on assuming models of simple topologies (deep vs. wide). I feel that the paper would benefit from either omitting or expanding this section.\n- More importantly, there appear to be details missing that I would find significant: (a) how is the Bayesian optimization implemented, and (b) how is (7) solved for in Algorithm 1.\n\nOriginality: The paper is an extension of previous work that adds original thought and explorations.\nQuality: The paper is written well, it puts the presented work in context well and combines theoretic with empirical results.\nSignificance: The main significance as it is exposed appears to me in Corollary 2 and the subsequent derivations of a practical optimization scheme for training-free/hybrid NAS. The significance of this result would be more empirically evident if the empirical results would show achievable trade-offs between accuracy and training time more differentiated from the state of the art as it does now.", "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": "WyOSZgkmfj", "reviewer": "Reviewer_cbB5", "summary": "This paper theoretically derives the connections among existing gradient-based metrics for training-free neural architecture search, and then develops a generalization bound based on these metrics, which explains why these metrics are correlated with model performance in a rigorous way. Two cases (zero and non-zero training error) are further analyzed. Based on the theoretical results, a unified objective and its corresponding BO-based search algorithm (HNAS) are proposed. Experiments on popular NAS benchmarks are conducted to show the validity of the theoretical results and the proposed algorithm. ", "questions": "See the weakness concerns listed in the last section. ", "limitations": "I do not see an explicit discussion about the limitations of the method in this paper. \n\nThere is no concern about negative societal impact. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well organized and has a clear presentation. \nThe theoretical perspective is very interesting. The generalization bound offers a unified view to inspect and interpret current training-free NAS metrics. I mainly have the following concerns:\n\n1.\tThe term O(k/M) plays the role of generalization gap. In M_{trace}, the trace norm of neural tangent kernel is highly correlated with gradient norm. The eigenvalues of neural tangent kernel matrix also affect gradient norm. So, are k and M correlated? How to ensure that decreasing k while increasing M would not cause optimization conflict?\n\n2.\tThe details of the proposed algorithm, HNAS, are not clear enough. How to calculate neural tangent kernel matrix and its eigenvalues efficiently has been a problem due to the large parameter dimension and the large number of samples in a dataset. So, the detailed process of solving Eq. (7) should be described. Besides, the BO step to optimize \\mu and \\nu is also unclear. Is the validation performance differentiable to BO? Detailed description should be offered. \n\n3.\tThe authors should compare their proposed NAS algorithm with simply using the metrics. For example, replace Eq. (7) with \\max M_{grad}, M_{snip}, M_{grasp}, or M_{Trace}, to show the effectiveness of the upper bound in Corollary 2, and the importance of BO. Besides, more recent NAS methods, such as [1], should be compared with. \n\n[1] Zhang et al., GradSign: Model Performance Inference with Theoretical Insights, ICLR 2022.\n\n", "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