ZiCo: Zero-shot NAS via inverse Coefficient of Variation on Gradients
Authors: Guihong Li
Yuedong Yang
Kartikeya Bhardwaj
Radu Marculescu
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Neural Architecture Search
Zero-shot NAS
Gradient Analysis
Training Convergence

Abstract: Neural Architecture Search (NAS) is widely used to automatically obtain the neural network with the best performance among a large number of candidate architectures. To reduce the search time, zero-shot NAS aims at designing training-free proxies that can predict the test performance of a given architecture. However, as shown recently, none of the zero-shot proxies proposed to date can actually work consistently better than a naive proxy, namely, the number of network parameters (#Params). To improve this state of affairs, as the main theoretical contribution, we first reveal how some specific gradient properties across different samples impact the convergence rate and generalization capacity of neural networks. Based on this theoretical analysis, we propose a new zero-shot proxy, ZiCo, the first proxy that works consistently better than #Params. We demonstrate that ZiCo works better than State-Of-The-Art (SOTA) proxies on several popular NAS-Benchmarks (NASBench101, NATSBench-SSS/TSS, TransNASBench-101) for multiple applications (e.g., image classification/reconstruction and pixel-level prediction). Finally, we demonstrate that the optimal architectures found via ZiCo are as competitive as the ones found by one-shot and multi-shot NAS methods, but with much less search time. For example, ZiCo-based NAS can find optimal architectures with 78.1%, 79.4%, and 80.4% test accuracy under inference budgets of 450M, 600M, and 1000M FLOPs, respectively, on ImageNet within 0.4 GPU days. Our code is available at https://github.com/SLDGroup/ZiCo.



Published as a conference paper at ICLR 2023
ZiCo: ZERO-SHOT NAS VIA INVERSE COFFFICIENT OF VARIATION ON GRADIENTS
Guihong Li', Yuedong Yang', Kartikeya Bhardwaj²; Radu Marculescu
'Te University of Texas at Austin, ?Qualcomm {1gh, albertyoung, radum) (adumm@uteexe @utexas edu, kbhardwa@qti. qual comm, com
ABSTRACT
Neural Architecture Search (NAS) is widely used to automatically obtain the neu- ral network with the best performance among a large number of candidate archi- tectures. To reduce the search time, zero-shot NAS aims at designing training-free proxies that can predict the test performance of given architecture. However, shown recently, none the zero-shot proxies proposed to date can actually work consistently better than naive proxy, namely, the number of network parameters (#Params). To improve this state of affairs, as the main theoretical contribution, we first reveal how some specific gradient properties across different samples impact the convergence rate and generalization capacity of neural networks. Based on this theoretical analysis, we propose new zero-shot proxy, ZiCo, the first proxy that works consistently better than #Params. We demonstrate that ZiCo works bet- ter than State-Of-The- (SOTA) proxies on several popular NAS-Benchmarks SisSSBenc-SSSSSSSS
TransNASBench--100 101) for multiple ap- plications (e.g.. image clasifiiation/recosstuuttii and pixel-level prediction). Fi- nally, we demonstrate that the optimal architectures found via ZiCo itive as the ones found by one-shot and multi-shot NAS methods, but with much less search time. For example, ZiCo-based NAS can find optimal architectures with 78. 1%, 79,4% 79,4%, and 80.4% test accuracy under inference budgets of 450M, 600M, and 1000M FLOPs, respectively, ImageNet within 0.4 GPU days. Our code is available at /tttps://gitnni com SLDGroup/ ZiCo
(NASBench 101,
compet-
INTRODUCTION
During the last decade, deep learning has achieved great success in many areas, such as computer vision and natural language modeling Krizhevsky
(2012; Liu Deng (2015); Huang et al.
(217);; He et al. (2016); Dosovitskiy et al. (2021) Brown et al. 2020); Vaswani et al. (2017). In recent years, neural architecture search (NAS) has been proposed search for optimal architectures, while reducing the rial-and-erro (manual) network design efforts Baker et al. (2017); Zoph & Le)
2017); Elsken al. (2019). Moreover, the neural architectures found via NAS show better perfor-
mance than the manually-designed networks in many mainstream applications Real et al.
(0017)
Gong et al. (2019); | Xie et al. (2019); 9. Wu et al. (2019); Wan et al. (2020); Li & Talwalkar 2020
Kandasamy al. (2018); Yu et al. (2020b); Liu et al. (2018b); Cai et al. (2011 2018)) Zhang et al.
2019a);
Zhou et al. (2019) Howard et al. 2019); Li et al. (2021b).
Despite these advantages, many existing NAS approaches involve time-consuming and resource- intensive search process. For example, multi-shot NAS uses a controller or an accuracy predictor to conduct the search process and it requires training of multiple networks; thus, multi-shot NAS is extremely time-consuning |Raal et al. (001)); Chiang et al. (2019). Alternatively, one-shot NAS merges all possible networks from the search space into supernet and thus only needs to train the supernet once Dong & Yang (2019); Zela et al. (2020); Chen et al. (2019); Cai et al. (2019); Stamoulis al.) (2019); CCuu al. (2021): Guo et al. (2020): Li al. (2020): this enables one- shot NAS to find good architecture with much less search time. Though the one-shot NAS has significantly improved the time efficiency of NAS, training is still required during the search process.
Work done while Kartikeya Bhardwaj was Arm, Inc.

---

Published as a conference paper at ICLR 2023
Recently, the zero-shot approaches have been proposed to liberate NAS from training entirely Wu ct al. (2021); Zhou et al. 2022, 2020): Ingolfsson et al. (2022); Tran & Bae (202T); Do & Luong (202)) Tran al. (2021 Shu et al. (2022)); et al. (2022). Essentially, the zero-shot NAS utilizes some proxy that can predict the test performance of a given network without training. The design of
such proxies is usually based on some theoretical analysis of deep networks. For instance, the first zero-shot proxy called NN-Mass was proposed by Bhardwaj et al. (2019); NN-Mass theoretically links how the network topology influences gradient propagation and model performance. Hence, zero-shot approaches can not only significantly improve the time efficiency of NAS, but also deepen the theoretical understanding on why certain networks work well. While NN-Mass consistently outperforms #Params, it is not defined for generie NAS topologies and works mostly for simple repeating blocks like ResNets/MobileNets/DDeeeeeee shot proxies are proposed for general neural architectures. Nonetheless, as revealed in Ning et al.) (202T): White et al. (2022), these general zero-shot proxies proposed to date cannot consistently work better than naive proxy, namely, the number of parameters (#Params). These results may undermine the effectiveness of zero-shot NAS approaches.
[Bhardwaj et al. (2019). Later several zero-
To address the limitations of existing zero-shot proxies, target the following key questions:
1. How do some specific gradient properties, i.e., mean value and standard deviation across different samples, impact the training convergence of neural networks?
2. Can we use these two gradient properties to design a new wwweetiiaall-groundde proxy that works better than #Params consistently across many different NAS topologies/tasks?
To this end, we first analyze how the mean value and standard deviation of gradients across dif- ferent training batches impact the training convergence of neural networks. Based on our analysis, we propose ZiCo, a new proxy for zero-shot NAS. We demonstrate that, compared to all exist- ing proxies (including #Params), ZiCo has either a higher or at least on-par correlation with the (NASBench101,
test accuracy on popular datasets (CIFAR10/100, ImageNet16- 120). Finally, we demonstrate that ZiCo enables a zero-shot NAS framework that can efficiently find the network architectures with the highest test accuracy compared to other zero-shot baselines. In fact, our zero-shot NAS framework achieves competitive FL FI.OP-aacuuac tradeoff's compared multiple one-shot and multi-shot NAS, but with much lower time costs. To summarize, we make the following major contributions:
for multiple
We theoretically reveal how the mean value and variance of gradients across multiple sam- ples impact the training convergence and generalization capacity of neural networks.
We propose a new zero-shot proxy, ZiCo, that works better than existing proxies popu- lar MAS-Bennhmmarks (NASBench101 NATS
TransNASBench- 101) for multiple applications (image clasification/rcconsttuuiii and pixel-level prediction).
We demonstrate that our proposed zero-shot NAS achieves competitive test accuracy with representative one-shot and multi-shot NAS with much less search time.
The rest of the paper is organized as follows. We discuss related work in Section 2 In Section 3 we introduce our theoretical analysis. We introduce our proposed zero-shot proxy (ZiCo) and the NAS framework in Section 3.44 (ection[4yalidau our analysis and presents our results with the proposed zero-shot NAS. We conclude the paper in Section 5 with remarks on our main contribution.
RELATED WORK
2.1 ZERO-SHOT NAS
The goal of zero-shot NAS is rank the accuracy of various candidate network architectures without training, such that we can replace the expensive training process in NAS with some computation- efficient proxies Xiang et al. (2021a); Javaheripi et al. (2022); Li et al. (2021a). Hence, the quality of the proxy determines the effectiveness of zero-shot NAS. Several works use the number of linear regions to approximately measure the expressivity of a deep neural network MMelor al. (202T): Chen et al.] (2021b): Bhardwaj et al. (2022). Alternatively, most of the existing proxies are derived from the gradient of deep networks. For example, Synflow, SNIP, and GraSP rely on the gradient w.r.t the parameters of neural networks; they are proved to be the different approximations of Taylor expansion of deep neural networks networks/Abdelffttaa Abdelfattah et al. 202 Lee et al. (0019)) Tanaka et al. (2020); Wang et al. (2020). Moreover, the Zen-scort approximates the gradient w.n.t featuremaps and mea- sures the complexity of neural networks Lin et al. (202T): ) (Sun et al. (202T). Furthermore, Jacob cov leverages the Jacobian matrix between the loss and multiple input samples to quantify the capacity
2

---

Published as a conference paper at ICLR 2023
of modeling the complex functions Lopes et al. (2021). Though zero-shot NAS can significantly
celerate the NAS process, has been revealed that the naive proxy #Params generally works better
than all the proxies proposed to date Ning et al. (202I); [hite et al. (2022). These limitations of
existing proxies motivate us to look for new proxy that can consistently work better than #Params and address the limitations of existing zero-shot NAS approaches.
2.2
KERNEL METHODS IN NEURAL NETWORKS
Kernel methods widely explored to analyze the convergence property and generalization capacity of networks trained with gradient descent Neal ( (1996); Williams (1996); : Du et al. (2019a); Lu et al.
Nica (2020); Golikov al. (2022). For example, the training of wide neural networks is proved to be equivalent to the optimization of specific kernel function Arora et al. (019a): Lee et al. (2019a); Chizat et al. (2019); Arora al. (2019b); Cho & Saul (2009). Moreover, given the networks with specific width constraints, researchers proved that the training convergence and generalization capacity of networks can be described by some corresponding kernel| et (2119); (Zhagg et al. (aabb://rrggga-iiii
20200) Allen-Zhu et al. (2019); Hanin
et al. (2019): et al.)
(2019b). In our work, we extend such kernel-based analysis to reveal the relationships between the gradient properties and the training convergence and generalization capacity of neural networks.
3 CONVERGENCE AND GENERALIZATION VIA GRADIENT ANALYSIS
We consider the mean value and standard deviation of gradients across different samples and first explore how these two metrics impact the training convergence of linear regression tasks.
3.1 LINEAR REGRESSION
Inspired by Du et al. (2019)), we use the training set S with M samples as follows:
...,, M, where R is positive constant and ||- denotes the L2-norm of given vector; 24 E Rd is the zth input sample and normalized by its L2-norm (i.e., | = 1), and y; is the corresponding label. We define the following linear model f a optimized with an MSE-based loss function L:
8 ( i
Rdd E R, ||m 1, |ya S R, M> 1}
(1)
f(x;; a)) mina Σjiara: -2))
mina f(zr)())))
where a E IRd is the initial weight vector of f. We denote the gradient of L w.r. to a as g(x;) when taking (xy, y.) as the training sample:
g(xx) = ÖL f(z;;;
(3)
da
We denote the jth element of g(xr,) as 9, (ax)). We compute the mean value (1²) and standard deviation (ar,) of 9ú (z;) across all training samples follows:
M
M
1 M M
1
Σ (as)
1
Σ
(as 2,)
M
Theorem 3.1.
We denote the updated weight vector à and denote Eis (xx)(==))3 G. Assume use the accumulated gradient of all training samples and learning rate update the initial
weight vector a. i.e., à = a 17 E. g(x)). If the learning rate < n7 < 2, then the total training loss is bounded follows:
LUn. ( S M2 - Σng
G "
(5)
In particular, if the learning rate n = t then L(ā) is bounded by:
M
Σ L(y,, f(x;; a)) < 2
Σ 03
(6)
We provide the proof in Appendix A and the experimental results validate this theorem in Sec 4.2
Remark 3./ Intuitively, Theorem. 3.1 tells us that the higher the gradient absolute mean across different training samples, the lower the training loss the model converges to; i.e., the network converges at a faster rate. Similarly, if nM < 1, the smaller the gradient standard deviation across different training samples/batches. the lower the training loss the model can achieve.
3

---

Published as a conference paper at ICLR 2023
3.2 MLPs WITH RELU
In this section, we generalize the linear model to a network with ReLU activation functions. We primarily consider the standard deviation of gradients in the Gaussian kernel space. We still focus on the regression task on the training set S defined in Eq. We consider neural network in the same form as Du et al. 2019b):
m h(:; 8, W) - Vm Σ o ReLU(w,
1
where m is the number of output neurons of the first layer; s, is the pth element in the output weight vector 8; W Rmxd is the input weight matrix, and wr E Rd is the rThh row weight vector in W.
For training on the dataset $ with M samples defined in Eq. we minimize the following loss function:
M
L(s, W)
(h(3 8, W) y1)
(8)
Following the common practice Du et al. (201b)), we fix the second layer (8) and use gradient descent to optimize the first layer (W) with a learning rate f
aLss ( Ow (t - 1)
w. = wr - 1)
==0
where (t- 1) denote the input weight matrix after t training steps; (r) denote the nh row weight vector after i training steps.
Definition 1. (Gram Matrix) A Gram Matrix H() E MMM on the training set {( Ve), = I,..., M) after & training steps is defined as follows:
(t) = x D
M w. (t) 2 0, 2 Wp (t) 2 0}
(10)
m
where Il is the indicator function and 1{A) if and only event A happens. We denote the Amin (F) as the minimal eigenvalue of a given matrix H. We denote the λo = Amin (Ho)))
3.2.1 CONVERGENCE RATE
Theorem 3.2. Given a neural network with ReLU activation optimized by minimizing Eq we assume that each initial weight vector (w,(0),r 1,..,; n1 is i.i.d. generated from (10, I) and the gradient for each weight follows i.i.d. (N0 o). where the a is measured across different training
207/58 steps. For some positive constants and e, if the learning rate n satisfies d) 2MM2220(1-066
then with with probability at least (1 6) e). the following holds true: for any E [m].
[() (t)( C ntto / - c), and at training step the Gram matrix H() satisfies:
Amain (H)))) Amin (H()) 2/2M2 ilt / >0
(11)
VTδ (-) is the inverse cumulative distribution function for a d-degree chi-squared distribution x²
We provide the proof in Appendix B We now introduce the following result from Du et al. (2019b)
to further help our analysis.
Lemma 1. Du et al. (219h) Assume set the number of output neurons of the first layer m
O 2 255 and we i.i.d. initialize wr ~ N0, I) and s, ~ uni [rnfom[([-1,1]] for e [m]. When
minimizing the loss function in Eq. g on the training set S in Eq. 0 with probability at least 1 - 8
over the initialization, the training loss after t training steps is bounded by:
L(s, (I)) < e Ammin (H()) L(s, (W(1- 1))
(12)
Theorem 3.3. Under the assumptions of Theorem 3.2 and Lemma 7
with probability at least (1
5)(1 E), the following inequality holds true:
[(s, (W(()) S Amin (H())) 2w2nd nte (11-6)
VeA
L(s, (W(( 1))
(13)
4

---

Published as a conference paper at ICLR 2023
The proof consists of replacing Amin (t) in Eq. 12 with its lower bound given by Theorem 3.2
Remark 3.4 Theorem. 3.3 shows that after some training steps t, the network with a smaller standard deviation (or) of gradients will have a smaller training loss; i..., the network has a faster convergence rate at each training step. We further validate this theorem in Sec. 4.2
3.2.2 GENERALIZATION CAPACITY
Several prior works show that the generalization capacity of a neural network is highly correlated with its sharpness of the loss function Keskar al. (2017b a): Li et al. (2018); Liang et al. (2019). Usually, a flatter loss landscape leads to a better generalization capacity. Moreover, has also been shown that the largest eigenvalue of the Gram matrix of loss can be used describe the sharpness of the loss landscape Sagun et al. 2018); more precisely:
Proposition 3.4. The lower the largest eigenvalue the the Gram matrix, the higher the generalization
capacity the network. (Lewkowyez al. (2020); Sagun et al. al.[(2016)
Next, we analyze how the gradient of neural network impacts the largest eigenvalues of the Gram matrix and its generalization capacity.
Theorem 3.5. Under the assumptions of Theorem 3.2 for some positive constants â and e, if the /5 learning rate 7) satisfies < 2/2 then with with probability at least (1 (1- 5)(1 for
any E [m], ||w,(() wr (1)l < C = 11100 10 - E), and at training step the Gram matrix
(t) satisfies:
2v2M2 / D
Amaaa (H())) S Xmaz (H(O) +
(14)
TT
(-) is the inverse cumulative distribution function for a d-degree chi-squared distribution (d).
We provide the proof in Appendix C
Remark 3.5 Theorem. 3.5 shows that after some training steps t, the network with a smaller standard deviation (σ)) of gradients will have a lower largest eigenvalues of the Gram matrix; i.e., the network has flatter loss landscape at each training step. Therefore, based on Proposition 3.4 the model will generalize better. We further validate this theorem in the following section.
3.3 SUMMARY OF OUR THEORETICAL ANALYSIS
Theorem 3.1 Theorem 3.3 and Theorem 3.5 tell us that the network with a high training convergence speed and generalization capacity should have high absolute mean values and low standard deviation values for the gradient, w.r.t the parameters across different training samples/batches.
3.4 NEW ZERO-SHIOT PROXY
Inspired by the above theoretical insights, next propose proxy (ZiCo) that jointly considers both absolute mean and standard deviation values. Following the standard practice we consider convolutional neural networks (CNNs) candidate networks.
Definition 2. Given neural network with D layers and loss function L, the Zero-shot inverse Coefficient of Variation (ZiCo) is defined as follows:
ZiCo Σ log( Σ E(V,,(X, y: I] 1=1 WEO, VVar(VV uo: O)))
i (1,....,
(15)
where denote the initial parameters given network: 0 denote the parameters the 4th layer of the network, and represents each element in 0;; X; and yt are the 7t input batch and corre- sponding labels from the training set; is number of training batches used to compute ZiCo. We incorporate log to stabilize the computation by regularizing the extremely large small values.
Of note, our metric is applicable to general CNNs; i.c., there's no restriction w.r.t. the neural ar- chitecture when calculating ZiCo. As discussed in Section 3.3] the networks with higher ZiCo tend
5

---

Published as a conference paper at ICLR 2023
Loss vs. Mean value
vs. Variance
0.450
Total Training Loss
Total Training Loss
15
0.425
0.400
0.375
0.350
0.9905 Square Sum Mean Value (Z44)
0.9900
1.5 Square Sum of Variance (f
0.5
1.0
(a) Loss vs. Mean (linear)
(b) Loss variance (linear)
Figure I: Training loss vs. square sum of mean gradients and the sum of gradients variances for linear networks on MNIST after one epoch. Clearly, larger mean gradient values lead to lower loss values; also, networks with smaller Σ, of have lower loss values.
Loss Standard Deviation
Loss vs. Standard Deviation
35
0.8
30
Training Loss
25
0.6
20
Test
15
0.4
10
0.2
5
0.000
0.005 0.010 0.015 0.020 0.025 Standard Deviation (a)
0. 0.000 0.005 0.0.10.011 00010.005..02000222... 0.0.0..0000.0000000
Standard Deviation (a)
(a) Training Loss std. dev (ReLU)
(b) Test Loss std. dev (RcLU)
Training loss and Test loss vs. standard deviation of gradients for two-layer MLPs with ReLU on MNIST after one training epoch. Networks with smaller tend to have lower training loss and test loss values. We provide more results in Appendix C.I
Figure 2:
to have better convergence rates and higher generalization capacity. Hence, the architectures with higher ZiCo are better architectures.
We remark that the loss values in Eq. 15 all computed with the initial parameters +; that is, we never update the value of the parameters when computing ZiCo for a given network (hence follows the basic principle of zero-shot NAS, i.e., never train, only the initial parameters). In practice, two batches are enough to make ZiCo achieve the SOTA performance among all previously proposed aceuracy proxies (see Sec.4.5) 4.5). Hence, we use only two input batches (N 2) compute ZiCo; this makes ZiCo very time efficient for given network.
EXPERIMENTAL RESULTS
4.1 EXPERIMENTAL SETUP
We conduct the following types of experiments: (i) Empirical validation of Theorem 3.1 The- orem 3.3 and Theorem 3.5) (ii) Evaluation of the proposed ZiCo on multiple NAS benchmarks; (iii) Illustration of ZiCo-based zero-shot NAS on ImageNet.
For the experiments (i, to validate Theorem 3.1 we optimize a linear model as in Eq. 2 on the MNIST dataset, the mean gradient values and the standard deviation the total training loss. Moreover, we also optimize the model defined by Eq. 7 on MNIST and report the training loss vs.
the standard deviation in order to validate Theorem 3.2 and Theorem 3.5
For experiments (if), we compare our proposed ZiCo against existing proxies on three mainstream NAS benchmarks: NATSBench is popular cell-based search space with two different search spaces: (1) NATSBench- consisting 15625 total architectures with different cell structures trained on CIFAR10. 10, CIFAR100, and ImageNet16-120 1mg16-1200 datasets, which is just renamed

---

Published as a conference paper at ICLR 2023
Table 1: The correlation coefficients between various zero-cost proxies and two naive proxies (#Params and FLOPs) vs. test accuracy on NATSBench- TSS (KT and SPR represent Kendall's 7 and Spearman's 's p. respectively). The best results are shown with bold fonts. Clearly, ZiCo the only proxy that works consistently better than #Params and is generally the best proxy. We provide more results in Table 3
and Table in Appendix E.
NATSBench- TSS
(NASBench201))
Datasel
CIFARTO
CIFARTOU
Img/6-1
120
Proxy
Correlation
KT
SPR
KT
SPR
KT
SPR
norm Abdelfattah et al.
norm
[2021]
0.46
0.63
0.47
0.63
0.43
0.58
SNIP Lee el al. 20199
0.46
0.63
0.46
0.63
0.43
0.58
GraSP Wang ct al. (20200
0.37
0.54
0.36
0.51
0.40
0.56
Fisher Liu ct al. 2021
0.40
0.55
0.41
0.55
0.37
0.50
Synflow
Lanaka et al, [2020)
0.54
0.73
0.57
0.76
0.56
0.75
Zen-score
Lan el al. (202))
0.29
0.38
0.28
0.36
0.29
0.40
FLOPS
0.54
0.73
0.51
0.71
0.49
0.67
#Params
0.57
0.75
0.55
0.73
0.52
0.69
ZiCo (Ours)
0.61
0.80
0.61
0.81
0.60
0.79
from NASBench-201 Dong & Yang 2020); (2) NATSBench-SSS contains includes 32768 architec- tures (which differ only in the width values of each layer) and also trained on the same three above datasets Dong et al. (202T). NASBench101 provides users with 423k neural architectures with their
test accuracy on CIFARTO dataset; the architectures are built by stacking the same cell multiple
times Ying et al. (019). TransNASBench- 101-Mirco contains 4096 networks with different cell
structures on various downstream applications (see Appendix E.2) Duan et al. 20221.
ImageNet. We first use Algorithm [ to find the networks with the highest ZiCo under various FLOPs budgets. We conduct the search for 100k steps; this takes 10 hours GPU days). Then, we train the obtained network with the exact same training setup as Lin et al. (021). Specifically, we train the neural network for 480 epochs with the batch size 512 and input resolution 224. We also use the distillation-based training loss functions by taking Efficient-B3. as the teacher. Finally, we set the initial learning rate as 0.1 with cosine annealing scheduling scheme.
For experiments (iii,, we use ZiCo to conduct the zero-shot NAS (see Algorithm
single NVIDIA 3090 GPU (i.e., 0.4
4.2 VALIDATION OF THEOREMS
To empirically validate Theorem 3.1 we first randomly sample 1000 training images in MNIST; we then normalize these images with their L2-norm to create the training set S. We compute the gradient w.r.t. the network parameters for each individual training sample. Next, as discussed in Theorem B.T. we use the accumulated gradient over these samples to update the network parameters with learning rate 7) = Then, we calculate the square sum of mean gradients and the total training loss. We repeat the above process 1000 times on the same S. As shown in Fig. Da), we plot the total training loss vs. square sum of mean gradients as defined in Eq. S Clearly, the networks with the higher square sum of mean gradients values tend to have lower training loss. In comparison, Fig. [bb) shows that networks with a lower square sum of variance value tend to have lower training loss values, which coincides with the conclusion drawn from Eq. 6 These results empirically validate our Theorem 3.1
Moreover, to optimize two-layer MLP with ReLU activation functions defined in Eq. use the entire training set of MNIST and apply the gradient descent (Fq. 9 to update the weights. We set the batch size as 256 and measure the standard deviation of gradients (a) w.r.t. parameters across different training batches. We set very small learning rate = 10 to satisfy the assumption in Theorem 3.2 and Theorem 3.5 We plot the training loss and test loss after one training epoch vs. standard deviation of gradients (σ) in Fig. [a.. Clearly, the results show that if a network has a lower gradient standard deviation, then tends to have lower training loss values, and thus, a faster convergence rate. These results empirically prove our claims in Theorem 3.3 Similarly, Fig. a shows that if network has a lower gradient standard deviation, then tends to have lower test Toss values, which empirically validates Theorem 3.5
4.3 ZiCO VS. OTHER PROXIES ON NAS BENCHMARKS
We first calculate the correlation coefficients between various proxies and the test accuracy CI- FARI0, CIFAR 100, and ImageNet16 120 datasets for NATSBench- TSS. As shown in Table. ZiCo achieves the highest correlation with the real rest accuracy. We provide more results in Appendix H
ZiCo
7

---

Published as a conference paper at ICLR 2023
Correlation Coefficients between Proxies and Test Accuracy
Spearman's p Kendall's
0.63
Correlation
0.5
0.46
0.44
0.43
0,29
0.23
0.0
-..12.p.17
40.7
-0,28
Grad_norm SNIP
GraSP
Fisher
Synflow Zen-score FLOPs
#Params
ZiCo
Figure 3:
Correlation coefficients various proxies vs. test accuracy on NASBench101 search
space. ZiCo has significantly higher correlation scores than other proxies, except for Zen-score.
Table 2: Comparison of Top-1 accuracy of our ZiCo-based NAS against SOTA NAS methods on
ImageNet under various FLOP budgets (averages over three runs). For the 'Method' column, 'MS'
means multi-shot NAS; 'OS' is short for one-shot NAS; Scaling represents network scaling methods; 'ZS' is short for zero-shot NAS. OFAF is trained from scratch and reported in Moons et al. 20021)
Budget (maximal LOPS
Approsch
FLOPs
Top-1 [%]
Method
Costs [GPU
Days
EfficieniNet-Be
2019
390M
Scaling
3800
MnasNet-Ar A. Tan 2019
403M
76.7
MS
OFA Cai al. 2020
406M
77.7
OS
50
BN-NAS hen ct al.
1222a
470M
75.7
MS
0.8
450M
NASNet-B Zoph et al, 20118
488M
1800
CARS-D Yang
12020
496M
73.3
MS
0.4
DONNA Moons el 22021
S0TM
78.0
OS
25
#Params ZiCo (Ours)
451M
63.5
ZS
0.02
448M
78.1
DARTS Liu et al 2019
574M
73.3
OS
PC-DARTS Xu of 12019
586M
75.8
BigNAS-LI
386M
79.5
OS
2304 (TPU days)
CARS-T Yang al 2020
591M
75.2
MS
0.4
InTranNAS Yang et 2021
594M
76.2
OS
2.1
MAGIC Xu et al, 2022
598M
76.8
600M
SemiNAS
2020
599M
76.5
MS
DONNA Moons el al 2022
399M
78.4
OS
25
Zen-scon: Lan al 2021
611M
79.1
78
0.5
OFA Car et 2020
662M
78.7
50
EfficientNer-H1
700M
79.1
Scaling
3800
ZiCo (Ours)
603M
79,410.3
ZS
0.4
sharpDARTS Hundi al. 2019
950M
76.0
1000M
Zen-score
934M
80.8
ZS
0.5
EfficientNer-B 52 Tan & Le 2019
1000M
80.1
Scaling
3800
ZiCo (Ours)
1005M
80,
78
0.4
For NASBench101, shown in Fig. ZiCo has significantly higher correlation score with the real test accuracy than all the other proxies, except Zen-score. For example, ZiCo has a 0.46 Kendall's r score, while #Params is only 0.31. In general, ZiCo has the highest correlation coefficients among all existing proxies for various search spaces and datasets of NATSBench and NASBench101 To our best knowledge, ZiCo is the first proxy that shows a consistently higher correlation coefficient compared to #Params.
The above results validate the effectiveness of our proposed ZiCo; thus, ZiCo can be directly used to search for optimal networks for various budgets. Next, we describe the search results in detail.
4.4 ZiCo ON IMAGENET
Search Space We use the commonly used MobileNetvv--bel based search space where the candidate networks are built by stacking multiple Inverted Bottleneck Blocks (IBNs) with SE modules [Sandler et al. (2018) 8); Pham et al. (2018): Lin et al. (202T). As for each IBN, the kernel size of the depth- wise convolutional layer is sampled from (3. 5, 7} and the expansion ratio randomly selected from 2, 4, 6}. We consider ReLU as the activation function. We use standard Kaiming Init to initialize all linear and convolution layers for every candidate networks He et al. 20015). More details of the search space given in Appendix D
modules(Sandler
We use Algorithm 0 (see Appendix D.2) to search networks under various FLOPs budgets (450M, 600M, and 1000M) within the above search space. As shown in Table 2 ZiCo outperforms most previous NAS approaches by a large margin. For example, when the FLOPs budget around 450M, ZiCo achieves 78.1 % Top-1 accuracy, which is competitive with one of the SOTA NAS methods
8

---

Published as a conference paper at ICLR 2023
Correlation Coefficients #Batch
Correlation Coefficlents vs. Batch Size
Correlation
0.8
Correlation
0.8
Spearman's
Kendall's
0.7
0.7
Kendall's т Spearman's
0.6
0.6
2
8
10
0
20
40
60
80
100
120
The Number of Training Batches
Batch Size
(a) Correlation vs. #Batch
(b) Correlation vs. Batch Size
Figure 4: Ablation study. The correlation coefficients between: (a) ZiCo under varying number of batches and real test accuracy; (b) ZiCo under varying batch size and real test accuracy.
(DONNA), but with fewer FLOPs and 648 faster search speed Moons et al. (202T). Moreover, if the FLOPs is 600M, ZiCo achieves 2.6% higher Top-1 Accuracy than the latest one-shot NAS method (MAGIC-AT) with a 3x reduction in terms of search time Xu et al. (2022).
To make further comparison with #Params, also use #Params as the proxy and Algorithm
to conduct the search under a 450M FLOPs budget. As shown in Table [2, the obtained network by #Params has a 14.6% lower accuracy than ours (63.5% vs. 78).%) Hence, even though the
correlations for ZiCo and #Params in Table | and the optimal networks in Table 4 are similar for small-scale datasets, ZiCo significantly outperforms naive baselines like #Params for large datasets like ImageMet. To conclude, ZiCo achieves SOTA results for Zero-Shot NAS and outperforms naive methods, existing zero-shot shot proxies, as well as several one-shot and multi-shot methods.
We remark that these results demonstrate two benefits of our proposed ZiCo: (i) Lightweight com- putation costs. As discussed in SeeB] during the search process, to evaluate given architecture, we only need to conduct the backward propagation twice (only takes 0.3s on an NVIDIA 3090 GPU). The computation efficiency and exemption of training enable ZiCo to significantly reduce the search time of NAS. (ii) High correlation with the real test accuracy. As demonstrated in Sec 4.3 ZiCo has a very high correlation score with real accuracy for architectures from various search spaces and datasets. Hence, ZiCo accurately predict the test accuracy of diverse neural architectures, thus helping find the optimal architectures with the best test performance.
4.5 ABLATION STUDY
Number of batches We randomly select 2000 networks from NATSBench- TSS on CIFAR100
dataset and compute ZiCo under varying number of training batches (N in Eq. [5) from (2)....10). We then calculate the correlation between ZiCo with the real test accuracy. Fig. 4aa shows that using two batches compute ZiCo generates the highest score. Hence, in our work, we always use two batches (N = 2) to compute ZiCo since it is both accurate and time-efficient.
Batch size We compute ZiCo with two batches under varying batch size 21, 8, 16, 32, 64, 128) for the same 2000 networks as above; we then calculate the correlation between ZiCo with the test accuracy. Fig. bb) shows that batch size 64 is enough to stabilize the coefficient. Hence, we set the batch size as 128 and use two batches to compute ZiCo. We provide more ablation studies in Appendix| F
CONCLUSION
In this work, we have proposed ZiCo, a new SOTA proxy for zero-shot NAS. As the main theoretical contribution, first reveal how the mean value and standard deviation of gradients impact the train- ing convergence of a given architecture. Based on this thcoretical analysis, we have shown that ZiCo works better than all zero-shot NAS proxies proposed so far multiple popular NAS-Benchmarks (NA.Bennch 101, MAXTSBnnch-SSS/TSS for multiple datasets (CIFAR 10/100, ImageNet16- 1220.. In particular, we have demonstrated that ZiCo is consistently better than (#Params) and existing zero- shot proxies. Moreover, ZiCo enables us to find architectures with competitive test performance to representative one-shot and multi-shot NAS methods, but with much lower search costs. For exam- ple,
NAS can find the architectures with 78. 18.1% %, 79.4%, and 80.4% test accuracies under 450M, 600M, and 1000M FLOPs budgets, respectively, on ImageNet within 0.4 GPU days.
ACKNOWLEDGMENTS
This work supported in part by the US National Science Foundation (NSF) grant CNS-2007284.
9

---

Published as a conference paper at ICLR 2023
REFERENCES
Mohamed S. Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Nicholas Donald Lane. Zero- cost proxies for lightweight NAS. In International Conference on Learning Representations (ICLR), 2021.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. International Conference on Machine Learning (ICMI.), 2019.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with infinitely wide neural net. In Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-graing analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning (ICML), 2019b.
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network archi- tectures using reinforcement learning. In International Conference Learning Representations (ICLR), 2017.
Friedrich L Bauer and Charles T Fike. Norms and exclusion theorems. Numerische Mathematik, 2 (1):137-141, 1960.
Kartikeya Bhardwaj, Guihong Li, and Radu Marculescu. How does topology influence gradi- ent propagation and model performance of deep networks with densenet-type skip connections? arXiv preprint arXiv:1910.00780 2019.
Kartikeya Bhardwaj. James Ward, Caleb Tung. Dibakar Gope, Lingchuan Meng. Igor Fedorov, Alex Chalfin, Paul Whatmough, and Danny Loh. Restructurable activation networks. CoRR, Abs/2208.08566 2022.
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Vee Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS). 2020.
Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. Efficient architecture search by network transformation. In Proceedings of the AAAI Conference on Artificial Intelligence, 2018.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference Learning Representations (ICLR), 2019.
Han Cai, Chuang Gan, Tianzhe Wang. Zhekai Zhang, and Song Han. Once-for-all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations (ICLR), 2020.
Boyu Chen, Peixia Li, Baopu Li, Chen Lin, Chuming Li, Ming Sun, Junjie Yan, and Wanli Ouyang. BN-NAS: neural architecture search with batch normalization. In Proceedings of the IEEE Inter- national Conference on Computer Vision (ICCV), 2021a.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four GPU hours: A theoretically inspired perspective. In International Conference on Learning Representations (ICLR), 2021b.
Xiangning Chen and Cho-Jui Hsich. Stabilizing differentiable architecture search via perturbation- based regularization. In International Conference on Machine Learning (ICML), 2020.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Confer- on Computer Vision (ICCV), 2019.
10

---

Published as a conference paper at ICLR 2023
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 257-266, 2019.
Lénaïc Chizat, Edouard Oyallon, and Francis R. Bach. On lazy training in differentiable program- ming. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Youngmin Cho and Lawrence K. Saul. Kernel methods for deep learning. In Advances in Neural Information Processing Systems (NeurIPS), 2009.
Xiangxiang Chu, Bo Zhang, and Ruijun Xu, Fairas:: Rethinking evaluation fairness weight shar- ing neural architecture search. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2021.
Tu Do and Ngoc Hoang Luong. Training-free multi-objective evolutionary neural architecture search via neural tangent kernel and number of linear regions. In International Conference on Neural Information Processing, pp. 335-347, Springer, 2021.
Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four gpu hours. In Pro- ceedings of the IEEE Conference on Computer Vision and Pattern Recognition ( (CVPR), 2019.
Xuanyi Dong and Yi Yang. Nas-bench-201 Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats-bench: Benchmarking nas algorithms for architecture topology and size. IEEE transactions on pattern analysis and machine intelligence, 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition scale. In International Conference on Learning Representations (ICLR), 2021.
Simon S. Du, Jason D. Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning (ICML), 2019a.
Simon S. Du, Xiyu Zhai, Barnabás Póezos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. In International Conference on Learning Representations (ICLR), 2019b.
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang. Tong Zhang, and Zhenguo Li. meunsnas-bench-ee 101: Improving transferability and generalizability of cross-task neural architec- ture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Stanley C Eisenstat and Ilse CF Ipsen. Three absolute perturbation bounds for matrix eigenvalues imply relative bounds. SIAM Journal on Matrix Analysis and Applications, 20(1):149-1588 1998.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Research, 2019.
Adrià Garriga-Alonso, Carl Edward Rasmussen, and Laurence Aitchison. Deep convolutional net- works as shallow gaussian processes. In International Conference on Learning Representations (ICLR), 2019.
Eugene Golikov, Eduard Pokonechnyy. and Vladimir Korviakov, Neural tangent kernel: A survey. CoRR, abs/2208. 13614, 2022.
Xinyu Gong, Shiyu Chang. Yifan Jiang, and Zhangyang Wang. Autogan: Neural architecture search for generative adversarial networks. Proceedings of the IEEE International Conference on Computer Vision (ICCV) 2019.
11

---

Published as a conference paper at ICLR 2023
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng, Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Proceedings of the European Conference on Computer Vision (ECCV), 2020.
Boris Hanin and Mihai Nica. Finite depth and width corrections to the neural tangent kernel. In International Conference on Learning Representations (ICLR), 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance imagenet classification. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In Proceedings of the IEFE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Andrew Howard, Ruoming Pang, Hartwig Adam, Quoc V. Le, Mark Sandler, Bo Chen, Weijun Wang, Liang-Chieh Chen, Mingxing Tan, Grace Chu, Vijay Vasudevan, and Yukun Zhu. Search- ing for mobilenetv3. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2019.
Gao Huang. Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely Connected Convolutional Networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Andrew Hundt, Varun Jain, and Gregory D. Hager. sharpdarts: Faster and more accurate differen- tiable architecture search. CoRR, abs/1903 abs/1903,,,990, 09900,,90, 2019.
Thorir Mar Ingolfsson, Mark Vero, Xiaying Wang, Lorenzo Lamberti, Luca Benini, and Mattco Spallanzani, Reducing neural architecture search spaces with training-free statistics and compu- tational graph clustering. In 19th ACM International Conference on Computing Frontiers. ACM, 2022.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2018
Mojan Javaheripi, Shital Shah, Subhabrata Mukherjee, Tomasz L. Religa, Caio T. Mendes, Gus- tavo H. de Rosa, Sébastien Bubeck, Farinaz Koushanfar, and Debadeepta Dey. Litetransform- ersearch: Training-free on-device search for efficient autoregressive language models. CoRR, abs/2203.02094, 2022.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabás Póczos, and Eric P. Xing- Neural architecture search with bayesian optimisation and optimal transport. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations (ICLR), 2017a.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference Learning Representations (ICLR), 2017b.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in Neural Information Processing Systems (NeurIPS), 2012.
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 Advances in Neural Information Processing Systems (NeurIPS), 2019a.
Namhoon Lee. Thalaiyasingam Ajanthan, and Philip Tor. Snip: Single-shot network pruning based on connection sensitivity. In International Conference on Learning Representations (ICLR), 2019b.
12

---

Published as a conference paper at ICLR 2023
Aitor Lewkowyez, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. CoRR, abs/2003.02218, 2020.
Guihong Li, Sumit K. Mandal, Ümit Y. Ogras, and Radu Marculescu. FLASH: fast neural architec- ture search with hardware optimization. ACM Trans. Embed, Comput. Syst. 20(5s):63:1-6333 2021a.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land-
scape of neural nets. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, 2020.
Yuhong Li, Cong Hao, Xiaofan Zhang, Xinheng Liu, Yao Chen, Jinjun Xiong, Wen-mei Hwu, and Deming Chen. Edd: Efficient differentiable dnn architecture and implementation co-search for embedded ai solutions. In 57th ACM/IEEE Design Automation Conference (DAC), 2020.
Yuhong Li, Cong Hao, Pan Li, Jinjun Xiong, and Deming Chen. Generie neural architecture search via regression. In Advances in Neural Information Processing Systems (NeurIPS), 2021b.
Yuhong Li, Jiajie Li, Cong Han, Pan Li, Jinjun Xiong, and Deming Chen. Extensible proxy for efficient nas. CoRR, abs/2210.00 10.0949,. 2022.
Tengyuan Liang, Tomaso A. Poggio, Alexander Rakhlin, and James Stokes. Fisher-rao metric, ge- ometry, and complexity of neural networks. In International Conference on Artificial Intelligence and Statistics, 2019.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-nas: A zero-shot nas for high-performance image recognition. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2021.
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 Proceed- ings of the European Conference on Computer Vision (ECCV), 2018a.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hier- archical representations for efficient architecture search. In International Conference on Learning Representations (ICLR), 2018b.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In
International Conference Learning Representations (ICLR), 2019.
Liyang Liu. Shilong Zhang, Zhanghui Kuang, Aojun Zhou, Jing-Hao Xue, Xinjiang Wang, Yimin Chen, Wenming Yang, Qingmin Liao, and Wayne Zhang. Group fisher pruning for practical network compression. International Conference on Machine Learning (ICML), 2021.
Shuying Liu and Weihong Deng. Very deep convolutional neural network based image classification using small training sample size. In 3rd IAPR Asian Conference Pattern Recognition (ACPR), pp. 730-734, 2015.
Vasco Lopes, Saeid Alirezazadeh, and Luís A Alexandre. Epe-nas: Efficient performance estimation without training for neural architecture search. In International Conference on Artificial Neural Nenworks, pp. 552-563. Springer, 2021.
Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean-field analysis of deep resnet and beyond: Towards provable optimization via overparameterization from depth. CoRR, 000.2003.00508, 2020.
Renqian Luo. Fei Tian, Tao Qin, Enhong Chen, and Tie- Van Liu. Neural architecture optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie- Yan Liu. semi-supervised neural architecture search. In Advances in Neural Information Processing Systems (NeurIPS). 2020.
13

---

Published as a conference paper at ICLR 2023
Song Mei, Theodor Misiakiewiez, and Andrea Montanari. Mean-field theory of two-layers neural networks: dimension- free bounds and kernel limit. In Conference on Learning Theory, 2019.
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. In International Conference on Machine Learning (ICML), 2021.
Bert Moons, Parham Noorzad, Andrii Skliar, Giovanni Mariani, Dushyant Mehta, Chris Lott, and
Tijmen Blankevoort. Distilling optimal neural networks: Rapid search in diverse spaces. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2021.
Radford M Neal. Priors for infinite networks. In Bayesian Learning for Neural Nenworks, pp. 29-53. Springer, 1996.
Xuefei Ning, Changcheng Tang, Wenshuo Li, Zixuan Zhou, Shuang Liang, Huazhong Yang, and Wang. Evaluating efficient performance estimators of neural architectures. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Hieu Pham, Melody Guan, Barrettophh Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning (ICML), 2018.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka I. Leon-Suematsu, Jie Tan, Quoe V. Le, and Alexey Kurakin. Large-scale Evolution of Image Classifiers. In International Conference on Machine Learning (ICML), 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the AAAI Conference Artificial Intelligence, 2019.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues of the hessian in deep learning: Singu- larity and beyond. CoRR, abs/1611, 1.07476, 2016.
Levent Sagun, Utku Evei, V. Ugur Güney, Yann N. Dauphin, and Léon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. In International Conference on Learning Representations (ICLR), 2018.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang-Chies Chich Chen. Mo- bilenetv2: Inverted Residuals and Linear Bottlenecks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
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 International Conference on Learning Representations (ICLR), 2022a.
Yao Shu, Zhongxiang Dai, Zhaoxuan Wu, and Bryan Kian Hsiang Low. Unifying and boosting gradient- based training-free neural architecture search. CORR, 0ttp//201109998. 2022b.
Dimitrios Stamoulis, Ruizhou Ding, Di Wang, Dimitrios Lymberopoulos, Bodhi Priyantha, Jie Liu, and Diana Marculescu. Single-path NAS: designing hardware-efficient convnets in less than hours. In Machine Learning and Knowledge Discovery in Databases European Conference, ECML PKDD 2019, 2019.
Zhenhong Sun, Ming Lin, Xiuyu Sun, Zhiyu Tan, and Rong Jin. Revisiting efficient object detection backbones from zero-shot neural architecture search. CORR, abs/2111. 2021.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning (ICML), 2019.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc V Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Hidenori Tanaka, Daniel Kunin, Daniel Yamins, and Surya Ganguli. Advances in Neural
Information Processing Systems (NeurIPS), 2020.
14

---

Published as a conference paper at ICLR 2023
Linh Tam Tran and Sung-Ho Bae. Training-fiee free hardware-awart neural architecture search with reinforcement learning. Journal of Broadcast Engineering, 26(7):855 861, 2021.
Linh-Tam Tran, Muhammad Salman Ali, and Sung-Ho Ho Bae. A feature fusion based indicator for training-free neural architecture search. IEEE Access, 9:133914-133923, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems (NeurIPS), 2017.
Alvin Wan, Xiaoliang Dai, Peizhao Zhang. Zijian He, Yuandong Tian, Saining Xie, Bichen Wu, Matthew Yu, Tao Xu, Kan Chen, Peter Vajda, and Joseph E. Gonzalez. Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions. In Proceedings of the IEEE Con- ference Computer Vision and Pattern Recognition (CVPR), 2020.
Chaoqi Wang, Guodong Zhang, and Roger B. Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference on Learning Representations (ICI.R) 2020.
Colin White, Mikhail Khodak, Renbo Tu, Shital Shah, Séhastien Bubeck, and Debadeepta Dey. A deeper look at zero-cost proxies for lightweight nas, ICLR Blog Track, 2022. URL https:
//iclr-blog-ttee
www.ggithhhg.... 1tt202200222222222222222222222 /220:/..2.....222222333/3/33//// zero cost proxies/
Christopher K. Williams. Computing with infinite networks. In Advances in Neural Information Processing Systems (NeurIPS), 1996.
Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang. Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangging Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Meng-Ting, Wu, Hung-I Lin, and Chun- Wei Tsai. training-free genetic neural architecture search. In ACM International Conference on Intelligent Computing and its Emerging Applications, 2021.
Lichuan Xiang, Lukasz Dudziak, Mohamed S. Abdelfattah, Thomas Chau, Nicholas D. Lane, and Hongkai Wen. Zero-cost proxies meet differentiable architecture search. CoRR, abs/2106.06799, 2021a.
Lichuan Xiang, Lukasz Dudziak, Mohamed S. Abdelfattah, Thomas Chau, Nicholas D. Lane, and Hongkai Wen. Zero-cost proxies meet differentiable architecture search. CoRR, obs/2900.00699, 2021b.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: In International Conference on Learning Representations (ICLR), 2019.
stochastic neural architecture search.
Jin Xu, Xu Tan, Kaitao Song, Renqian Luo, Yichong Leng, Tao Qin, Tie-Yan Liu, and Jian Li. Analyzing and mitigating interference in neural architecture search. In International Conference on Machine Learning (ICML), 2022.
Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. KNAS: green neural architecture search. In International Conference on Machine Learning (ICML), 2021.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-efficient architecture search. CoRR, abs/1907.05733 2019.
Yibo Yang. Shan You, Hongyang Li, Fei Wang, Chen Qian, and Zhouchen Lin. Towards improving the consistency, efficiency, and flexibility of differentiable neural architecture search. In Proceed- ings of the IEÉE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Zhaohui Yang, Yunhe Wang, Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. CARS: continuous evolution for efficient neural architecture search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), 2020.
15

---

Published as a conference paper at ICLR 2023
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning (ICML), 2019.
Jiahui Yu, Pengchong Jin, Hanxiao Liu, Gabriel Bender, Pieter-Jan Kindermans, Mingxing Tan, Thomas Huang. Xiaodan Song, Ruoming Pang, and Quoe Le. Bignas: Scaling up neural ar- chitecture search with big single-stage models. In Proceedings of the European Conference on Computer Vision (ECCV), 2020a.
Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase neural architecture search. In International Conference on Learning Repre- sentations (ICLR), 2020b.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In International Conference on Learning Representations (ICLR), 2020.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. In International Conference on Learning Representations (ICLR), 2019a.
Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one-hidden-laye layer relu net- works via gradient descent. In International Conference on Artificial Intelligence and Statistics, 2019b.
Xuanyang Zhang, Pengfei Hou, Xiangyu Zhang, and Jian Sun. Neural architecture search with ran- dom labels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
Zhihao Zhang and Zhihao Jia, Gradsign: Model performance inference with theoretical insights. In International Conference Learning Representations (ICIR), 2022.
Dongzhan Zhou, Xinchi Zhou, Wenwei Zhang, Chen Change Loy, Shuai Yi, Xuesen Zhang, and Wanli Ouyang. Econas: Finding proxies for economical neural architecture search. Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. In International Conference on Machine Learning (ICML). 2019.
Qinqin Zhou, Kekai Sheng, Xiawu Zheng, Ke Li, Xing Sun, Yonghong Tian, Jie Chen, and Ron- grong Ji. Training-free transformer architecture search. CoRR, 0bs/2203.122113 2022.
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. Interna- fional Conference on Learning Representations (ICLR), 2017.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning Transferable Archi- tectures for Scalable Image Recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
16

---

Published as a conference paper at ICLR 2023
A PROOF OF THEOREM 3.1
Theorem We denote the updated weight vector as à and Eiş [9s (xi)]²
G. Assume we use the accumulated gradient of all training samples and learning rate y to update the initial weight vector i.e., à = 1) >; ((r)). If the learning rale O < 1J < 2, then the total training loss is bounded
as follows:
Σ Lun. [(x;; à)) s
G 2
7 2 11) Σ m3
(16)
1 In particular, if the learning rate n M then L(a)) is bounded by:
Σ L(vi, fla;; a)) < 2
Σ oj
(17)
Proof. Given each training sample (æ4, v1) the gradient of L. w.r.t to when taking (az,, Us) as the input is as follows:
@L(yis (a);a)
g(xxz)
(18)
Oa
We note that:
(a - g(xx)) xs - yt = a x; a x as + yoor xz
= a x; (a" x; (xe (x)
(19)
a æi a d':;;
0 Vi (a (a--g(te (((w:))) Tw:
Then the total training loss among all training samples is given by:
M
1
Σ
à
x4
y2)2
(20)
2
By using Eq.
19
we can rewrite Eq. 20 as follows:
M
M
wi - y1)2 =
Σ
(T 8; - (a- - g(xx))) xx)))
2
2
1=1
(21)
M
((a a + g(x+)) xx)))²
2
1=1
Recall the assumption that a - Zn g(x;); we rewrite Eq. 21 as follows:
M
M Σ
àa T' x;
y1)²
(g(xx)
Σ 9( xx
(22)
2
1=1
17

---

Published as a conference paper at ICLR 2023
According to the Baucch--cchwarce inequality and | 1, the total training loss is bounded by:
a" 04
-v:) -
1
([(((a))) Σ Il gzx,)]l ||00||2
Σ [M((())))) - - Σ g((x))l?
2
M
Σ (x1) - m))p
2
j=1
M
Σ (x;)) 2n. + 1f
2
(23)
j=1
ΣLe (xxe) + Σ 11pM' - > (1 E gz((xa))
2
1/
Els (xx4)) + -E -2 2 -2EnMu,Muu)
2
G+ Σ (n² E(1²
2 kz)
=
2
G - 2/ n
n) Σ m3
2
Since Di=1 2 {( x; y; is always non-negative, the above upper bound of training loss satisfies:
M 1
M
G n22 - 71 Σ m
(a xs =1)²
(24)
Note that, 0 < 17 upper bound of training loss in Eq. 23 closer O. In other words, the higher the gradient absolute mean values across different training samples/batches, the lower the training loss values the model converges to; i.e., the network converges
then n7(2 (12-1) 11)
Therefore, the larger E, n² term would make the
faster rate.
In particular, if 7 37
1 the Eq. 23 can be rewritten as:
M
(TT: xi v.)²
(g)(204) 111)3
Σ Mo²
(25)
M
Σ o3 2
This completes our proof.
B PROOF OF THEOREM 3.2
Theorem 3.2
Given a neural network with ReLU activation fctivation,uunctoon optimized by minimizing Eq. S
we assume that each initial weight vector (w,(0), 1,....1) n. is i.i.d. generated from (1 I) and the gradient for each weight follows an i.i.d. (0, For some positive constants 7 and if the
Aoy/55 learning rate d) satisfies 1) 2M3224(1-0016 then with with probability at least (1- 8)(1 e), the
following holds true: for any r E [m]. (0) - -w,(t)l & = itto / c), and at training
step L. the Gram matrix H1) satisfies:
18

---

Published as a conference paper at ICLR 2023
Aminn (H(t)) 2 Amin (H()) 2/ nttor /$(1 ((1-))
(26)
2() is the inverse cumulative distribution function for a d-degree chi chi-squared distribution x (d).
Proof. We first compute the probability of (0) (.(())l < C. Based on the assumption
w;(0), i = I...., } follows i.i.d. NN 7) and the gradient for each weight follows i.i.d. (N a), considering the weight updating rule defined in Eq 9 each element in w, w,(0) wt) follows ii.d (N nlo). Therefore, (00-(0) w.ll (d)..
follows the chi-squared distribution with d degrees of freedom
1/"1"
(0] w1 |l S C) = P(11,,, (0) w, (t]]l2 S C²)
P( ||, (0) (t)l1
C2
12²1002
122602
(27)
PO |2r (t)l1
I 401 - e))
1222
= -
Given an input sample a; and weight vector (1) from W (l), we define the following event:
Air = (t) w, (0)]l CC (0) 2 0} * 1( wr (t)(t) 2 0}} If [() (t) - wr
(28)
( (0)1 - C' holds true, ox w() 2 (1) w+ o (0)
(29)
-sign( [ (w,(1) (t) w. (,))) Ww (1) - w,- (0)l + sign( w. (0))[(>>(0))
Eq. tells us that if ([)]l is larger than (1) w, (0)ll. then = uz (0) determines the sign value of af (t)(t;; in other words, a!. (t) always has the same sign values with x! w,, (0); i.e., If I<=: (0) 2 0} =I<=Tw,(t) wt(() 2 0}. That is, if ((),(() w,)l)| < C and If27 w,) 2 0} + I( (t) 2 0} hold true, then (0]]| & C. Therefore, the probability of event Ag::
P(A,.) S ((() S C))
(30)
By anti-concentration inequality of Gaussian distribution Du al. (201b)), we have:
V2C
P(A+) & P([lw, s cC)) < V
(31)
Therefore, if any weight vector Wi,..., Wm satisfies |() w,,(()) < C, we can bound the entry-wise deviation on the Gram matrix Ht) at training step t: for any (i,j) [m]] x [n]:
(
(t)l))
E 3jj
( (0) 2 0, (0) 2 0} - 1( (I]Tw, 2 0, 0, w.(()) (1) 2 03)1]
171
=F m
oh nu (0) 2 20T (0) 2 0} T( w,(()) 2 03T(25 (1) 2 0))1
1 m
<E
(I(A,, A P(A.)) P(Ag))
m
2/2C
VT
(32)
where the expectation is summing over the initial weight w()). Hence, considering all the elements in H. we have:
M.M
2M2 /2C
E
Σ
(1
-1,(
(33)
/
1=1
19

---

Published as a conference paper at ICLR 2023
Therefore, by Markov's inequality, given the probability 8, we get:
M.M
2M2
-
VTō
(34)
In Du et al. 2019b), the authors prove that, given small perturbation K:
if
(1) H.gll & K, then (m) 2 Amin (H K
(35)
In our case, K in Eq. 35 given by 22C V=0
Therefore,
Amin (H(1)) 2 Amin (H())) 22C
Amin (m(n)((())) 2v 2v2M2 Φ01 -)
(36)
VTδ
VT8
We replace the term 1j in 36 with rj's upper bound given assumption of Theorem 3.2 i.e.,
AO 2212/20(1-)) we can get that Amin(H is always larger than O; that is:
Amin (H())) 2 Aman (H()) 2v2M2 1yto / 1
(37)
V v
This completes our proof.
C PROOF OF THEOREM 3.5
Theorem 3.5 Given neural network with ReLU iedivaationfuncttonn optimized by minimizing Eq.
we assume that each initial weight vector {w, = .,., i.i.d. generated from No,0 and the gradient for each weight follows an i.i.d. distribution (0, For some positive constants
8 and e, the learning rate yj satisfies 17
2M2V/6(1-ee00' then with with probability at least
(1 - (1-8)(1-) (1), the following holds true: for any r E [m]. |/,, (t)( & C = =nto / ()--).
and training step the Gram matrix H (t) satisfies:
Amax (H)) (maz(((()) 2
/ / cc
(38)
v TT
(-) is the inverse cumulative distribution function for a d-degree chi-squared distribution ²d).
The proof is similar to the proof of Theorem 3.2 (see Appendix below.
B We provide the entire proof
Proof. We first compute the probability | (0)
(t)l < C. Based on the assumption that {w, (0), 1..,, n follow i.i.d. A/(0, I) and the gradient of each weight follows i.i.d. (N0 o), considering the weight updating rule defined in Eq. with learning rate 7) each element in wo (0)
(t)(t) follows an i.i.d. A A/ ryto). Therefore, [|w,(0) w follows a chi-distribution with d degrees of freedom (d):
P(Ilw, (0) wy S C') p(| (0) wt (t)ll < C²)
P( |w) Wr wr (t)ll2
C
121202
121202
(39)
P( ||r (0) Wp wr (t)l12
<
Φ c))
022222
-
Given an input sample and weight vector (t from W (t), we define the following event:
Air (1) w,,(0]l < C) (T wr (0) 0) + 1(2 un (1) 0)}
(40)
20

---

Published as a conference paper at ICLR 2023
If (t) (r)l C' holds true, then:
at (t) 2. (w, (t) (0)) w
(41)
sign(æ ( (t) w,, (0)))) Wr (1) w, + (0))
Eq. 41 implies that if [[,, (0)ll is larger than (t),((t) - (0)l.. then = (0) determines the sign value of xf (t). In other words, 2 (t) always has the same sign values as x (,) that is, [e (0) 2 0} = 1[x; (t) 2 0}. Hence, if (()((t) w, (e)(l)] S C and 1[= wr(() 2 0} + Ma (t) 2 0} hold true, then [|,]( & C. Therefore, the probability of event Air:
P(A,)) & P(lllw, (0)1 - C))
(42)
By the onti-concentration inequality of a Gaussian distribution Du et al. (019b),, we have:
V2C
P(A+) < ((]])w,())] c)) <
(43)
V
Therefore, if any weight vector wi,..., Wm satisfies | entry-wise deviation on the Gram matrix Ht) at the training step for any (i,j) E [n] x [n]:
wt)l < C, we can bound the
E1 Bi (0) (t)(
=B
2 2jj
[ (+) 2 0, (0) 2 0} T( w. (1) 2 0, 0, ux (4) 2 0})1
=E
x
(T w. (0) 2 03T(2 (0 2 0} T(x (t) 2 03Т(2 wt 2 0})
m
(44)
We note that all the samples in the training set (Eq. D are normalized with their L2-norm. Hence, have both ||œ||| = 1 and |xyا|| Therefore, using the Cauchy-Schwarz inequality, the above equation is bounded as follows:
1 m
2V2C VT
E (0) - (01 < >a CLA UA P(Ab) + P(A,r)
(45)
m
where the expectation is over the initial weight w. (0),r = {L...,, elements in H. we have:
Hence, considering all the
M.M Σ
2M2
E
H2
H1)( -H
(46)
Vi
Therefore, by the Markov's inequality, given the probability 1 - 8, we get:
M.M
2M2
H2y( -H,(tH))++=
(47)
Vi8
Based on the matrix perturbation theory Bauer & Fike (1960); Eisenstat & Ipsen (1998). given small perturbation K:
if Σ 1
(0) (t)( s K, then Amaz (H(t)) < Amaz (H(0) + K
(48)
In our case, K in Eq. 48 is given by
2M 23C V
that is:
Aman (H(t)) Xmaz (H())) 2 2/2M2 / 101
(49)
This completes our proof.
21

---

Published as a conference paper at ICLR 2023
Standard Deviation
Standard Devistion
vs.
35
35
40-
30
35
25
30-
20
25
15
10-
5-
5-
1.0000.005..0100
0110000.111.000. 015 0155.0200 ww0.0.0..cooo Standard Deviation (of
0250.030.000
0.0000 Standard Deviation
0250.0300.00
Standard Devistion (o)
(a) Batch size=64
(b) Batch size= 128
(c) Batch size=256
Figure 5: Test loss vs. standard deviation of gradients (a in Eq. 13 for randomly sampled 500 two- layer MLPs with ReLU on MNIST after one training epoch. We train these networks by minimizing the MSE loss between the output of networks and the real labels. As shown, the Networks with smaller tend to have lower test loss values and thus have a better generalization capacity.
C.I SUPPLEMENTARY RESULTS: VALIDATION OF THEOREM 3.5
To empirically validate Theorem 3.5 we first create the training set S by normalizing the training samples in MNIST with their L2- norm. Next, optimize two-layer MLP with ReLU activation functions as defined in Eq. 7 We use the entire training set of MNIST and apply the gradient descent (Eq. 9 to update the weights. We vary the batch size {64, 128, 256) and measure the standard deviation of gradients (a) w.r.t. parameters across different training batches. A very small learning rate of 1) = 10 is set to satisfy the assumption in Theorem 3.5 Fig. S demonstrates the training loss after one epoch vs. standard deviation of gradients (o)). Clearly, the results show that if network has a lower gradient standard deviation, then it tends to have lower test loss values, and thus, a better generalization capacity. These results empirically prove our claims in Theorem 3.5
D EXPERIMENTAL SETUP OF ZICO ON IMAGENET
D.1 SEARCH SPACE
We use the commonly used MobileNetv2-based search space where the candidate networks are built by stacking multiple Inverted Bottleneck Blocks (IBNs) with SE modules [Sandler et al. (2018); Pham et al. (2018); Lin et al. (2021); all the SE modules share the same ratio as 0.25. For each IBN, we vary the kernel size the depth-wise convolutional layer from (3, 5, 7} and sample the expansion ratio from {1, 2, 4. 6}. We consider ReLU as the activation function. For each point- wise convolutional layer, the range of the number of channels from to 1024 with a step size of 8. We use standard Kaiming Init to initialize all linear and convolution layers for every candidate networks He et al. (2015).
D.2 SEARCH ALGORITHM
We use an Evolutionary Algorithm (EA) to conduct the zero-shot NAS because it is concise and easy to implemen As shown in Algorithm we search for the neural architectures with the highest ZiCo within the search space, given specific budget B (e.g.. FLOPs). We repeat the search T times; each search step, we randomly select a structure from the candidate set IF and mutate its architectures (e.g., kernel size, block type, number of blocks, and layer width) generate new network F, S. If the generated network F; meets the inference budget B, we calculate its ZiCo on Z and add F; the candidate set F. We remove the network with the smallest ZiCo from I,, if the number of architectures in I exceeds the threshold E. After T' steps, we select the network with the largest ZiCo as the final (optimal) architecture Fp.
One also other methods perform the search; see Appendix F22
22

---

Published as a conference paper at ICLR 2023
Algorithm ZiCo-based zero-shot NAS framework
INPUT:
Number of search steps T Inference budget B, Search space $ Set of input batch ž {Xx,, i 1, Population size Initial network Fo OUTPUT: Optimal network Fp.
SEARCH:
Initialize IF = [Fo
for i 1 7 do
Randomly sample network F; from
F. = randomly mutated architecture based on Ft from S
if F. meets the inference budget B then
Compute ZiCo for F; on & by Eq. 15
Add F;
[
E
Remove network with the smallest ZiCo from IF
end if end if end for Fp= the network of the highest ZiCo in F.
Specifically, we repeat the search 10" times (i.e., T = 10") with the population size E = 512. For each of the candidate architectures, we compute ZiCo with two batches randomly sampled from the training set of ImageNet with batch size 128. In total, it takes 10 hours on single NVIDIA 3090 GPU for 10 search steps.
D.3 TRAINING DETAILS
We the data augmentations configurations in Pham al. (0188) mix-up, label- smoothing, random erasing, random crop/resire/ffii/ighnnng and Auto We use the SGD optimizer with momentum 0.9 and weight decay 4c-5. We take EfficientNet-B3 as teacher network and use the knowledge distillation method to train the network. We set the initial learning rate as 0.1 and used the cosine annealing scheme adjust the learning rate during training. We train the obtained network 480 epochs, which takes 83 hours on a 40-core Intel Xeon CPU and 8 NVIDIA 3090 GPU- -oweeed server.
E SUPPLEMENTARY RESULTS ON NAS BENCHMARKS
E. COMPARISON WITH MORE PROXIES
In this section, we further provide the comparison between our proposed ZiCo and more proxies proposed recently: KNAS (Xu et al. (202T), D,, NASWOT (Lopes et al. (202I)). Ih.. GradSign (Zhang & Jia )2022)) and NTK (TE-NAS Chen et al. (2021b), NASI Shu et al. (2022a)). To compute the correlations, we use the official code released by the authors of the above papers to obtain the values of these proxie As shown in Table 3 our proposed ZiCo performs better than all these proxies. For example, NASWOT and GradSign achieve similar correlation score as ZiCo on HATSBench-TSS. however, ZiCo has significantly higher correlation score than these two proxies NATSBench- SSS.
Beside the correlation coefficients, also report the optimal architectures found with various prox- ies. As shown in Table the architectures found via ZiCo have the highest test accuracy on all these three datasets.
NASI uses NTK to build their own search algorithms. Here, directly compute the correlation hetween NTK and the real test accuracy.
23

---

Published as a conference paper at ICLR 2023
The correlation coefficients between various zero-cost proxies and two naive proxies (#Params and FLOPs) vs. test accuracy on NATSBench-SSS and NATSBench-TSS (KT and SPR represent Kendall's and Spearman's p. respectively). The results in italics represent the values of #Params' correlation coefficients. The results better than #Params are shown with bold fonts. Clearly, our proposed ZiCo is the only proxy that works consistently better than #Params and is gen- erally the best among all these proxies. Both TE-NAS; (Chen et al. (2021b) and NASI; (Chen et al. 202Ib)) use NTK (Jacot et al. (2018) as the accuracy proxy to build their own search algorithms.
Table 3:
NATSBench- ISS (NASBench201)
Datasel
CIFARIO
CIFARIOU
Imgl6-15
120
Proxy
Correlation
KT
SPR
KT
SPR
KT
SPR
Grad_norm Abdelfattah al. [2021)
0.46
0.63
0.47
0.63
0.43
0.58
SNIP Lee ct al. 2019b
0.46
0.63
0.46
0.63
0.43
0.58
GraSP al. (2020)
0.37
0.54
0.36
0.51
0.40
0.56
Fisher Liu et al. 2021
0.40
0.55
0.41
0.55
0.37
0.50
Synllow Lanaka ct al. (2020)
0.54
0.73
0.57
0.76
0.56
0.75
KNAS Xu et al. (022
0.14
0.20
0.24
0.35
0.30
0.42
NASWOT Mellor et al. [202]]
0.58
0.77
0.62
0.80
0.60
0.78
NTK (TE-NAS Chen et al. [2021b] NASI Shu et al. (2022a
0.33
0.44
0.33
0.43
0.46
0.63
GradSign Zhang & Jia (202
0.58
0.77
0.59
0.79
0.59
0.78
Zen-score Lin et al. 2021
0.29
0.38
0.28
0.36
0.29
0.40
FLOPs
0.54
0.73
0.51
0.71
0.49
0.67
#Params
0.57
0.75
0.55
0.73
0.52
0.69
ZiCo
0.61
0.80
0.61
0.81
0.60
0.79
NATSBennch-SS
Dataset
CIFARIO
CIFARION 100
Img 6-
-20
Proxy
Correlation
SPR
KT
SPR
SPR
Grad norm Abdelfattah et al. (021
0.35
0.51
0.34
0.49
0.49
0.67
SNIP et al. 2019b
0.42
0.59
0.46
0.62
0.57
0.76
Wang et al, 2020
-0.09
-0.13
0.01
0.01
0.29
0.42
Fisher ct al. (0011
0.30
0.44
0.41
0.55
0.33
0.47
Synflow Tanaka et al. 22020
0.61
0.81
0.60
0.80
0.39
0.57
KNAS Xu et al. 1202T
0.25
0.37
0.12
0.18
0.32
0.46
NASWOT Mellor
(2021]
0.45
0.63
0.43
0.59
0.42
0.59
NTK (TE-NAS Chen
(2021b] J. NASI (Sh al. 2022a
0.17
0.26
0.04
0.06
0.20
0.30
GradSign Zhang Jia (2022)
0.21
0.30
0.16
0.27
0.04
0.05
Zen-score Lin ct al. 2021
0.50
0.69
0.52
0.71
0.69
0.87
FLOPs
0.19
0.28
0.21
0.30
0.38
0.53
#Params
0.53
0.72
0.54
0.73
0.65
0.84
ZiCo
0.54
0.73
0.55
0.75
0.70
0.88
Table 4: The test accuracy of optimal architectures obtained by various zero-shot proxies (averaged over 5 runs) on NATSBench-TSS TSS search space. The best results are shown with bold fonts.
CIFARI00
Groud Truth
Grad
SNIF
GraSP
Fisher
Jaceb cav
Syallow 71.1
Zen-score
#Params
FLOPs
ZiCo
60.0
60.0
60.0
60.0
68.9
68
71.1
71.1
Img16-120
Groud Truth 47.3
Grad morm 29.3
SNIP
GaSP
Fisher 29.3
Jacob.cov 25.1
Syatlow 41.2
Zen-score 40.8
#Params 41.4
FLOPs
ZiCo
29.3
5.5
41.4
41,8+0.3
CIFARI0
Grond Truth
Grad moor
SNIP
GraPP 89.5
Fisher
Incob.oov
Synflow 90.4
Zen-score 90.6
#Params
PLOPs
ZiCo
89.5
89.5
93.7
94010..4
E.2 COMPARISON ON TRANSVAS-BENCH-IO1- BENCH-101-MICHH
In this section, we compare proposed ZiCo against existing proxies more diverse tasks. We compare our proposed ZiCo against existing proxies on one mainstream NAS benchmark TrS-sNAS- Bench-10l 10/ Duan et al. (022I) We pick the largest search space TransNAS-Bencch 101 -Micro which contains 4096 total architectures with different cell structures. We compare ZiCo with various prox- ies under the following four tasks:
Scene Classification. Scene classification is a 47-class classification task that predicts the room type in the image.
24

---

Published as a conference paper at ICLR 2023
Table 5: The correlation coefficients under different proxies vs, test performance on TransNAS- Bench-1011 101-Mi Clearly, our proposed ZiCo is consistently very close to the best score (only 0.01 or 0.02 lower score) except for Autoencoding (still, ZiCo is the second best on Autoencoding). Though Fisher works better than ZiCo Autoencoding, ZiCo has significantly higher score on the rest of tasks. We note that existing proxies do not achieve a high correlation on all tasks consistently.
Autoencoding
Scene Classification
Proxy
Kendall's s r
Spearman
Kendall's r
Spearman's 's
Grad norm Abdelfattah et al. (2021
0.24
0.32
0.47
0.65
SNIP
Lee et al. (2019b
0.20
0.27
0.52
0.71
Grasp Wang et al. (2020)
0.09
0. 14
0.19
0.28
Fisher Liu et al. (021)
0.42
0.59
0.49
0.67
Synflow Tanaka et al.
2020
0.00
0.00
0.53
0.72
NASWOT Lopes et
2021
0.01
0.02
0.43
0.60
Zen-score Lin al. 2021
0.09
0.14
0.52
0.72
GradSign Zhang & Jıa
(2022)
0.01
0.02
0.32
0.46
Params
0.01
0.01
0.46
0.64
FLOPs
0.02
0.02
0.47
0.65
ZiCo (Ours)
0.24
0.35
0.51
0.71
Jigsaw
Surface Normal
Proxy
Kendall's s 7
Spearman's 's
Kendall's T Spearman 's
Grad_norm
Abdelfattah et al. (2021)
0.23
0.35
0.24
0.36
SNIP
Lee et al. (2019b)
0.27
0.41
0.32
0.49
Grasp Wang et al. (2020)
0.07
0.11
0.01
0.01
Fisher Liu el al. 2021
0.19
0.30
0.10
0.14
Synflow Wang el al. 2220
0.32
0.47
0.00
0.00
NASWOT
Lopes et 2021
0.29
0.42
0.41
0.57
Zen-score Lin al. 2021
0.35
0.50
0.52
0.71
GradSign
Zhang & J1a (2022
0.38
0.53
0.29
0.40
Params
0.29
0.44
0.45
0.63
FLOPs
0.30
0.45
0.46
0.64
ZiCo (Ours)
0.36
0.52
0.50
0.68
Jigsaw. In the Jigsaw task, the input image is divided into nine patches and shuffled based on one of 1,000 predefined permutations. The target here is to classify which permutation is used.
Autoencoding. Autoencoding is a pixel-level prediction task that encodes an input im- age into a low-dimension embedding vector and then reconstructs the raw image from the vector.
Surface Normal. Similar to autoencoding, surface normal a pixel-level prediction task that predicts surface normal statistics.
ZiCo consistently works well on Scene Classification, Jigsaw, and Surface Normal: ZiCo has only 0.01 0.02 lower correlation scores than the highest scores. Though Fisher works better than ZiCo on Autoencoding, ZiCo has significantly higher correlation scores than Fisher the remaining three tasks. One possibility why Fisher works best Autoencoding is that Autoencoding is an image-to toogge-to-imaee task; Fisher is the only proxy that is built on the gradient w.r.t. feature maps and thus can better extract the information between the input and output images. Although Fisher works better than ZiCo on Autoencoding (we are still second best), ZiCo has significantly higher score on the remaining tasks. As shown in the main paper, we again note that existing proxies do not achieve high correlation on all tasks consistently.
As shown in Table 5
Table demmonttesssss the test accuracy of the best architectures found using various proxies on each of the above tasks in MaansNAS--Behhhh 1-n------nn-----iirrro Once again, see that ZiCo significantly out- performs existing proxies on all tasks except Autoencoding, where we trail Fisher by only 0.01 SSIM. Nonetheless, ZiCo is second best the Autoencoding task. Note that, similar to the correla- tion results in Table other proxies do not consistently achieve high accuracy. For instance, while methods like Synflow Zenscore achieve results close
Scene Classification and Surface
25

---

Published as a conference paper at ICLR 2023
Table 6: The test performance of optimal architectures obtained by various zero-shot proxies (av- eraged over 5 runs) on TransNAS-Bent -AEAAAS--eec---e 101-Micro search space. The best results are shown with bold fonts.
Autoencoding
Scene Classification
Jigsaw Accuracy
Surface Normal
Metric
SSIM
Accuracy
SSIM
Ground Truth
0.58
54.9
95.4
0.59
Grad norm
0.36- 0.03
48.7440.7
80.3+-0.3
0.53--00.0
SNIP
0.3310.04
4..
80.310.1
0.53-10.01
Grasp
0.33
5..2++1.6
91.1+0033
0.38-1:0006
Fisher
0.49
48.7:10.6
83.5+:1.2
0.31-10.03
Synflow
0.46:10.07
5.2
90.91104
0.57-10.06
NASWOT
0.43+0.02
53.2:10.6
92.310.3
0.53-10.02
7en-score
0.46+00.0
5.2
87.5+-..4
0.55+F0.00
GradSign
0.35+:0.33
53.61:0.4
93.110.4
0.57-10.02
Params
0,46
53.70
85,90
0.55
FLOPs
0.46
53.70
85.90
0.55
ZiCo (Ours)
0.48
53.7:10.4
93.2.10.4
0.50-10.01
Table The correlation coefficients under three different proxies vs. test accuracy on NATSBench- SSS (KT and SPR represent Kendall's 7 and Spearman's 's respectively). Clearly, our proposed
ZiCo works consistently better than using mean only and STD only on all these datasets.
Dataset
CIFARTO
CIFARTON TOO
Img
7mg16-15
120
Method
KT
SPR
KT
SPR
KT
SPR
Mean Only
0.25
0.37
0.39
0.55
0.61
0.81
STD only
0.39
0.55
0.42
0.6
0.45
0.62
ZiCo (Mean + STD)
0.54
0.73
0.55
0.75
0.70
0.88
Normal, they produce poor results on other tasks like Jigsaw. Therefore, ZiCo consistently performs well highly different tasks.
E.3 ILLUSTRATION OF VARIOUS PROXIES VS. REAL TEST ACCURACY
We provide some illustration figures of real accuracy vs. various proxies on NATSBench-SSS search space for CIFARI0 (Fig, (6) and ImageNet16- 120 datasets(Fig, 77). We also show the same illustrative results (real test accuracy vs. various proxies) on NASBenchTOr search space in Fig.
F ABLATION STUDY
F.1 IMPACT OF MEAN AND STD
We randomly select 2000 networks from NATSBench-SSS on CIFARIO, CIFARI00, and Img16- 120 datasets and compute the following proxies: (i) Mean value of gradients only; (ii) Standard deviation (STD) value of gradients only; (iii) Combination of mean and std value, i.e., our proposed ZiCo. We then calculate the correlation coefficients between these proxies and the real test accuracy. As shown in Table. 7 our proposed ZiCo performs better on these three datasets than either using mean only or STD only. Therefore, our proposed ZiCo is better-designed proxy than using mean or STD individually.
F.2 SEARCH ALGORITIMS: ZERO-COST PT
In this section, we demonstrate that our proposed ZiCo can be combined with other search algo- rithms. We take the Zero-Cost-PT (Zero-PT) as an example Xiang et al. (202b)) because it is specifically designed for zero-shot proxies and is very time-efficient. Essentially. Zero-PT first integrates all candidate networks into supernet and assigns learnable weights to each candidate operation (same one-shot NAS). Then Zero-PT uses the zero-cost proxy instead of the training
26

---

Published as a conference paper at ICLR 2023
Table 8: The test accuracy of optimal architectures obtained by various zero-shot proxies (average on 5 runs) on NATSBench-TSSS search space. The best results are shown with bold fonts.
Proxy
CIFARIO
CIFARTOO
Img16-120
CPP hours)
Zeto-PT+SNIP Lee DeroPP-NNASWorLops al. [2021]
2019h]
93.52+0.18
70.75=0.19
44.45=00.14
0.10
93.42:10.07
70.7710.51
45.11:10.26
0.11
Zero-PT+SSynllow Lanaka (2020)
87.6810.16
58.92.10.77
32.20110.00
0.13
7ero-PT-KNAS Xu al. 2021
93.95+0.03
72.44+0.26
46.01+0.12
0.10
Zero-PI+Grad norm Abdellattah el al.
2021
93.5210.18
70.7540.30
44.48.10.11
0.07
score Lin et al. 2022
93.84+00.05
71.63+00.06
46.67
0.02
Zero GrraPSi+GradSign Zhang & Jia 2022
93.76+0.12
71.11
42.95
0,06
Zero-PT+ZiCo (Ours)
94.15=0.22
72.77=0.66
46.39+-023
0.12
Table 9: Comparison of Top-1 accuracy of our ZiCo-based NAS against NAS methods with stan- dalone training on ImageNet under various FLOP budgets. For the 'Method' column, 'MS' repre- sents multi-shot NAS; *OS' is short for one-shot NAS; Scaling represents network scaling methods; 'ZS' short for zero-shot NAS. 'no KD' means we train the network without Knowledge Distilla- tion (KD); '150E' means we train the network with 150 epochs, similar for 350E. The results are averaged over three suns. We note that some NAS methods use knowledge distillation to improve the test accuracy; hence, remove those methods from this table. The results averaged over three runs.
Budget (maximal #FLOPs)
Approach
FLOPS
Top-1
Method
Costs|GPU Days
EfficieniNet-B Le 12019
[350E]
390M
77.1
Scaling
3800
EllicientNet B0 Jan al.
2019
[5OE]
390M
76.0
Scaling
3800
MnasNet- A3 cral. 2019
403M
76.7
MS
BN- Chen 2021a
470M
75.7
MS
0.8
450M
RLNAS Zhang al
2021
473M
75.6
OS
NASNci- Zupli
488M
72.8
MS
1800
CARS-D lung 2020
496M
73.5
MS
0.4
Zen--oore Lin et 2021 [10 KD: ISOE]
4TOM
75.6
ZS
0.5
45TM
63.5
ZS
0.02
ZiCo (Ours) [no KD; 150E)
448M
76.5:1022
ZS
0.4
DARTS Liu et al, 2019
574M
73.3
OS
4
Lao Luo &t al 2218
584M
75.5
MS
38.3
PC-DARTS
586M
75.8
OS
3.8
PNAS Liu et al 80
588M
74.2
MS
224
CARS-I yump cl 2022
591M
75.2
MS
0.4
En EnTranNAS Yung
594M
76.2
OS
2.1
ProkylesSNAS Cu al
2019
595M
76.0
OS
8.3
RLNAS Zhaing cl
75,9
OS
600M
MAGIC Xu
2022
598M
76.8
OS
2
SemıNAS Lio al
2020
599M
76.5
MS
EfficiemiNetBB1
350E]]
700M
79.1
Scaling
3800
EfficientNet-BB
Tai u.
[
2019
[15EE]
700M
77.4
Scaling
3800
TE-NAS Chen et
20211
75.5
ZS
0.17
Zen-score Lin et 2021
10 KD.
150E)
611M
76.1
ZS
0.5
ZiCo (Ours) [no KD; 150E]
603M
77.1:0.3
ZS
0.4
accuracy to update the weights for each candidate operation. The final architecture is generated by selecting the operations with the highest weight values.
We combine different accuracy proxies with Zero-PT under the NASBench-201 and report the op- timal architectures found with various p] As shown in Table g the architectures found via ZiCo have the highest test accuracy except for Img16-120 datasets (ZiCo is the second best on Img 12-))..).
F.3 TRAINING RECIPE: WITHOUT DISTILLATION
In this section, we train the obtained network under various FLOPSs budgets with the exact same training setup as Xu et al. (2022); Cai et al. (2019). Specifically, we train the neural network for 150 epochs with batch size 512 and input resolution 224. We train the network without knowledge
We implement the code ourselves since the authors have not released the code yet. The difference between Table 4 and Table 8 comes from the search algorithm: Table 4 uses traversal search among all candidate networks; Table & uses perturbation-base zero-cost PT Xiang (022T)).
27

---

Published as a conference paper at ICLR 2023
Table 10: Comparison of Top-1 accuracy of our ZiCo-based NAS against NAS methods with stan- dalone training on CIFARIO DART'S search space. For the 'Method' column, 'MS' represents multi-shot NAS: 'OS' short for one-shot NAS; 'ZS' is short for zero-shot NAS. '600E' means we train the network with 600 epochs, similar to 800E. The results are averaged over three suns. The results are averaged over three runs.
Approach
Test Error (%)
Method
Cost(GPU days)
AmoebaNet-A Real et al. (2019
3.3410.06
MS
3150
PNAS Liu al. (0118a)
3.41
MS
225
ENAS lan & Le (2019]
2.89
MS
0.5
NASNet- Zoph et al. (2018)
2.65
MS
2000
DARTS-V Liu al.
2019
3,00 14
OS
0.4
DARTS- v2 Liu et al. 2019
2.76:t0.009
OS
SNAS Xie et al. (2019)
2.85
OS
1.5
GDAS Dong & Yang 2019
2.82
OS
0.17
BayesNAS Zhou et al. 22199]
2.81
OS
0.2
ProxylessNAS Cai al. (2019)
2.08
OS
P-DARTS Chen et al. 2019
2.5
OS
0.3
PC-DARTS Xu et al. (2019
2.57=00.07
OS
0.1
SDARTS-ADD Chen & Hsteh
(2020)
0.02
OS
1.3
Zen-score Lin al.
202
2.55+10.04
ZS
0.01
TE-NAS Chen et al. (20216)
2.63+0.064
ZS
0.05
ZiCo(ours)
2.45+0.11
7S
0.03
distillation and do not use advanced data augmentation methods (e.g., mixup, RandAugment, etc). Finally, we set the initial learning rate as 0.4 with a cosine annealing scheduling scheme. Moreover, train EfficientNets and the previous SOTA zero-shot NAS approach (Zen-score) under the same setup.
As shown in Table ZiCo outperforms all of the previous zero-shot NAS approaches. For exam- ple, when the FLOPS budget is around 600M, ZiCo achieves 77.1% Top-1 accuracy, which is 1.0% and 1.6% higher than previous SOTA zero-shot NAS methods, i.e., Zen-score, and TE-NAS, spectively. Moreover, ZiCo finds model with similar accuracy as EfficientNet-B1, but with 100M fewer FLOPs and much less search cost. Overall, compared to the regular one-shot or multi-shot NAS methods, ZiCo achieves comparable or higher test accuracy with 5-9500 less search time.
F.4 SEARCH SPACE: DARTS
In this section, we use ZiCo to conduct the zero-shot NAS on the DARTS search space. first use Algorithm [ to find the networks with the highest ZiCo without FLOPs budgets the CIFAR 10 dataset. We conduct the search for 100k steps; this takes 0.7 hours on a single NVIDIA 3090 GPU (i.e., 0.03 GPU days). Then, train the obtained network with the exact
training setup the original DARTS paper Liu et al. 2019 [ specifically, we train the neural network for 600 epochs with batch size of 128. We only use the standard data augmentation (normalization, cropping, and random flipping) together with the cutout tricks. We don't tt use knowledge distillation or any other advanced data augmentation tricks. Finally, we the initial learning rate as 0.025 with cosine annealing scheduling scheme. We repeat the same experiments for Zen-score.
As shown Table I0 ZiCo outperforms previous zero-shot NAS approaches, e.g, Zen-score and TE-NAS. Moreover, compared to the regular one-shot or multi-shot NAS methods, ZiCo achieves comparable higher test accuracy with at least 10x less search time.
Moot of the haseline approaches in Tahle use the setup as ours.
28

---

Published as a conference paper at ICLR 2023
Test Grad
Test SNIP p
70
70
Test accuracy
60
Test accuracy
60
50
50
40
40
2.5
5.0
7.5
10.0
12.5
15.0
Grad norm (a) Grad_nom
SNIP
(b) SNIP
acc (T= p=
vs. (r= p 0.44)
70
70
Test Test accuracy
60
Test accuracy
50
-0.2
-0.1
0.0
0.1
0.2
0.3
GraSP
Fisher (d) Fisher
GraSP
Test acc vs. Synflow (t- 0.61 p 0.81)
Test acc vs. Zen-score (T- 0.50 p 0.69)
Test accuracy
60
Test accuracy
50
40
40
5.0
7.5
10.0
12.5
15.0
17.5
20.0
50
55
Synflow
Zen-score
(e) Syntlow
(f) Zen-score
Test acc #Params 0x50 0.72)
Test vs. ZiCo (T- 0.54 0.73)
70
70
Test accuracy
60
Test accuracy
60
50
50
40
40
200000
400000
600000
200
220
260
280
#Params
ZiCo
#Params
(h) ZiCo
Figure 6: Real accuracy vs. various proxies on NATSBeneh-SSS search space for CIFAR10 dataset. 7 and p are short for Kendall's 7 and Spearman's respectively.
29

---

Published as a conference paper at ICLR 2023
Test Grad 0.49
p D.76)
45
40
40
accuracy
Test accuracy
35
35
30
30
25
25
2.0
2.5
3.0
3.5
4.0
4.5
5.0
Grad_ _
SNIP
(a) Grad_norm
(b) SNIP
vs. (T= p= 0.42)
vs. (g= 0.41 p-5.7)
45
45
40
40
Test accuracy
Test accuracy
35
35
25
25
20
20
0.1
0.2
0.3
0.4
0.0002
0.0004
0.0006
0.0008
GraSP
Fisher
GraSP
(d) Fisher
Test acc vs. Synflow (r- 0.39 p 0.57)
Test acc vs. Zen-score (T 0.69 p 0.871
45
45
Test accuracy
40
Test accuracy
40
35
30
30
25
25
20
20
100
150
200
25
30
35
40
45
50
55
Synflow
Zen-score
(e) Synflow
(f) Zen-score
Test acc #Paams (t 0.65 p-0.80 0.844
Test vs. ZiCo
0.70 0.88)
45
45
Test accuracy
40
Test accuracy
35
35
30
30
25
25
20
200000
400000
600000
200
220
240
260
280
300
320
# PParams
ZiCo
#Params
(h) ZiCo
Figure 7: Real test accuracy vs. various proxies on NATSBench-SSS search space for ImageNet16. 120 dataset. and are short for Kendall's and Spearman's 's p, respectively.
30

---

Published as a conference paper at ICLR 2023
Test Grad (r- p=
Test SNIP
Test accuracy
Test accuracy
0.6
0.6
0.2
0.2
0
400
600
1000
1200
2000
4000
6000
Grad norm
SNIP
(a) Grad_norm
(b) SNTP
acc (r p= 0.29)
acc vs. fr= 0.20 p=
0.8
0.8
Test Test accuracy
Test accuracy
0.6
0.6
0.2
0.2
5000
10000 15000 20000 25000
250
500
750
1000
1250
GraSP
Fisher
GraSP
(d) Fisher
Test acc vs. Synflow (r- 0.23 o- D.35)
Test acc vs. Zen-score (t 0.46 0.63)
0.8
0.8
Test accuracy
Test accuracy
0.4
0.4
0.2
50000
100000
150000
50
75
100
125
150
175
Synflow
Zen-score
(e) Synilow
(f) Zen-score
Test Params (r- 0.31 p-0.33)
Test ZiCo (T- 0.46 0
'18"
Test accuracy
Test accuracy
0.6
0.6
0.4
0.4
800
1000
#Params
1e7
ZiCo
#Params
(h) ZiCo
Figure 8: Real test accuracy vs. various proxies on NASBench101 search space for CIFAR10
dataset. 7 and p are short for Kendall's 7 and Spearman's respectively.
31


Reviews:
[{"review_id": "xrogQT5RUQ", "reviewer": "Reviewer_oG3W", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new zero-cost proxy (called ZiCo) for neural architecture search motivated by theoretical insights about the relationship of statistics of gradient across different input samples (absolute mean and standard deviation) and a network's converge speed.\nThe proposed proxy is evaluated by investigating ranking correlation on NATSBench-TSS, NATSBench-SSS and NASBench101, as well as by end-to-end NAS performance (guiding an evolutionary algorithm) using MobileNetv2 search space on ImageNet.\nAdditionally, experiments designed to validate theoretical claims and ablations, including investigation of ZiCo's correlation to accuracy on NATSBench-TSS with varying number of batches and batch size, are also presented.", "summary_of_the_review": "I like the paper and the presented attempt at designing a theoretically-grounded zero-cost proxy for NAS.\nOverall, I am leaning towards accepting the paper even with a high score. However, since I am not sure about some important aspects of the paper, I am leaving a lowered score for now and hope that the authors will be able to adequately address my concerns.", "strength_and_weaknesses": "**Strengths:**\n\n- a novel zero-cost proxy for NAS grounded in theory is always a nice thing to see\n- overall good writing and organization of the paper\n- good performance of the proposed method (although see below)\n\n**Weaknesses:**\n\nI haven't actually found anything that I would confidently consider a major weakness. I would have a series of suggestions how to improve writing in certain places, as well as possibly extending evaluation, but these are minor things.\nMore importantly, I have two questions to the authors which might turn out to be major weaknesses, but it is hard to conclude that just from reading a paper and therefore I would like to give the authors a chance to explain these things.\n\n1. Theoretical contributions in Section 3 are concluded with a statement that \"(...) network with high training convergence speed should\nhave high absolute mean values and low standard deviation values for the gradient (...)\", which is used to motivate design of ZiCo.\nI wouldn't say that this statement is incorrect (although, admittedly, the analysis from Section 3 it's not my primary area of expertise), however I have some doubts regarding applicability of this statement to NAS.\nSpecifically, it is a common pattern observed in practice that networks that converge faster usually converge to worse local minima - one of the most representatives examples could be two networks with significantly different number of parameters, usually a smaller network would converge much faster but to much worse results, whereas it takes longer to optimize networks with significantly more parameters but they tend to achieve better results.\nHow is the analysis provided helpful in those situations? Does it provide us with means to correctly identify such cases?\nAdditional bonus question: doesn't the assumption about $g_i~\\mathcal{N}(0,\\sigma)$ in Theorem 3.2 undermine applicability of Theorem 3.1? If I am not mistaken, under this assumption $\\mu_j$ in Eq. 5 is going to be 0, and Remark 3.1 is not really helpful.\n\n\n2. How much ImageNet results depend on distillation from EfficientNet-B3?\nPersonally, I consider it cheating when a NAS methods shows that it can discover \"better\" architectures but compares them using a different training scheme.\nIt is a well-known fact that even old architectures can benefit greatly from utilizing state-of-the-art training scheme (e.g., see \"ResNet strikes back\" by R. Wightman et al.), and it seems that the paper currently contains comparisons between ZiCo and other NAS methods where ZiCo might have unfair advantage of an improved training scheme.\nFor example, the paper makes direct comments about results such as: \"Moreover, if the FLOPs is 600M, ZiCo achieves 2.6% higher Top-1 Accuracy than the latest one-shot NAS method (MAGIC-AT) with a 3× reduction in terms of search time\" - not only is MAGIC-AT not the best Zero-Cost method for 600M FLOPs in Table 3, the authors of MAGIC-AT specifically write in their paper: \"For stand-alone model training, to be consistent with the previous works, we follow the same strategy as ProxylessNAS5 and do not employ tricks like cutout or mixup\", while ZiCo not only includes all these tricks, it also employs distillation from much more accuracy EfficientNet-B3!\nOn the other hand, ZenNAS, which roughly follows the same training procedure, achieves much closer results to the proposed method, up to the point that it might very well lie within randomness of each method.\nTo adequately address this issue, I would suggest the authors to at least limit their comparison to methods that use the same search space and training scheme, but ideally also include NAS results in a different setting, as presenting end-to-end results only on a single search space is, in general, considered rather limited. How about performance of the proposed method on a significantly different search space like DARTS?\nAlso, how about comparison with other zero-cost methods?\nIn general, my current impression is that the choice of baselines and retraining scheme was a bit cherry-picked to present the proposed method in a favourable way.\nI am happy to be convinced it is not the case, though.\n\n**Minor suggestions and questions:**\n\n - within your computational capabilities, please try to run experiments multiple times and report avg. + std. (or whatever other \nconfidence metric)\n - is there a point in highlighting \"key questions\" and \"major contributions\" in Introduction? Is is there to make sure the reader understands that the contributions are major or that the following bullet points are in fact contributions?\n - \"We demonstrate that, compared to all existing proxies (...)\" - results in the paper hardly demonstrate comparison with \"_all_ existing proxies\"... I would expect more linguistic rigour from a math-heavy paper like this; examples of published proxies that are not included in the comparison: NASWOT (Mellor et al., ICLM'21), TE-NAS (Chen et al., ICLR'21), KNAS (Xu et al., ICML'21), NASI (Shu et al., ICLR'22), GradSign (Zhang and Jia, ICLR'22).\n - NATSBench-TSS is not NASBench201, as suggested by the header in Table 1\n - how would you explain the fact that correlation of ZiCo degrades with more batches? Shouldn't more batches result in better estimates of mean and variance, resulting in better performance of the proxy?\n - I am not exactly sure if highlighting that the proposed method works consistently better than #Params on benchmarks where #Params happens to be highly correlated with performance is really important for the paper... To be clear, it is worth mentioning that the proposed method works the best, etc., but specifically highlighting superiority w.r.t. the #Params baseline is a bit too narrow in my opinion - what about cases when #Params is not a good proxy? (the comment is specifically related to contribution 2)\n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "b44BrjKsZT", "reviewer": "Reviewer_9avK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "While existing training-free proxies can usually achieve compelling search results, they typically can not work consistently better than #Params in practice (White et al., 2022). So, this paper aims to improve such a state of affairs. Specifically, this paper firstly theoretically proves that the convergence of DNNs is highly correlated to the mean and variance of the gradient at initialization with respect to different input samples. Inspired by such a finding, this paper then proposes to use the inverse coefficient of variation on gradients as the zero-shot proxy for training-free NAS. Empirical results show that the proposed method in this paper can improve over other zero-shot proxies.", "summary_of_the_review": "Overall, my major concerns lie in the theoretical part and the empirical comparison of this paper. I hope the authors can address my concerns during the rebuttal period.", "strength_and_weaknesses": "Strengths:\n1. Overall, this paper is well-written and well-motivated.\n2. The proposed method in this paper is motivated by the theoretical convergence of linear models and DNNs.\n3. Extensive results in this paper have validated the effectiveness and efficiency of the proposed method.\n\nWeaknesses:\n1. While this paper is motivated by the inconsistent performance of existing zero-shot proxies, the reason why the proposed method is able to tackle this problem has not been well explained either from the empirical perspective or the theoretical perspective.\n2. There is a gap between the derived theoretical convergence and the proposed zero-shot proxy in eq.14. Firstly, Theorem 3.1 and 3.2 are the bounds for step t during the model training with SGD. This means that the convergences of linear models and DNNs are related to not only the initialization but also the model parameters during training and hence can not be simply determined by initialization according to the theorems in this paper. So, without further justification, simply using eq.14 alone may not characterize the convergence of DNNs well theoretically. Secondly, it seems that the mathematical form of eq.14 can not be directly derived from Theorem 3.1 and 3.2, i.e., the form of coefficient of variation doesn't appear anywhere in these theorems. So, the motivation for using the form of eq.14 is kind of weak to me. Thirdly, Theorem 3.1 and 3.2 can only characterize the convergence of models whereas we need to characterize the generalization performance of architectures in NAS. So, is there any other justification that authors can provide to support why characterizing convergence is already enough?\n3. This paper misses the comparison with other training-free NAS works [1,2] in their experiments.\n4. While this paper is motivated by the inconsistent performance of existing zero-shot proxies, I recommend more search results on other diverse tasks (e.g., the ones mentioned in (White et al., 2022)) to support the improved consistency achieved by ZiCo.\n\n[1] GradSign: Model Performance Inference with Theoretical Insights\n[2] NASI: Label- and Data-agnostic Neural Architecture Search at Initialization", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XCqgD00jpQs", "reviewer": "Reviewer_V9fp", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper first theoretically reveal how some specific gradient properties impact the convergence rate of neural networks. Based on their theoretical analysis, they propose a new zero-shot proxy, *ZiCo*, the first train-free proxy that works consistently better than #Params.\n", "summary_of_the_review": "\nThe authors theoretically reveal how the mean value and standard deviation of gradients impact the training loss of neural networks. And based on their theoretical analysis, they propose a new train-free proxy, ZiCo, which achieves better correlation scores with the real test accuracy. But there are still several concerns need to be addressed.\n\n# Update after reading response\n\nI think all my previous concerns are well addressed. Thanks the author for their effort. I raise my score as promised. ", "strength_and_weaknesses": "\nStrength:\n\nThe authors theoretically reveal how the mean value and standard deviation of gradients impact the convergence of neural networks. And based on their theoretical analysis, they propose a new train-freet proxy, ZiCo.  Experiment results have shown that ZiCo works better than previous zero-shot NAS proxies on multiple popular NAS-Benchmarks (NASBench101, NATSBench-SSS/TSS) for multiple datasets (CIFAR10/100, ImageNet16-120). \n\nWeaknesses:\n\nSeveral concerns in  **Clarity, Quality, Novelty, Reproducibility**. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "EuOWB_C9jRl", "reviewer": "Reviewer_AcGU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies train-free metrics for NAS.\n\nThe performance of existing train-free metrics is often inconsistent across different search spaces, less consistent than even simply counting parameters.\n\nThis paper presents a new train-free metric based on a theoretical analysis on the correlation of gradient statistics to network convergence.\n\nExtensive empirical results are provided on a wide range of popular benchmarks and also importantly on MobileNet space and ImageNet.\n\nWhile the results do not always outperform existing train-free metrics, it is much more stable across different search spaces, which is far more important.", "summary_of_the_review": "The paper is solving an important and relevant problem of train-free NAS metrics: their consistency issue across different search spaces.\nThe proposed method is simple yet theoretically grounded. I vote for acceptance.", "strength_and_weaknesses": "Strength:\n\n- The proposed method is theoretically inspired. The author provides an extensive principled analysis of how gradient statistics contribute to the convergence of the network.\n- The author provides extensive evaluations of the proposed metrics across popular benchmarks and also on MobileNet space. Empirical results are strong and consistent.\n\nWeakness:\n\n- [minor] Though extensive analysis, the theoretical findings are not too surprising: i.e. stabler and non-vanishing gradients help with network training.\n- While the paper presents detailed theoretical results on how gradient statistics affect convergence, it might not necessarily lead to better generalization. It is often the case that there are networks that converge fast but plateau quickly [1]. I’d like to hear the author’s take on potential ways to connect the current results with generalization errors.\n\nQuestion:\n\n- For ImageNet results, it is sometimes hard to make sense of the improvement since different methods could be using drastically different search spaces and training protocols. I wonder which specific training protocol the author uses to achieve the reported accuracy. Also, whether the search space is identical to some previous works or modified?\n\n[1] Zhou et al. Theory-Inspired Path-Regularized Differential Network Architecture Search. NeurIPS 2020", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%