MeCo: Zero-Shot NAS with One Data and Single Forward Pass via Minimum Eigenvalue of Correlation
Authors: Tangyu Jiang
Haodi Wang
Rongfang Bie
Venue: NeurIPS 2023 spotlight (2023)
Keywords: Neural Architecture Search
Zero-Cost Proxy
Evaluation Strategy
Feature Map
TL;DR: A new zero-cost proxy for NAS that requires a single forward pass using one data and achieves SOTA results.

Abstract: Neural Architecture Search (NAS) is a promising paradigm in automatic architecture engineering. Zero-shot NAS can evaluate the network without training via some specific metrics called zero-cost proxies. Though effective, the existing zero-cost proxies either invoke at least one backpropagation or depend highly on the data and labels. To alleviate the above issues, in this paper, we first reveal how the Pearson correlation matrix of the feature maps impacts the convergence rate and the generalization capacity of an over-parameterized neural network. Enlightened by the theoretical analysis, we propose a novel zero-cost proxy called $\mathsf{MeCo}$, which requires only one random data for a single forward pass. We further propose an optimization approach $\mathsf{MeCo_{opt}}$ to improve the performance of our method. We design comprehensive experiments and extensively evaluate $\mathsf{MeCo}$ on multiple popular benchmarks. $\mathsf{MeCo}$ achieves the highest correlation with the ground truth (e.g., 0.89 on NATS-Bench-TSS with CIFAR-10) among all the state-of-the-art proxies, which is also fully independent of the data and labels. Moreover, we integrate $\mathsf{MeCo}$ with the existing generation method to comprise a complete NAS. The experimental results illustrate that $\mathsf{MeCo}$-based NAS can select the architecture with the highest accuracy and a low search cost. For instance, the best network searched by $\mathsf{MeCo}$-based NAS achieves 97.31% on CIFAR-10, which is 0.04% higher than the baselines under the same settings. Our code is available at https://github.com/HamsterMimi/MeCo

MeCo: Zero-Shot NAS with One Data and Single Forward Pass via Minimum Eigenvalue of Correlation
Tangyu Jiang
Haodi Wang
School of Artificial Intelligence Beijing Normal University jty@mail. bnu lauu..du.ccom
School of Artificial Intelligence Beijing Normal University whd@mail 1. bnu edu.
Ronglang Bie*
School of Artificial Intelligence Beijing Normal University rfbie@bnu. edu. cn
edu..
Abstract
Neural Architecture Search (NAS) is a promising paradigm in automatic archi- tecture engineering. Zero-shot NAS can evaluate the network without training via some specific metrics called zero-cost proxies. Though effective, the existing zero-cost proxies either invoke at least one backpropagation or depend highly on the data and labels. To alleviate the above issues, this paper, first reveal how the Pearson correlation matrix of the feature maps impacts the convergence rate and the generalization capacity of an over- wver-parameterized neural network. Enlightened by the theoretical analysis, we propose novel zero-cost proxy called MeCo, which requires only one random data for single forward pass. We further propose an optimization approach MeCoopt to improve the performance of our method. We design comprehensive experiments and extensively evaluate MeCo on multiple popular benchmarks. MeCo achieves the highest correlation with the ground truth (e.g., 0.89 on NATS-Bench-TSS with CIFAR-10) among all the state-of-the-art proxies, which is also fully independent of the data and labels. Moreover, integrate MeCo with the existing generation method to comprise a complete NAS. The experimental results illustrate that MeCo-brsd BeCo-based NAS tecture with the highest accuracy and low search cost. For instance, the best network searched by MeCo-based NAS achieves 97.31% CIFAR-10 10, which is 0.04% higher than the baselines under the same settings. Our code is available at https//ggfhbb.coo/HHHaaattniiii
select the archi-
Introduction
Deep Neural Networks (DNNs) have been ubiquitously adopted in various fields due to their ability in hierarchical feature extraction (1-5). It is common consensus that the architecture of DNN is essential in model performance. Unfortunately, the manual trial-and-error method is non-scalable and inefficient, making infeasible find the globally optimal structure. Thanks the development of the Neural Architecture Search (NAS), it possible to automatically select the network architecture with the best performance.
Corresponding author.
These authors contributed equally this work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

There are abundant works proposed to improve the performance of NAS. The most fundamental observation is to fully or partially train the candidate networks with specific data and select the network with the highest accuracy. Though effective, these multi-shot NAS methods are inevitably resource-consuming, thus, are non-trivial to be adopted in real-world applications. To address this issue, the one-shot NAS has been proposed in which supernet is designed and only requires one-time full training [6]. In 2020, Mellor et al. 7 proposed the zero-shot NAS and realized an efficient approach in which zero-cost proxy is proposed to evaluate the networks without training.
Despite the effectiveness of the existing zero-cost proxies, there are some critical issues that remain to be solved. (i) Almost all current proxies are established from the network gradients. As consequence, computing these proxies requires at least one backpropagation, which is resource-consumingg (ii) The majority of the currently used proxies rely highly on the input data and labels. The reliance on the input samples underestimates the evaluation of the network's s intrinsic characteristies, and the incorrect labels (which are commonly occurred in real-world datasets) may obfuscate the ranking results. (iii) Although various zero-cost proxies have been proposed, the performance of those proxies can still be promoted in network evaluation.
Objectives. The main objective of this paper is to design a novel zero-cost proxy with better perfor- mance than the current methods. The proposed proxy should be easily computed by small number of data without backpropagation. Furthermore, to estimate the intrinsic trait of the architectures and avoid the label influence, our proxy should be label-independent.
Our Contributions. To this end, in this paper, we craft a novel zero-cost proxy for zero-shot NAS from a new perspective. The proposed proxy, called MeCo, outperforms the State-OffThheAnt (SOTA) zero-cost proxies in NAS and only requires one data sample for single forward pass. Specifically, we harness a novel observation on the multi-channel convolutional layers and view them as the "multi-sample fully-connected layers with constraints". This insight permits MeCo be computed by only one data. Moreover, we rigorously analyze how the Pearson correlation matrix of the feature maps impacts the training convergence rate and the generalization capacity of the networks, which theoretically proves the effectiveness of MeCo. Unlike the existing methods 97] MeCo is established upon each layer of the feature maps and hence requires only a single forward pass. Based on our design, we further propose an optimization approach MeCoopt to promote the performance of our method. The experimental results show that both MeCo and MeCo achieve a higher correlation with the network ground truth than the SOTA methods. For example, the Spearman correlation coefficients of MeCo on NATS- SATS--Bnnh-TSS. with CIFAR- 10 and CIFAR-100 are 0.89 and 0.88, respectively, which are 0.09 and 0.08 higher than the best baseline method. Our MeCo-based zero-shot NAS also acquires the highest accuracy among all the existing approaches, e.g., MeCo- based NAS selects the network with 97.31 1% accuracy, which is 0.04% higher than the SOTA work. In all, our major contributions are as follows.
We theoretically analyze how the Pearson correlation matrix of the feature maps impact the training convergence rate and the generalization capacity of the networks, based on the characteristics of the multi-channel convolutional layers.
We propose MeCo. a novel zero-cost proxy for zero-shot NAS that achieves better perfor- mance than SOTA methods. Through systematic analysis, we further proposed MeCo as an optimization approach. Our proxy is fully training free and data-independent, which requires only one data sample with single forward pass.
We rigorously implement our MeCo and extensively design the experiments to evaluate its performance on several popular benchmarks (e.g.. BAS--Benc-- 101, -ATT-Beenc---- NATS-Bennh- NAS Bench-301, and Transbench- with diverse datasets and random data samples. The experimental results show that our zero-cost proxy outperforms the existing methods, and MeCo-based NAS can select the network with the highest accuracy.
2 Related work
2.1 Zero-shot NAS and zero-cost proxy
Zero-shot NAS uses specific metrics called zero-cost proxies to evaluate the networks. Unlike the traditional multi-shot and one-shot strategies 110 6. 19, zero-shot NAS eliminates the training procedure thus significantly improves the efficiency. Various studies have been brought forward to

---

promote the quality of the zero-cost proxies, and most of them are based on the gradients. Mellor et al. firstly evaluated the performance of the initialized networks using the activation overlaps between data points. Abdelfattah et al. g proposed series of parameter-pruning based proxies including snip [20], grasp [21], synflow [22] and fisher 233. Recently, Li al. [9] proposed ZiCo, which firstly works better than the parameter amounts. These approaches need at least one backpropagation and rely on the data labels to compute the proxies. Another line of work [24H226] is based on the theory of deep learning such as NTK, which is independent of the labels yet still needs backpropagation. For example, Chen et al. 24 utilized the condition number of NTK to evaluate the trainability of the networks. Finally, there
few works that do not require backpropagation instance, Lin et al. [27] proposed Zen-Score, in which they design an efficient zero-cost proxy with Gaussian random inputs. However, Zen-Score requires multiple forward passes while our MeCo only needs a single forward pass.
data labels. For
2.2 Over-parameterized networks
wver-parameterizer networks have received lot of attention due to their outstanding effect and ease of optimization. Jacot et [28] demonstrated that the training dynamic of an infinite- width network follows a kernel called NTK
30]. For hiite-width networks, the training dynamic can 32 Further, Du et al. [3 proved that the loss of an over-
22
be illustrated by a gram matrix 31
parameterized network could converge to global minimum 33 and the training convergence
rate could be characterized by the minimum eigenvalue of the gram matrix. Some works also discuss the optimization of the training convergence rate (36) and the topological properties of DNNs (37.
3 MeCo: minimum eigenvalue of correlation on feature maps
3.1 Preliminaries
Notations. We define [n] [m]= (1, The lower and uppercase bold font represent vectors and matrices, respectively, e.g., x is a vector with entry Ti, and M is a matrix with entry [M] The minimum eigenvalue of M is denoted as \min(M). We define A o B as Hadamard product between two same-sized matrices A and B. 1mxn represents a m x n matrix filled by ones and || |l2 is used to represent the l2 norm of a vector. (0, and U (S} represent the standard Gaussian distribution and uniform distribution over a set S, respectively. We denote by X {x,, Y/ [x; E IRdx1 V/s E R. i E [n]] } the training set, where x; and y/4 represent the i-th data and label. I[{}} defined as the indicator function that demonstrates the event occurrence, such that for event A, I{A] = 1 if and
only if A happened, otherwise equals to
For input x E dgd weight vector w E Rdx1 in the weight matrix W E Rdxm and output weight gmx1 we denote f( ((W, a, x) as a neural network with single hidden layer such that
1m Σ (wo(
f(W, a,
where a is the activation function. this paper, we mainly consider the ReLU function due to its effectiveness, i.c., a²))= 21{2> > 0}. Given training set X, the optimization goal is to minimize
the empirical risk loss function
a) 1 1 (f(,, - y1)²
(2)
We follow the definitions in 31 and define the matrices H(t) and H follows.
Definition 1 (Gram Matrix), For a neural network with single hidden layer, the gram matrix H(t) e Rax= induced by the ReLU activation function on a training set X == {(x,, y1) with entry H()) is defined as:
H [())) Σ.,, (x), O, W. (1)x; 0}
where w, is a vector that depends on t. We further construct H with entry H ki such that
[ ]ij = E E [I"xxxxxxxx 2 20, wf 2 20]
We denote Ao == Amin )
3

---

Oparatin Connection
Inpul
Fitters
map
Output
Inputs
Hidden
Output
Figure I: Conversion between the multi-channe convolution and multi-sample fully-connected operation. The input size is w x and each filter size is x 3 x 3. Each input channel can be flattened with size d x 1, with constrained fully-connected operations (dot lines for zero operations and solid lines for full connection). The final output is computed by sum operation (dashed lines) from the hidden nodes.
h. We collect the three flattened samples to obtain the output
Remark 1. Gram matrix H(t) reflects the prediction dynamic at the t-th iteration of the network training. Du et al. (37) proved that for all t 2 0, [H((t) H l| - 0 as - co. Moreover, the gram matrix H has the following key property: if k x,, Vi + j. then N The proof of this property can be found in Theorem 3.1 in 131y.
Definition 2 (Pearson Correlation Matrix). P(X) is Pearson correlation matrix with the (i. (ith entry (i as
[P p(x,, [[[x [xx)((x Mx;)]
(5)
xx,
where Mx and 0x are the mean and standard deviation of x, respectively.
Remark 2. Pearson correlation matrix P(X) is closely related to H(t). For instance, suppose [m] and i E [2]. then [H(t))12
X1 I)..I), X; Rax1 and wx (f)x; 2 0, for (d ()(()]((X]] We will use this characteristic to approximate the training convergence rate and generation cupacity of the networks when designing our proxy.
3.2
The construction of MeCo
To present the theoretical analysis, we first approximate the Convolutional Neural Network (CNN) to an over-parameterized Neural Network (NN) and then craft our proxy.
3.2.1 Back to convolution
The convolutional layers are the fundamental parts of CNN. Suppose we have the input x and the filter w Roa We set the stride size to one and retain the size of the feature maps via zero padding, then the convolutional layer can be formally expressed as:
Koutli. = Σ Go Σ P
b- [ letp+1bbtp+1 [xplatit64)
(6)
cm
where xf, (resp. w represents the c-th channel of Xin (resp. w). 1k [w], [h]. In this paper, observe that Xout and x be flattened to one-dimensional vectors Nout E Rddx and [56]] E [dx where E [Cin], d x h. More concretely, we have the following transformations:
Nout ΣSn A.o((B. xx))
Gn
s.l. A R dxxd
[Aclis = I[j (c 1)
B, Rdaxd
[B.lk = [[(cc- <i cd).
(8)
B, o W satisfies weight sharing constraints

---

where d, = Cin x d, W E Rdxdd is the weight matrix. Hence, the convolutional layer in CNN is equivalent to collycooneette layer with constraints, i.e., shown in Equation [ To further simplify the problem, we relax the second constraint to B, = 1d, xd and ignore the last constraint. As consequence, we obtain multi-sample fully-connected network in which each flattened channel x is regarded an independent data sample, and the total number of samples is Gin- To better illustrate our insight, we present an example the conversion procedure in Figure]] [
3.2.2 Over-parameterized neural networks
The over-parameterized NNs are competitive in hierarchical feature extraction due to a large number of parameters. One of the typical architectures is the networks with wide hidden layers, which is proved to be tractable in training (38). In the previous subsection, we convert multi-channel convolutional layer to a multi-sample fully-connected layer with constraints. We further argue that if the number of hidden nodes in the transformed fully-connected layer is large enough, then can be viewed as an over- over-paramet parameterized NN layer. Therefore, the characteristics of the over- parameterized NN can be transferred to CNN. To this end, we present the following theorem [31 about the convergence rate of the fully-connected NN with a single hidden layer as follows.
Theorem 1. gram matrix H O. ||x,I12 1, Iyd for some constant C and i [ni,, hidden and i.i.d. initialize w, (0, a, U[[-1, 1}} for E [m], then with 2g53
nodes = Ω
probability at least - 8 over the initialization, the following inequality holds:
(x( - exp <xpp (=x((>>o))lf(((O)) a, y11
(9)
This inequality shows that Xa positively affects the training convergence rate of the network. We further point out that the convergence rate of the network is independent of the label y. which makes it possible to measure the network performance with only a single forward pass. Based this observation, establish our proxy the intermediate feature maps measure the performance of the network.
Remark 3.
2 further analyze the relationship between the minimum eigenvalue of the matrix P(X) and the training convergence rate of the over-parannn peee-parameterizedd network. We summarize results in the following theorem:
Based on Theorem 1 and Remark
Theorem 2. Suppose f is an NN with a single hidden layer and ReLU activation function. Assume X E _ddx" w(0) ~ (O, P(X) > 0, Po == Amin Amin(P(X) (P(X)), and hidden nodes m = S then the following formula holds with probability at least ö over the initialization
X
(t), a, X) - y1l2 S exp( X. - y
(10)
where is a constant depending on m, and d.
Proof sketch. The key of the proof is to find the relationship between A and pa by Hoeffding's inequality and Weyl inequalities [39. We provide the full proof in Appendix A Theorem 2 shows that Po can reflect the convergence rate of the network to a certain extent. The advantage of P(X) over H() is that its computation only depends on the data. Therefore, it is feasible to estimate the training convergence rate of the network only through the feature maps.
Other than the convergence rate, we also analyze the relationship between po and the generalization capacity of the over-pun wee--paramterriee NN. We present the results the following theorem:
Theorem 3. For an over-parumeterized neural network with the loss on the testing set as L(W).
Let y (yi,...; yN) and x be the step of SGID, 7 RC1vyT H 0s -reee-yyy// (y/mm/N) for some small
enough absolute constant Under the assumption of Theorem 2 for any E (0, e e there exists m"
N, Ao), such that if m 2 m², then with probability at least 5. we have (6, m²(,,
yT PoN + +0(1
log(1/5)
E[L(W)] < OCC
V
N
(11)
where C, C², are constants.
Proof sketch. The proof of the above theorem derives from the Corollary 3.10 of [40] and Section D.2 of (26). We present the detailed proof in Appendix A.2
5

---

3.2.3 New zero-cost proxy: MeCo
The above theorem and analysis indicate the following key insights:
A multi-channel CNN layer can be viewed as multi- sample over- over-paramann parameterized NN layer.
The minimum eigenvalue of P(X) positively affects the training convergence rate and the generalization capacity of NN, which is independent of the labels.
Enlightened by these observations, we harness the Minimum eigenvalue of the Pearson Correlation matrix upon each layer of the feature maps to craft our novel zero-cost proxy called MeCo, such that Definition (MeCo). Assume the NN f(; 8) has a total of layers, then MeCo is defined as
MeCo = -
D
Amin (P(F
(12)
where ('(X;0) 0) represents the i-th feature map with the initialized parameters on dataset X. Remark 4. Note that the Pearson correlation matrix contains the process of data normalization, thus our MeCo eliminates the deviation caused by the data, which is more conducive to discovering the essence of the network architectures.
Experiments and evaluations
We evaluate MeCo from three aspects: (i) The correlation with the ground truth and comparison with the baseline proxies; (ii) The dependency on data/labels; (iii) Performance of MeCo-based NAS scheme. We first describe the experimental configurations and then give the detailed performance.
4.1 Experimental configurations
Hardware. We fully implement our MeCo in Python. We evaluate MeCo on a desktop with an Inter Core 17-12700F CPU and GeForce RTX 3090.
contains 15,625 CNN architectures with different topologies. We demonstrate the performance of the zero-cost proxied on NATS-Bench- Bench-TSs. with CIFAR- (43, CIFAR- 100 [43. 1- and three extra datasets [45] in Appendix E.1 (ii) HATS-Bench--SS 42 contains 32,768 CNN architectures with the same topology but with different numbers of channels. We show the results on NATS -Bench- SSS with CIFAR-I0. 10,, CIFAR-100 and ImageNet16- 120.. (iii) NAS-Bench-301 446 is surrogate NAS benchmark for the DARTS search space. We illustrate the results with CIFAR- 10 and the extra three datasets in Appendix E.I (iv) TransBench-JO0 44 is benchmark composed of two subsets, ie., TransBench- -Mirro and TransBench- 101-Macro. The former is evaluated with 10 datasets and the latter with 7 datasets. We present these results in Appendix
Benchmarks. We use several popular benchmarks in NAS. (i) NATS-Bench-TSS
E.3 (v) NAS-Benck /0/ (48) includes 423,624 cell-based CNN architectures, which are trained and evaluated on the CIFAR-10 (vi) AutoFormer
dataset and shown in Appendix H.2
49 and MobileNet OFA 50) The description
and results are shown in Appendix
E.4
Baselines. The baselines for zero-cost proxies include the number of parameters Param, grasp 21
fisher 23 snip [20], synflow [22], jacov 77. grad_norm norm (8), NTK (44, zen [27], NASWOT 7
KNAS 51 NASI [52). GradSign [53], and ZiCo [9. Specific forms of these proxies provided in
Appendix We adopt the Spearman rank correlation coefficient between zero-cost proxies and the dataset ground truth to measure their performance.
4.2 Performance of our MeCo and comparisons
We evaluate p between MeCo and the ground truth, and compare it with the baseline zero-cost proxies various benchmarks. We present the results on NATS- MATS-Bench-TSS and MATS-Bench-SSS. in Table We run MeCo for ten times with
I and the results on WAS-Bench-301 are provided in Table 2 different inputs and present the mean and standard deviation.
TSS. We run our MeCo and baseline proxies on 15,625 networks of NATS-Bench- TSS with three public datasets. As see in Table MeCo achieves 0.89440.003, 0.883-00005.

---

Table 1: Spearman correlation coefficients p of proxies on HATS-Bennch- TSS and BATS-Bench-SSD
NATS-Bench-TSS
NATS-Bench-SSS
Approach
CIFAT-10 10
CIFAR- 100
ImageNet16
CIFAT-10 10
CIFAR 100
ImageNet16
grasp
0.39
0,46
0.45
-0.13
0.01
0.42
fisher
0.40
0,46
0.42
0.44
0.55
0.47
grad_norm
0.42
0.49
0.47
0.51
0.49
0.67
snip
0.43
0.49
0.48
0.59
0.62
0.76
synflow
0.74
0.76
0.75
0.81
0.80
0.57
#arrm
0.72
0.73
0.69
0.72
0.73
NWOT
0.77
0.80
0.77
0.45
0).43
0.42
jacov
0.73
0.70
0.70
0.30
0.13
0.30
NTK
0.76
0.75
0.72
0.34
0.29
0.28
zen
0.38
0.36
0.40
0.69
0.71
0.87
KNAS
0,20
0.35
0.42
0.25
0.12
0.32
NASI
0.44
0.43
0.63
0.17
0.04
0.20
GradSign
0.77
0.79
0.78
0.21
0.16
0.04
ZiCo
0.80
0.81
0.79
0.73
0.75
0.88
MeCo (Ours)
0.894
0.883-10.005
0.845:10.004
-0.79=0.01
-0.87:10.01
-0.86:10.02
MeCoopt (Ours)
0.901=00002
0.890=
0.000
0.89=:0.002
0.83=0.004
0.09000003
and 0.845=00.004 correlation on CIFAR-10, CIFAR-100, and ImageNet16- respectively. The variation shows that our method is stable and independent of the input samples. The Spearman correlation coefficients are significantly higher than the baselines, e.g., the SOTA proxy ZiCo 9 only achieves 0.80, 0,81, 0.79 on three datasets, which is 0.06 to 0.09 lower than ours. Note that ZiCo the first proxy that proved to be consistently better than the naive proxy Param and requires batch of input data. On the other hand, we surpass all the previous works and only use one data sample. The high correlation coefficients demonstrate the effectiveness of MeCo, which is consistent with the theoretical analysis. To make our results more intuitive, we sample 2,000 networks randomly and present the relationship between MeCo and the ground truth on three public datasets. The results shown in Figure 4(a) in the Appendix E where the trend in the scatter charts effectively proves that our zero-cost proxy has a highly strong correlation with the architecture quality.
The results of MeCo 32,768 networks NATS-Bench-SSY are summarized Table Among all the datasets, MeCo shows the tigheetccorrlaatt with the ground truth on CIFAR- 100, i.., 00.87 + 0.01, which is 0.07 higher than the best baseline synflow. MeCo also achieves stable and competitive results on CIFAR-10 and ImageNet16- with one data as input. We find that MeCo is highly negatively correlated with the test accuracy, which is somehow counterintuitive. In fact, MeCo is sensitive the number of channels (#channels) that cause this phenomenon. Specifi- cally, the channels viewed the data samples as described in Section 3.2.1] This leads to the fact that the more channels contained, the larger the On
NATS-Bench-SSC.
Channels v.s. Eigenvalue
Minimum Eigenvalue
0.8
0.6
0.4
0.2
200
400
Number of Channels
Pearson matrix, which will lead to smaller the other hand, larger #channels will normally lead to higher accuracy of the architectures (yet lower convergence rate). Thus, the variation of #channels in NATS- Sancc-SSS(chhoen from to 64) leads to a negative correlation on this benchmark. In NATS- SANTS-Benc--TSS however, all the networks share the same #channels each stage, thus MeCo does not show negative correlation. To verify this, we generate random data with different numbers of channels and calculated Po respectively, and demonstrate the results in Figure We also sample 2,000 networks randomly and present the correlation of MeCo test accuracy Figure 4(b) in the Appendix E
Figure 2: The influence different channel numbers of data on the minimum eigenvalue.

---

We demonstrate the results of MeCo and the baseline proxies on 301 with CIFAR-10 Table can be shown from the results that MeCo and op also achieve the highest correlation with the testing accuracy on NATS Bench-301, which is 0.04-0.05 higher than the SOTA approach ZiCo. More experimental results of MeCo can be found in Appendix
Table 2: p between zero-cost proxies and test accuracy
MAS-Bench-301 with CIFAR-10
Buselines
Dulaset
MeCo
McCo
grasp
fisher
grad_narm
snip
synflow
norm
Paaram
zen
jacov
nwot
ZiCo
CIFAR-10
0.7:1001
0.71
0.34
-0.88
-0.04
-0.05
0.18
0.45
0.46
0.43
-0.04
0.47
0.66
4.3
Dependency on data
MeCo is designed to be fully data-indepenndet due the characteristics of Pearson correlation matrix (Theorem 2 To further illustrate this attribute, we generate a random dataset and use it as the input of MeCo and NTK 244 which is also independent of the data and labels. We compute the Spearman correlation coefficients between MeCo and the test accuracy on three public datasets, and compare them with the baseline approach. All the results for MeCo is ran ten times with random inputs.
More concretely, the random data is generated following a Gaussian distribution and fed into the initialized network. Note that the baseline method requires a batch of random data input, while MeCo only uses one. We present the results for NATS-Bench- Bench-nnhhhSS TSS and NATS-Bench S-s--BBen--SSSS in Table
The results show that even if we use random data as the inputs, MeCo is still able to maintain high correlation with the corresponding ground truth. For example, P 0.87 on NATS-Bench TSS with CIFAR-10 and -0.93 on NATS- Bench-SSS with ImageNet16- 120, which are significantly higher than the data-independent proxy NTK. Note that most existing proxies rely the gradients and backpropagation. Hence they cannot utilize the random input data for architecture evaluation, such as ZiCo and jacov.
Table 3: Spearman correlation coefficients of MeCo and NTK with random data on NATS- Bench-TSS and NATSSBenchh-SS.
NTAS Bend-TTS
NATS Bendt-SS8
Dataset
MeCo
NTK
MeCo
NTK 24
0.87::0.00
0.87=00.00
CIFAR-10U
0.85+0.001
0.79
-088+00001
0.16
ImageNet16-120
0.83+00.001
0.76
-0:94+0.000
0.20
4.4 NAS with MeCo
We integrate our MeCo with the existing search space and generation strategy to comprise a com- plete NAS method. Specifically, we use NATS- Bench-TSS TSS, DARTS-CNV CNN (6). and MobileNet V3 [54] as the search spaces to demonstrate the performance. We use the Zero-Cost-PT [55] as the generation strategy. The algorithm of MeCo- based NAS and the results MobileNet V3
NATS Beach TSS
NATS Bench SSS
0.50
0..5
-0.7
0.65
0.53
presented in Appendix and F.3 respectively.
dala size
data size
We directly evaluate all net- works in NATS-Bench-TSS using MeCo and baseline proxies. The average test accuracy of the Top-10 networks on three datasets is summa- rized in Table 12 in Appendix F.I As shown in the table, the average test accuracy on CIFAR-I0 of MeCo is 0.08% higher than the best baseline ZiCo. Moreover, we further search the networks using Zero-Cost-PP with different proxies and run the search algorithm three times. The networks searched have the highest average test accuracy on three public datasets, that is, 93.76%, 71.11%, and 41.44% on CIFAR-10 10, CIFAR- 100, and ImageNet16-122) respectively. The results are provided in Table 13 Appendix F.
NATS-Bench-TSS.
CIFAR-10:
CIFAR-
ImageNet16-122
Figure 3: Spearman correlation coefficients of MeCo with different data size on TSS and
respectively.
DARTS-CNN. We compare our MeCo-based NAS with multi-shot, one-shot, and zero-shot NAS schemes in DARTS-CNI spaces. All the NAS schemes exccuted on CIFAR-10 and CIFAR-100

---

Approach datasets, respectively, to compare the Top-1 errors and the search cost. For zero-shot NAS, we use Zero-Cost-PT as the generation strategy due its effectiveness. The results on CIFAR-10 10 are summarized in Table 4 where we denote multi-shot, one-shot, and zero-shot as MS, OS, and 7S, respectively. We present the CIFAR-100 results in Appendix F.2 The results demonstrate that our MeCo-based NAS outperforms the existing baseline methods. More concretely, for zero-shot methods, MeCo outperforms all the baselines for 0.04% to 0.43% on Top-1 error with a similar level of search cost under the same generation strategy. For training-based methods, MeCo-based NAS achieves competitive accuracy but with much less search cost. For instance, our approach requires only 0.08 GPU days and obtains 97.31% accuracy, while DARTS- TIRTS-PTTT costs 10x GPU days than with 0.08% higher accuracy.
Table Comparisons of MeCo-based NAS with baselines using DARTS-CNN and CIFAR-10
Test Error (%)
Search Cost
Params
Method
(GPU Days)
(M)
AmoebaNet-A 56
3.34 + 0.06
3150
3.2
MS
PNAS 57
3.41 + 0.09
225
3.2
MS
DARTS (1st)
3.00 0.14
1.5
3.3
OS
DARTS-PT(588
2.61::00
0.8
3.0
OS
SDARTS-RS 59
2.67 0.03
0.4
3.4
OS
SGAS (Cri. 60
2.66::0.21
0.8
3.7
OS
Eigen-NAS
7.4
ZS
TE-NAS [24)
2
0.05
3.8
ZS
Zero-Cost-Pi
synflow
22
0.11
0.03
5.1
ZS
Zero-Cost-P1 fisher
23
0.16
0.05
2.5
ZS
21
0.10
0.1
3.3
ZS
grasp
Cas--Cot-PPPP Prost-PTjacce jacov
0.15
0.04
3.5
ZS
[20
2.90
0.04
4.0
ZS
Zero-Cost
Cas-Coot--PPi NTK
24
2.89
0.21
4.1
ZS
Zero-Cost-PIT zico
2.80 + 0.03
0.04
5.1
ZS
pero-Cost-PPTMeca (Orr)(sss)
2.69 + 0.05
0.08
4.2
ZS
We remark that the experimental results in this section demonstrate the following properties of MeCo: (i) High correlation with the ground truth; (ii) Requies only one data without labels for a single forward pass. That is because MeCo is established upon the observations over the multi-channel CNN layers. Moreover, the minimum eigenvalue of the Pearson correlation matrix independent of the data labels, and thus we exert MeCo the feature maps instead of the gradients.
Diseussion and Optimization
5.1 Optimization method MeCoopt
In the previous sections, we illustrated the theoretical basis of MeCo and evaluated our proposed proxy various benchmarks. However, as described in Section 4.2 the negative correlation NATS-Bench-SSS and some other tasks (e.g., Transbench- 101 the appendix) reflect that MeCo highly sensitive to the number of channels. Although this phenomenon does not contradict the theoretical results or undermine the effectiveness of MeCo, it might problematic when Po = 0. To this end, we present optimization method on top of MeCo to alleviate the channel-sensitiig trait.
Specifically, for convolutional layers, Po is strictly greater than zero if for Vi j. 2; zy, and < X h. where e is the number of channels, we, h are the size of the inputs. Thus, in real-world applications, MeCo might lose efficacy during the down-sampling procedure. To address this issue, instead of flattening all the channels of the feature map as described in Section B.2.1] we randomly sample a fixed number of channels and flatten them as matrix P'. We then compute the final result by multiplying the minimum eigenvalue of P' with channel weight, such that
(5)
MeCogpt Σ i=1 n
Amii (P')
(13)

---

where c(') is the number of channels in the i-th layer, and n is the fixed sampling numbers. The high-level idea of this optimization is to limit the dimension of the Pearson correlation matrix by constraining #channels. Instead of computing upon large matrix, we calculate the minimum eigenvalue upon a fixed-sized matrix and then enlarge it with corresponding constants. Note that the bonus of this optimization is that the time cost can be controlled because the matrix dimension is significantly reduced compared to the original one.
To show the effectiveness of MeCoopt. we calculate the Spearman correlation coefficients of McCOopt on AATS-Bench--SS. Transbench-100 101 (Table and Table ITI. All the experiments are conducted under n. = 8. The results demonstrate that opt effectively solves the negative correlation issue on multiple benchmarks, e.g., NATS- Bench-SSS and TransBench- 101. Meanwhile, the majority of the positive correlations are promoted up to 0.23, and the remaining results are not impacted.
SATS-Bench-SSS (Table D.. NATS- SAT'S-Bench-333 cench-301 (Table and Table g), and
5.2 Ablation study
Sample size. We consider the effect of the sample size on the performance of MeCo. We select the size of data from {16, 32, 64, 128, 256]. respectively, and calculate the Spearman rank correlation coefficient p between MeCo and the test accuracy of the networks on three public datasets. The results are summarized in Figure 3
p increases rapidly before size 64 and grows slowly after that. The maximum value is acquired at size 128, which is slightly higher than size 64. On the other hand, the overall fluctuation is relatively large on MATS-Bench-SSS The Spearman correlation coefficients are low when the size is smaller than 32, and reach higher at 32. Then p reduces as the sample size grows larger. The ablation results show that the most appropriate size of random data is around 32 and 64, which is also adopted in our settings.
For WATS-Bench-TSS
Sample numbers. We explore the performance of MeCo regarding the sample numbers that are used as the inputs. We randomly choose different number of samples to evaluate the architectures in the entire ASTS-Bench-TSS and HATS-Bench.
respectively. The results are shown in Figure 5 It can be demonstrated from the figure that MeCo is relatively stable when varying the number of samples. The performance MeCo fluctuates around 0.01 throughout the experiments. These results support that MeCo only requires one data sample.
Fixed channel numbers n. We conduct an ablation study on n v.s. MeCoopt with TSS and NATS-Bench-SSS to illustrate the best choice of n. The results are shown in Table
Table 5: Spearman correlation coefficients p of proxies on NATS-Bench-TSS and NATS -NTS-Bench-SSS
NATS-Bench-TEE
NATS-Bench-SSS
Approach
CIFAT-I0
CIFAR-100
ImageNet16
CIFAT-10
CIFAR-100
ImageNet16
0.87.L 0.003
0.88.L 0.002
0,84.1 0.005
0.8000.005
0.82.1 0.003
0.84_ 0.003
0.88.1 0.004
0.88.1 0.001
0.84.L 0.004
0.88.1 0.007
0.83.L 0.002
0.85.L 0.006
n
0.90-L 0.002
0.89.1 0.003
0.85 0.003
0.89.1 0.002
0.83.L 0.004
0.89 0.003
The results show that with n growing larger, MeCoopt increases by 0.1 to 0.5. We set n = 8 in our experiments to obtain the best performance.
6 Conclusion
In this work, we propose a novel feature-based zero-cost proxy called MeCo and its optimization method MeCo.pt. Unlike the existing methods, our zero-cost proxies require only one data for single forward pass. Specifically, we theoretically approximate multi-channel convolution layer to an parametteeee NN layer. We then harness the relationship between the theoretical properties and the minimum eigenvalue of the Pearson correlation matrix to craft our new proxies. We rigorously implement our proxies and extensively design the experiments. The experimental results show that MeCo and MeCo,pt significantly outperforms the SOTA zero-cost proxies, which is also independent of the data and labels. Moreover, MeCo can be integrated into a complete NAS and enables us to efficiently find the architecture with the highest accuracy.
10

---

Acknowledgment
We sincerely thank all the reviewers of 23 for their constructive suggestions which signifi- cantly improve the quality of our paper. The work was supported by National Key R&D Program of China [Grant No. 2022ZD01 15901J, in part by the National Natural Science Foundation China (Grant No. 62177007), and the China-Central Eastern European Countries High Education Joint Education Project (Grant No. 202012).
References
[1] K. Simonyan and A. Zisserman, "Very deep convolutional networks for large-scale image recognition," in International Conference on Learning Representations, 2015.
[2] K. He, X. Zhang, S. Ren, and Sun, "Deep residual learning for image recognition." in Proceedings of the IEEE conference computer vision and pallern recognilion, 2016, pp. 770-778.
[3] J. Redmon, S. Divvala, R. Girshick, and A. Farhadi, "You only look once: Unified, real-time object detection," in Proceedings of the IEEE conference on computer vision and patlern recognition, 2016, pp. 779-788.
[4] S. Hochreiter and J. Schmidhuber, "Long short-term memory." Neural computation, vol. no. 8, pp. 1785-1780, 1997.
[5] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and Polosukhin, "Attention all you need," Advances in neural information processing systems, vol. 30, 2017.
[6] H. Liu, K. Simonyan, and Y. Yang, "DARTS: Differentiable architecture search," in International Conference on Learning Representations, 2019
[7] J. Mellor, J. Turner, A. Storkey, and E. J. Crowley, "Neural architecture search without training."
in International Conference on Machine Learning. PMLR, 2021, pp. 7588-7598.
[8] M. S. Abdelfattah, A. Mehrotra, L. Dudziak, and N. D. Lane, "Zero-cost proxies for lightweight nas," " in International Conference on Learming Representations, 2021.
[9] G. Li, Y. Yang, K. Bhardwaj, and R. Marculescu, "Zico: Zero-shot NAS via inverse coefficient of variation on gradients," " in The Eleventh International Conference on Learning Representations, 2023.
[10] B. Zoph and Q. Le, "Neural architecture search with reinforcement learning,"" in International Conference on Learning Representations, 2017.
[11] L. Xie and A. Yuille, "Genetic enn," in 2017 IEEE International Conference Computer Vision (ICCV), 2017, pp. 1388-1397.
[12] B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le, "Learning transferable architectures for scalable image recognition," Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 8697-8710.
[13] E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin, "Large-scale evolution of image classifiers," in International Conference on Machine Learning. PMLR, 2017, pp. 2902-2911.
[14] C. Thornton, F. Hutter, H. H. Hoos, and K. Leyton- "Auto-weka: Combined selection and hyperparameter optimization of classification algorithms," in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, 2013, pp- 847-855.
[15] Y. Geifman and El-Yan "Deep active learning with neural architecture search," Advances in Neural Information Processing Systems, vol. 32, 2019.

---

[16] T. Elsken, J. H. Metzen, and F. Hutter, "Efficient multi-objective neural architecture search via lamarckian evolution," International Conference on Learning Representations, 2019.
[17] M. Javaheripi, G. de Rosa, S. Mukherjee, S. Shah, T. Religa, C. C. Teodoro Mendes, S. Bubeck, F. Koushanfar, and D. Dey, "Litetransformerseacch" Training-frre neural architecture search for efficient language models," Advances in Neural Information Processing Systems, vol. 35, pp. 24 24 267, 2022.
[18] I. Fedorov, R. Matas, H. Tann, C. Zhou, M. Mattina, and P. Whatmough, "Ude: Unified dnas for compressible tinyml models for neural processing units," Advances in Neural Information Processing Systems, vol. 35, pp. 18 456 18 471, 2022.
[19] X. Wang, W. Guo, J. Su, X. Yang, and J. Yan, "Zarts: On zero-order optimization for neural architecture search," in Advances in Neural Information Processing Systems, S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35, Curran Associates, Inc., 2022, pp. 12 828-188800 880.
[20] N. Lee, T. Ajanthan, and P. Torr. "Snip: Single-shot network pruning based on connection sensitivity," in International Conference on Learning Representations, 2019.
[21] C. Wang. G. Zhang, and Grosse, "Picking winning tickets before training by preserving gradient flow," in International Conference on Learning Representations, 2020.
[22] H. Tanaka, D. Kunin, D. L. Yamins, and S. Ganguli, "Pruning neural networks without any data by iteratively conserving synaptic flow," Advances in Neural Information Processing Systems, vol. 33, pp. 6377-6389, 2020.
[23] J. Turner E. J. Crowley, M. O' O'Boyle, A. Storkey, and G. Gray, "Blockswap: Fisher- Fisher-guided block substitution for network compression on a budget," in International Conference on Learning Representations, 2020.
[24] W. Chen, X. Gong, and Z. Wang, "Neural architecture search imagenet in four gpu hours: A theoretically inspired perspective," in International Conference on Learning Representations (ICLR), 2021.
[25] Y. Shu, Z. Dai, Z. Wu, and B. K. H. Low, "Unifying and boosting gradient-based training-free free neural architecture search," in Advances in Neural Information Processing Systems, A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, Eds., 2022.
[26] 7. Zhu, F. Liu, G. Chrysos, and Cevher, "Generalization properties of nas under activation and skip connection search," Advances in Neural Information Processing Systems, vol. 35, pp. 23 13551122 565, 2022.
[27] M. Lin, P. Wang, Z. Sun, H. Chen, X. Sun, Q. Qian, Li, and R. Jin, "Zen-nas: A zero-shot nas for perf-peeformance image recognition," in Proceedings of the IEEF/CVF International Conference on Computer Vision, 2021, pp. 347-356.
[28] A. Jacot, F. Gabriel, and C. Hongler, "Neural tangent kemel: Convergence and generalization in neural networks," Advances in neural information processing systems, vol. 31, 2018.
[29] S. Arora, S. S. Du, W. Hu, Z. Li, R. R. Salakhutdinov, and R. Wang, "On exact computation with an infinitely wide neural net,"' Advances in neural information processing systems, vol. 32, 2019.
[30] Lee, L. Xiao. S. Schoenholz, Y. Bahri, R. Novak, J. Sohi-Dickstein, and Pennington, "Wide neural networks of any depth evolve as linear models under gradient descent," Advances in neural information processing systems, vol. 32, 2019.
[31] S. Du, X. Zhai, Poezos, and Singh, "Gradient descent provably optimizes over- parameterized neural networks," in International Conference on Learning Representations, 2019.
[32] B. Hanin and M. Nica, "Finite depth and width corrections to the neural tangent kernel," in International Conference Learning Representations, 2020.
12

---

[33] S. Du, J. Lee, H. Li, L. Wang, and X. Zhai, "Gradient descent finds global minima of deep neural networks," " in International conference on machine learning. PMLR, 2019, pp. 1675-1685.
[34] D. Zou and Q. Gu, "An improved analysis training over wvrrpaaaaetteriee deep neural networks," Advances in neural information processing systems, vol. 32, 2019.
[35] Q. N. Nguyen and M. Mondelli, "Global convergence of deep networks with wide layer followed by pyramidal topology," Advances in Neural Information Processing Systems, vol. 33, pp. 11 961-11 972, 2020.
[36] N. Lee, T. Ajanthan, Gould, and H. S. Torr, "A signal propagation perspective for pruning neural networks at initialization." in International Conference on Learning Representations, 2020. [Online]. Available: http://onnneeeivvvee//ommmnnnnno
[37] K. Bhardwaj. G. Li, and R. Marculescu, "How does topology influence gradient propagation and model performance of deep networks with densenet-type skip connections?" in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 13 498- 13 507.
[38] H. Li, Z. Xu, G. Taylor, C. Studer, and T. Goldstein, "Visualizing the loss landscape of neural nets," Advances in neural information processing systems, vol. 31, 2018.
[39] R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university press, 2012.
[40] Y. Cao and Q Gu, "Generalization bounds of stochastic gradient descent for wide and deep
neural networks," Advances in neural information processing systems, vol. 32, 2019.
[41] X. Dong and Y. Yang. "Nas-bench- 2011: Extending the scope of reproducible neural architecture search," in International Conference on Learning Representations, 2020.
[42] X. Dong, I.. Liu, K. Musial, and B. Gabrys, "Nats:bench: Benchmarking nas algorithms for architecture topology and size," IEEE transactions on pattern analysis and machine intelligence, 2021.
[43] A. Krizhevsky, G. Hinton et al., "Learning multiple layers of features from tiny images." Toronto, ON, Canada, 2009.
[44] P. Chrabaszez, I. Loshchilov, and F. Hutter, "A downsampled variant of imagenet an alternative to the cifar datasets," arXiv preprint arXiv: /et::00777933 2017.
[45] A. R. Zamir, A. Sax, W. Shen, J. Guibas, J. Malik, and S. Savarese, "Taskonomy: Disentan- gling task transfer learning." " in Proceedings of the IEEE conference on computer vision and pattern recognition, 2018, pp. 3712-3722.
[46] A. Zela, J. N. Siems, L. Zimmer, J. Lukasik, M. Keuper, and F. Hutter, "Surrogate nas bench- marks: Going beyond the limited search spaces of tabular nas benchmarks," in International Conference on Learning Representations, 2022.
[47] Y. Duan, X. Chen, H. Xu, Z. Chen, X. Liang, T. Zhang, and Z. Li, "Transnas-bench- 101: Improving transferability and generalizability of cross-task neural architecture search," " in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2021, pp. 5251-5260.
[48] C. Ying, A. Klein, F. Christiansen, E. Real, K. Murphy, and F. Hutter, "Nas-bench- 101: Towards reproducible neural architecture search," in International Conference on Machine Learning. PMLR, 2019, pp. 7105-7114.
[49] M. Chen, H. Peng. J. Fu, and H. Ling, "Autoformer: Searching transformers for visual recogni- tion," " in Proceedings of the IEEE/CVF international conference on computer vision, 2021, pp. 12 270-12 280.
[50] H. Cai, C. Gan, T. Wang, Z. Zhang, and S. Han, "Once-for-all: Train one network and specialize for efficient deployment," in International Conference on Learning Representations, 2020. [Online]. Available: http://pwwwwvoooooo/o//omm/t///a
13

---

[51] J. Xu, L. Zhao, J. Lin, R. Gao, X. Sun, and H. Yang, "Knas: green neural architecture search," in International Conference on Machine Learning. PMLR, 2021, pp. 11 613-11 625.
[52] Y. Shu, S. Cai, Z. Dai, B. C. Ooi, and B. K. H. Low, "NASI: Label- and data-agnostic neural architecture search initialization," in International Conference Learning Representations, 2022. [Online]. Available: https///peenevvee.neeffoom www.e//oooommmd.ioooo//NN
[53] Z. Zhang and Z. Jia, "Gradsign: Model performance inference with theoretical insights," in International Conference on Learning Representations, 2022. [Online]. Available:
[54] A. Howard, M. Sandler, G. Chu, L.-C. Chen, B. Chen, M. Tan, W. Wang. Y. Zhu, R. Pang, V. Vasudevan et al., "SSarching for mobilenetv3," in Proceedings of the IEEE/CVF international conference on computer vision, 2019, pp. 1314-1324.
[55] L. Xiang, L. Dudziak, M. S. Abdelfattah, T. Chau, N. Lane, and H. Wen, "Zero-cost proxies meet differentiable architecture search," arXiv preprint arXiv:2106.06799 2021.
[56] E. Real, A. Aggarwal, Y. Huang, and Q. V. Le, "Regularized evolution for image classifier architecture search," in Proceedings of the aaai conference on artificial intelligence, vol. 33, no. 01, 2019, pp. 4780-4789.
[57] C. Liu, B. Zoph, M. Neumann, J. Shlens, W. Hua, L.-J. Fei-Fei, A. Yuille, Huang, and K. Murphy, "Progressive neural architecture search," in Proceedings of the European conference on computer vision (ECCV), 2018, pp. 19-34.
[58] R. Wang, M. Cheng. X. Chen, X. Tang, and C.-J. Hsieh, "Rethinking architecture selection in differentiable nas," " in International Conference on Learning Representation, 2021.
[59] X. Chen and C.-J. Hsieh, "Stabilizing differentiable architecture search via perturbation- regularization," in International conference on machine learning. PMLR, 2020, pp. 1554-1565.
[60] G. Li, G. Qian, I. C. Delgadillo, M. Muller, A. Thabet, and B. Ghanem, "Sgas: Sequential greedy architecture search," in Proceedings of the IEEF/CVE Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
[61] W. Hoeffding, "Probability inequalities for sums of bounded random variables," The collected works of Wassily Hoeffding, pp. 409-426, 1994.
[62] G. H. Golub and C. F. Van Loan, Matrix computations. JHU press, 2013.
[63] Y. Xu, L. Xie, X. Zhang, X. Chen, G.-J. Qi, Q. Tian, and H. Xiong, "Pe-darts: Partial channel connections for memory-efficien architecture search," in International Conference Learning Representations, 2020.
[64] X. Chen, L. Xie, J. Wu, and Q. Tian, "Progressive differentiable architecture search: Bridging the depth gap between search and evaluation," in Proceedings of the IEEE/CVF international conference on computer vision, 2019, pp. 1294-1303.
[65] G. Huang, Z. Liu, L. Van Der Maaten, and K. Q Weinberger, "Densely connected convolutional networks," " in Proceedings of the IEEE conference on computer vision and pattern recognition, 2017, pp. 4700-4708.
[66] S. Xie, Zheng, C. Liu, and L. Lin, "SNAS: stochastic neural architecture search." in Interna- tional Conference on Learning Representations, 2019.
[67] A. Zela. T. Elsken, T. Saikia, Y. Marrakchi, T. Brox, and F. Hutter, "Understanding and robustify- ing differentiable architecture search," in International Conference on Learning Representations, 2020.
[68] Ye, B. Li. Y. Li. T. Chen, J. Fan, and W. Ouyang, "3-darts: Beta-decay regularization for differentiable architecture search," in 2022 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR). IEEE, 2022, pp. 10 804-10
14

---

A Detailed proofs
A.1 Proof of Theorem
In this section, we present the proof for our main theorem (Theorem 2 in Section 3.4). We first introduce the following definitions and lemmas to better illustrate our proof.
2 ( log log (g)). then with probability at least - ô, [[H(O) H S 2 and 1u S Amin (H(()) Ao
Lemma 1 (Lemma 3.1 in 31). If m
Definition 4. We denote the empirical indicator matrix as (()) with entry (W(0) such that
m (w) 2 (0)x, 2 0}
[W == m
and indicator matrix as W with entry [Wi
W by = Ew-N [[w"x; 20, w 2 03]
The indicator matrix W has the following property. Proposition 1. If x; X X3, then [W]i > 0.
Proof. If Proposition 1 does not hold, then Rio. [n]] x [n], satisfying
W Wioso
N [T TT X 2 0, wT x 2 0H}
= =P =w (w? X1o 0, w. T 2 0)
(w
Thus X = -jo which contradicts the hypothesis Xio i Xjo-
In real-world datasets, the possibility of two different data being parallel is slight. Thus, proposition T holds in general. We further introduce Weyl inequality as follows:
Lemma 2 (Weyl inequality (391). Let E Raxn be Hermitian matrices, and let the eigenvalues of A, B. and A+B be (A(A)) (B b and (A)B))] respectively. The eigenvalues of each matrix are arranged in ascending order. Then we have
A:(A + B) & (A) + An-;(B), j= 1..,,...,
(14)
for each = I,... with equality for some pair i, if and only if there is nonzero vector such that Ax Aiti (A)x, Bx (B)x, and (A + B)x A; B)x. Also,
+ (A)
S A(A+B), B), j=
(15)
for each ,,...,,,, with equality for some pair i, if and only if there is nonzero vector such that Ax = (A)x, Bx = >3 B xx and (A + B)x = (, + B)x. If A and B have no common eigenvector, then inequality 14 and are strict inequality.
Now, we provide the full proof of Theorem 2.
Theorem 2. Suppose f is an NN with a single hidden layer and ReLU activation function. Assume X _d (0) ~ (O, I), P(X) 0, Po == Amin (P(X)), and hidden nodes m Ω then the following formula holds with probability least 8 over the initialization
n
5
(W), a, X) y11 < exp exp(-cpot)](((()) a. 21
where is constant depending and d.
15

---

Proof. To simplify our proof, we assume = 0, 0x 1, and | S C for all x E X. Recall that
m [w: 2 0, (0) 2 03 x (W)))
H(O); = x x3 m
Due to [[ (0)x; 2 0, w (0)xy 2 0} an independent random variable between 0 and 1, then by Hoeffding's s inequality [61]. the following inequality holds with probability 1 - 8:
2 log (1/6) v m
[w 2 [W
Let μo = (e) (Wy and choose m
16 (1/6) HB
then we have
2olog (1/5)
2 2olog (1/6)
[W0)) 2 Na
c(m)
vm
Vm
Define the matrix M with entry MM as
MM,y == [H()); c(m, -mm,,mmm(m)))))) d))(())
where c(m, d) = cd - 1). We claim that if m is large enough, then M is positive definite. To clarify this statement, we consider the gap between (0) and M:
[(())
M| |e(m, d) P(X) S c(m,,)))P(X)II d)?22
6-1 6o (d=""("=)))"
we choose m
we have
X8
A 4
H(0)- M S
Then the following formula holds by matrix perturbation theory (Corollary 6.3.8 in
Ao 2
Ao
0
Amin (H())=
Amin (M)
which indicates that M is positive definite. We next exert Lemma 2 on M and get
0 < mmi (H(0) - c(m, d))(X)) < Amiu (H(O)) Amiu Amiu(c(m d)P(X))
That means
0 << c(m, d)po S Amin (H())) - Ao
(16)
4
Therefore, combined with Theorem we have
[l X) - y1
S exp <xxp(-Aot)]((((()))) X) yyl?
[exp(=cdm..dpod))l([// aX y
where c(m, d) is constant depending and d. This completes the proof of Theorem 2.
16

---

A.2 Proof of Theorem 3
Proof. By Corollary 3.10 and Remark 3.11
we have
yy (H
log(118)
B[L(W) 50 c.
+0
N
According to the courant minimax principle
62
D.2 in 22
and inequality I6
we get
y y
y y
Amin
H 20
po
Thus, we have
y (H))
(v @(V
y
log log(1/8)
B(L(W) 50 c.
N
y"y Npu
+0
0O
c.
B Zero-cost proxies
In this section, we provide the details of the baseline zero-cost proxies. Suppose L is the loss function and is the parameters an initialized network. We denote as the Hadamard product. The concrete formulations of the existing zero-cost proxies are as follows.
snip. Lee et al. 20 use the changes in loss caused by the parameter perturbations to measure the importance the parameters an initialized network, such that
0L 00
Snip (0)
grasp. Wang et (21 replace the loss change in snip with the change of the gradient norm to establish the proxy, such that
öL 00 о
Sgrasp() ((
where H is the Hessian.
synflow. To avoid layer collapse, Tanaka et al. (2 utilize the product of all parameters in the network during the parameter perturbation to represent the loss, such that
äL
Saynflow (0)
00
grad _orm_ Abdelfattah et al. 8 adopt the l2 norm of the gradients in an initialized work proxy, such that
0L
Sgrad norm
00
jacov/NWOT. Mellor et 7 use the correlation of activations within network proxy to evaluate the performance of the network, such that
17

---

Na dn(
NA du (c1, CN)
Sjacov = log [ K =
Na dx(c,,
NA du (cN. CN)
where NA is the number rectified linear units, du (Ci, cj) represents the Hamming distance between two binary codes e; and Cj-
NTK. Chen et al. 24 propose to use the condition number of NTK to measure the
trainability of the networks, such that
Amax (Qreein)
KN
Amin train))
where Orannn stands for NTK of the networks. In our paper, we calculate the Spearman correlation coefficient between 1/KN and the test accuracy of the networks.
zen. Lin et al. 27 propose Zen-Score, in which they design an efficient zero-cost proxy with Gaussian random inputs, such that
Σ log ( [
Szen log (Exx (1xx - f(x + 0)(r))
where oij is the inini-batcl standard deviation statistic of the j-th channel in BN.
NASI. Shu et al. [52) propose NASI to evaluate the networks by approximating the trace of the NTK, such that
NASI my-1 b-
Loo
xEX,,
where X2 is mini-batch of data with size |2,]] b.
KNAS. Xu et al. [51] propose to use gradient kernel to evaluate the networks, such that
(t) Öw(()
(Ott()) T Ow(t)
g
where y² is the output of L-tth layer.
GradSign. Zhang and Jia [53 propose GradSign, which they analyze the sample-wise optimization landscape of the networks, such that
GradSign Σ Σ
ZiCo. Liet al. [9 explore the effect of gradient properties network performance. They use absolute mean and standard deviation values gradients to evaluate network performance:
ZiCo Σ log
i [N]
where N and D represent the number of batches and network layers, respectively. 0 represents the parameters of the 1-th layers.
18

---

C Algorithm of MeCo-based NAS
We slightly abuse the notation and denote MeCo as proxy function for the network. We adopt the Zero-Cost-PT [55 to integrate MeCo to a zero-shot NAS. The algorithm of our MeCoobased NAS is summarized in Algorithm [ We denote Ag edge, which stands for mixed operation
untrained supernet, represents the t-th the search cells, and Ct,K is the k-th operation of f-th edge. We denote &, .V, and O as the of edges, nodes, and candidate operations in the search cells, respectively. For any node n E N, we use (m) as the set of its input edges, and ex is the k-th element of (1)). Note that can other zero-cost proxies described in section replace MeCo in Algorithm
Algorithm 1 MeCo-based NAS
Require: Ag: An untrained supernet: &: The set of edges in search cells; W/ The set of nodes in search cells; O; The set of candidate operations; N: the number of candidate networks.
Ensure: The best network Abest-
1: // Stage I: Architecture Proposal
2: C'= C= 0;
3: for -: + (
4:
for j=
5:
Randomly choose an un-discretized edge Choose the best edge from the supernet, s.t.
6:
E best
arg min MeCo(Ao/ee, 1gk$|0
7:
Use operation Ctabest to substitute Ct
8:
end for
9:
A consists of (er, 1 S S |&|}
10:
for j = 1; < [W j + do Randomly select unselected node E N
b prune the edges of the obtained architecture Alej
12:
do Calculate MeCo the architecture //g end for
for = 1; < [[(n]]
13:
14:
15:
Retain edges e, ea with the 1st and 2nd best MeCo value, and remove the other edges 16: end for
17: Get the candidate networks A, that consist of {Cr,best |1 I S 8). and append it to the set C
18: end for
19: // Stage 2: Architecture Validation
20: Get the best network:
Abest arg max MeCo(Ai), s.t. A₁ E C
I9KS
D Experimental configurations
We use the same settings for the experiments in 155 We summarized the configurations of the searching phase and training phase on CIFAR-10 and CIFAR- 100 in Table/oland Table respectively. For ZiCo, we use two mini-batch of data, which has size 64. For the other baseline proxies, we use one mini-hatch of data. On the other hand, our MeCo only uses one random data x E R 3133x32x32
E
More experimental results of
E.1 MeCo NASBench-201 and NASBench-301 with three extra datasets
We evaluate MeCo and MeCogpt on NASBench-20 and NASBench-301 with Spherical-CIFAR--I0 NinaPro, and SVHN, respectively. We only use one random data æ |3332x32 for MeCo and MeCoapt- The results are summarized in Table Our MeCo achieves competitive results most benchmarks and achieves the best results on NASBench--01-SVVNN where the Spearman correlation coefficient is 0.88.
19

---

Table 6: The settings of Zero-Cost-PT with all proxies in DARTS-CNN for CIFAR-10
Searching phase
Training phase
Settings
Baselines
MeCo (Ours)
Baselines
MeCo (Ours)
batch size
64
96
cutout
True
False
True
True
cutout length
16
learning rate
0.025
0.025
0.025
0.025
learning rate min
0.001
0.001
momentum
0.9
0.9
0.9
0.9
weight decay
3e-4
3e-4
3e-4
3e-4
grad clip init channels
5
5
5
16
16
36
36
layers drop path prob
8
8
20
20
0.2
0.2
Table 7: The settings of Zero-Cost-PT with all proxies in DARTS-CNT for CIFAR-100
Searching phase
Training phase
Settings
Baselines
MeCo (Ours)
Baselines
MeCo (Ours)
batch size
64
96
cutout
True
False
True
True
cutout length
16
16
learning rate
0.025
0.025
0.025
0.025
learning rate min
0.001
0.001
momentum
0.9
0.9
0.9
0.9
weight decay
3e-4
3e-4
3e-4
3e-4
grad clip init channels
5
5
5
16
16
16
layers drop path prob
8
8
20
20
0.2
0.2
Table Comparisons of p with baselines using NASBench-301 and NASBench-201 three extra datasets
NASBench--00
NASBench-201
Method
Sph-Cifarlie
NinaPro
SVHN
Sph-Cifar100
NinaPro
SVHN
grasp
0.13
0.04
0.18
-0.01
-0.01
0.62
fisher
0.00
-0.11
0.05
0.07
-0.38
0.71
grad_ norm
-0,00
-0.20
0.42
-0.08
-0.23
0.77
snip
-0.01
-0.10
0.38
-0.09
-0.28
0.76
synflow
0.05
-0.07
0.50
0.13
0.02
0.71
12_ 12_norm
0.12
-0.07
0.70
-0.00
0.02
0.67
#params
0.07
-0.07
0.70
-0.14
-0.11
0.72
zen
0.07
-0.09
0.68
0.23
0.15
0.18
jacov
0.08
0.13
-0.36
-0.41
0.29
0.67
nwot
0.05
0.02
0.64
-0.02
0.06
0.76
MeCo (Ours)
-0.05
-0.11
0.68
-0.23
0.02
0.88
MeCoogt (Ours)
0.03
0.12
0.68
20

---

CIFAR-10 (0.89)
CIFAR- (0.88)
oe (0.85)
80
40
40
Test
Test
Test
20
20
0-
60
80
20
00
20
MeCo
MeCo
MeCo
Performance NATS-Bench-TSS
CIFAR-10 (-0.80)
CIFAR-100 (-0.89)
ImageNNet16-121 (-0.88)
50
90
70
60
Test
85
Test
50
Test
40
20
McCo
MeCo
MeCo
(b) Performance on NATS-Bench-SSS Bench-SSS
Figure 4: Relationship between our zero-cost proxies and test accuracy for WAT'S-Bench-TSS and NATS-Bench-SSS three datasets.
E.2 MeCo NAS-Bench-101
We present the Spearman correlation coefficient between all zero-cost proxies and the test accuracy of the networks in NAS-Bench-101. Our MeCo uses one data of CIFAR-10, i.c., E R 11xx332x32 while the baselines adopt a batch of samples as input. The results are summarized Table
Table Spearman correlation coefficients p between zero-cost proxies and test accuracy on NAS- Bench-101
Baselines
Dataset
MeCo
grasp 21
fisher
grad_norm norm S
snip
synflow
jacov 2
zen 27
ZiCo
9
CIFAR-10
0.44
-0.33
-0.27
-0.32
-0.25
0.36
-0.35
0.63
0.63
MeCo achieves competitive results NAS Bene--Benhh---eeee 101 with CIFAR-10 10. i.e., the Spearman correlation coefficient obtains 0.44, which is higher than the majority the baselines. However, zen and ZiCo perform better than MeCo.
E.3 MeCo TransBench-101
We further evaluate our MeCo on diverse tasks. Specifically, we compare MeCo and the other proxies Transhench-101-Wir and Transhench-101-Macre 47 respectively.
TransBench-10l-MMiicn We evaluate MeCo and MeCoopt on TransBench-101 101-Micro with ten tasks. We calculate the Spearman correlation between our proxies and the accuracy of the networks. The results are summarized in Table [0, MeCo achieves the best performance on the three tasks, i.c., Class Objection, Spherical-Cifart TOO, and NinaPro, which are 0.58, 0.85, and 0.47, respectively. It can seen that MeCoopt effectively improves the performance MeCo. For example, MeCoopt improves MeCo from 0.62 0.77 segmentation tasks.
Trans -ac-o. We compare MeCo, MeCoopt and baselines on TransBench- Maatnchh-01-MMPP 00--Mocro with seven tasks. The results are summarized in Table [T] Our proxies achieve the best performance on Autoencoding, Jigsaw, and Surface Normal, which are 0.74, 0.48, and 0.80, respectively. Our proxies also achieve competitive results on the remaining tasks. Experimental results show that
21

---

our proxies can be used for diverse tasks. It can be demonstrated that MeCo and MeCo become ineffective on few tasks, such Room Layout. We would like note that the existing proxies do not achieve high correlation on all tasks consistently.
Table 10: Comparisons of p with basclines using Transbench- Cactbbenchh-------- Mic- on Ten Tasks
Appronch
Antoenending
Class Objection
Scene Classification
Jigsaw
Surface Normal
Segmantation
Room Layout
Spherical -Clfar 100
NinaPro
SVHN
graup
fisher
.0.58
0.44
4.133
0.16
0.12
0.30
0.72
0.42
0.81
grad grad_nomm norm
-0.32
0.39
40.33
0.36
0.36
0.60
0.25
0.72
0.40
0.78
snip
0.45
synllow
12_ norm
0.04
0.32
0.28
0.35
0.50
0.48
0.18
0.53
0.36
0.52
Apurams
-0.01
0145
0.32
0.44
0.62
0.68
0.300
0.79
0.36
0.76
Jucov
0.18
0.51
0.19
0.75
0,40
0.40
0.77
Dwot
0.03
0.39
0.89
0.42
0.57
0.53
0.25
0.64
0.38
0.63
0.35
0,71
0.68
(Ours)
MeCouy (Ours)
0.03
0.55
0.64
0.47
0.67
0.77
0.26
0.85
0.47
0.88
Table 11: Comparisons of p with baselines using Transbench- 101-Macro Seven Tasks
Class Objection
Scene
Surface Normal
Room
Approach
Autoencoding
Jigsaw
Segmantation
Classification
Layout
grasp
-0.02
-0.64
-0.43
-0.26
-0.05
-0.02
-0.26
fisher
-0.19
-0.30
-0.13
-0.26
0.15
0.03
-0.26
grad_norm norm
0.31
-0.56
-0.33
-0.27
0.35
0.21
-0.27
snip
0.20
-0.38
-0.14
-0.19
0.45
0.27
-0.19
synflow
0.00
0.12
0.27
0.34
0.00
0.00
0,34
n2rn
-0.20
0.08
0.28
0.15
0.30
0.18
0.15
fparams
-0.18
0.16
0.32
0.15
0.30
0.06
0.15
zen
-0.01
0.10
0.27
0.24
0.38
0.27
0,24
jacov
0.45
0.07
0.19
0.19
0.50
0.57
0.19
nwot
0.67
0.83
0.89
0.48
0.78
0.80
0.76
MeCo (Ours)
0.51
0.59
0.81
0.17
0.80
0.62
0.23
MeCogpt (Ours)
0.74
0.73
0.76
0.48
0.76
0.63
0.33
E.4
MeCo AutoFormer and MobileNet OFA
AutoFormer. Chen et al. 49 proposed a novel one-shot architecture search framework for transformer-based models. We load the trained supernets and regenerate the candidate subnets. We then re-evaluate the subnets to obtain the accuracy on ImageNet and compute MeCo. The correlation of MeCo and model accuracy on AutoFormer is 0.45.
OFA. To solve the problem of efficient inference across devices and resource constraints, Cai et al. 50 proposed to train once-for-all (OFA) network, which supports diverse architectural settings. We randomly sample 1,000 subnets from the OFA network and use the accuracy of the predictor predictions as the test accuracy. The Spearman correlation between MeCo and test accuracy 0.86.
F More experimental results of NAS with MeCo
In this section, provide more results and comparisons of zero-shot NAS NATS-Bench-TSS, and DARTS-CNN. In the following descriptions, we denote multi-shot, one-shot, and zero-shot as MS, OS, and 7.S, respectively.
F.1 Results on NATS-Bench-TSS
In the AXTS-Bench search space, we evaluate all networks using zero-cost proxies and choose the Top- networks with the highest scores. Then we calculate the average test accuracy and standard deviation. The results are summarized in Table T2 As shown in the table, the networks searched by MeCo have the highest average precision on CIFAR-IO, which 0.08 higher than the best bascline proxy ZiCo. For CIFAR- 100 and ImageNet16- 1200, MeCo achieves competitive results,
22

---

e.g., 70.86% + 0.96% with CIFAR- 100 and 42.59% 1.77% with ImageNer16-1200 In all, the results demonstrate that our MeCo has a great advantage in evaluating network performance, considering MeCo only requires one data sample as input.
We further combine MeCo with Zero-Cost-Pi with different seeds. The accuracy of the selected architectures as well as the comparisons with the baseline methods are presented in Table 13
5 and search for the best architecture three times
be shown from the results that our MeCo-based
NAS achieves competitive results with the SOTA baselines, e.g., synflow, zen, and ZiCo. However, MeCo-bas based NAS invokes one data for single forward pass, thus being more resource- resource-saving.
Table 12: The average test accuracy of Top- architectures obtained by various zero-cost proxies on NATS-Bench- -SS using CIAFR-10 10, CIAFR- 100, and ImageNet16- 120, respectively
Baselines
Datasct
MeCo
grasp
fisher
grad_norm
snip 20
synflow
jacoy 7
NTK(24
zen
ZiCo
CIFAR-10
93.64
-0.31
89.34
+2.16
-2.10
89.27
89.27
89.27
+2.10
93.27
+0.74
91.21
92.67
+0.48
58.99
+3.44
93.56
CIFAR-100
70.86
20.96
60.80
61.06
60.89
60.89
71.12
68.50
60.31
11.33
12.73
70.64
1m1geNet16-120
42.59
22.99
24.10
23.35
23.35
42.65
40.39
39.98
15.10
42.74
=1.77
=11.66
+11.4
20.51
Table 13: The test accuracy of optimal architectures obtained by Zero-Cost-PT with various zero-cost proxies NATS-Bench-TSS. using CIAFR-10, CIFAR-I00, and ImageNet16-120, respectively
Baselines
Datasct
MeCo
grasp 21
fisher 23
grad_norm boormB g
snip 20
synflow
22
jacov 7
NTK24
zen
27
2:Co
93.76
92.59
88.39
91.61
91.92
92.61
93.76
CIFAR-10
+0
+1.12
+2.05
+0.08
#2.85
=0
+-2.0
+0.65
+00
+:
CIFAR-100
71.11
68.98
66.77
65.20
65.29
71.11
69.67
68.27
71.11
71.11
100
42.80
1.0.9
4..56
40.96
=0
4.2.39
42,34
1.0
1.0
1mageNet16-120
41.44
35.29
28.91
35.82
37.38
41.44
40.35
41.25
41.44
41.44
:10
18.33
13.18
13.99
#4.11
=0
1:6.56
42.37
100
1:0
F.2 Results on DARTS-CNN
For DARTS-CNN search space, search the architectures by Zero-Cost-PT with different zero-cost proxies on CIFAR-100 100. Each searched network is trained five times, and the results are summarized
in Table 14 There two settings in experiments DARTS-CNE networks initialized with 16 channels and trained as in Table 7 and networks initialized with 36 channels and trained as in [63]. can be shown from Table 14 that MeCo achieves competitive results compared with MS, OS, and ZS baselines. More concretely, MeCo-based NAS obtains 19.33% test error with 0.08 GPU days, which outperforms all the ZS methods under the same settings. On the other hand, compared with the manual, MS, and OS methods, MeCo also competitive. For example, MeCo-based NAS achieves 83.14% accuracy, which is only 0.34% lower than the bascline method 3-DARTS (64, but five times more efficient computation.
We further visualize the networks searched by Zero-Cost-PTT with different proxies on DARTS-CNE The results on CIFAR-I0 and CIFAR- 100 are presented in Figure 6 and Figure 7 respectively.
F33 Results on MobileNet V3
We search the architectures on MobileNet space using Algorithm 1 using ImageNet- for 480 epochs with batch size of 256 and input resolution 224 224. The results are summarized in Table 15 MeCo achieves 77.8% Top-1 accuracy. which 0.7% higher than the SOTA baseline method ZiCo. Moreover, method only takes 0.04 GPU days, which outperforms the SOTA methods.
We retrain the searched network
G Limitations and future works
23

---

Table 14: Comparison of our method with SOTA NAS methods using DARTS-CNN and CIFAR-IO0
Test Error
Search Cost
Params (MB)
Approach
Method
(%)
(GPU Days)
DenseNet-BC 6C 17.18
25.6
Manual
NASNet-A D
16.82
2000
3.3
MS
17.76
1.5
3.3
OS
SNAS 166
17.55
1.5
2.8
OS
P-DARTSI 64
15.92 + 0.18
0.4
3.7
OS
R-DARTS
18.01 + 0.26
OS
PC-DARTS
16.9
0.1
3.6
OS
3-DARTS
16.52 + 0.03
0.4
3.83 + 0.08
OS
Zero-Cost-PP synflow
22
19.82 + 0.35
0.04
1.2
ZS
Zero-Cost-PTT fisher
21.14 0.24
0.06
0.7
ZS
Zero-Cost-PTT
21
22.65 + 0.30
0.13
0.7
7S
grasp
Zero-Cost-PT jacov
22.90 + 0.35
0.04
0.6
ZS
Zero-Cost-PT snip
20
19.95 + 0.28
0.04
0.8
ZS
Zero-Cost-PTT NTK
20.30 + 0.33
0.19
0.9
ZS
Zero-Cost-PTTze ZiCo!
19.54 + 0.28
0.06
1.1
ZS
Zero-Cost-PT MeCo
19.33 + 0.25
0.08
0.8
ZS
Corr--ost-PPT..... MeCo
16.86 + 0.30
0.08
3.7
ZS
networks initialized with channels and trained settings in c networks initialized with 36 channels and trained as settings in
63
Table 15: Comparison of method with SOTA NAS methods using MobileNet and ImageNet- IK.
Top-1 (%)
Search Cost
Params
Approach
Method
(GPU Days)
(M)
MobileNet-V3(1.00
75.2
288
5.3
MS
PNAS
74.2
224
5.1
MS
DARTS
73.3
4.7
OS
PC-DARTS
75.8
3.8
OS
SPOS
74.7
8.3
OS
GreedyNAS
74.9
7.6
3.8
OS
TE-NAS
75.5
0.17
5.4
ZS
ZiCo
77.1
0.4
ZS
Zero-Cost-PT
76.4
0.04
ZS
Zen-score
76.1
0.5
ZS
MeCo (Ours)
77.8
0.08
7.9
Z.S
24

---

Finally, we demonstrate the limitations of this work and the possible directions of our future
NATSSBBecch-Te BSS-chnnh--SSS
NATS-Bench-SSS
0.9
-0.78
work. In Section 5 We propose optimization
0.89
method alleviate the channel-sensitive issue
0.88
00.8
0.84
of MeCo. This weight-sampling approach can
0.85
be further improved future work. Moreover,
0.84
-0.88
we would like to point out that the evaluation of a zero-cost proxy often tied to the availabil- ity of benchmarks. Hench though the proxies are "zero cost", the evaluation of the proxies is strongly dependent
0.85
3
3
Samples
Saaplls
CIFAR-I0: 10:
CIFAR- 100:
ImageNet 1--1
benchmark, which in the first place is very expensive to create. Finally, although MeCo achieves the highest correlation with the test accuracy on multiple benchmarks, few tasks
Figure 5: Spearman correlation coefficients of
it shows near zero correlations (e.g., TransBench- 101-Micro with Autoencod- ing), We will leave these issues our future
MeCo with different number of samples on NATS- Bench-TSS and HATS-Bench-SS respectively.
work.
25

---

3:5
comy 516
Sea [o__smm_300 566
O0T 545
Normal Cell
Reduction Cell
(a) synflow
200 eug poel 3el
skpp FOC
50p con.
598 Dory 3d
max pool
CO 5A5
Oolyonryyy.o 36
Normal Cell
Reduction Cell
(b) fisher
di
Scp conk 545
24g
24g cont 355
K
5:0 contect
con 36
50 c0n 30
909 C0N 345
5ep 345
Normal Cell
Reduction Cell
(c) snip
rop_conv_555
sap ANPLIONN
2-g pool
SAO COW. 200
0
podl 36]
Normal Cell
Reduction Cell
(d) grasp
omyy 3el
max
4 Loco 306
max pol
s80_pomv 36
con 30
cory 30
Normal Cell
Reduction Cell
jacov
Sep. con 3x3 Loom_
5op
200 _00
@sp_com__33
163
Reduction Cell
Normal Cell
(I) NTK
#80L.om 3x SAaL Mancco
9e3_ooy_5d
36)
Sea cory 5:5
0007 545
Normal Cell
Reduction Cell
(g) ZiCo
26

---

$00 o00r 56
dl Lon,, 36
dL 545
000 2w., 30
50g, concoO 5k5
95 200roryy 36
Normal Cell
Reduction Cell
(h) MeCo
Figure 6: Cells found by Zero-Cost-PT with all zero-cost proxies on the DARTS- -ART search space using CIFAR-10
cony 565
359 cony 5:5
303 mom,mmyy 36
Dmy 565
Normal Cell
Reduction Cell
(a) synflow
eep mayy Tel
muc par 3a3y
can
E [:0
poLp 5s3
Reduction Cell
Normal Cell
(b) fisher
550 c0ny 3:
connect
akgp cornect
Sop www.
505
con 363
shlp connect
skppjomnes
www. 5x5
Normal Cel
Reduction Cell
(c) snip
peo_
cony 3G
WnL pio 363
con. 363
conw 363 sep CONN 300
16
eop 2017 33
1000
PAO 3k3
DWV 30
Normal Cell
Reduction Cell
(d) grasp
dil conw 5k5 300, oolyooyyy 5.5
poot 36)
513
di conN 3x5
5
Normal Cell
Reduction Cell
(c) jacov
27

---

de 545
Lonn Su5
503 cony
corn 5a5
Day,
000
Normal Cell
Reduction Cell
(I) NTK
500 conv 345
500, zony S:5
Ma. Lamm
20__0m_333
969 2077 36
502 sam, 36
587_56
Normal Cell
Reduction Cell
g ZiCo
conn 3x3
305
sogy cone 1el
Normal Cell
Reduction Cell
(h) MeCo
Figure 7: Cells found by Zero-Cost-PT with all zero-cost proxies the DARTS C-NN search space using CIFAR-100
28


Reviews:
[{"review_id": "KVEd1nkCcs", "reviewer": "Reviewer_gqC1", "summary": "The paper proposes a new zero-cost proxy (called MeCo) for neural architecture search motivated by theoretical insights about the relationship of the statistics of Pearson Matrix and a network's convergence rate. The proposed proxy is evaluated by investigating ranking correlation on NATSBench-TSS, NATSBench-SSS, and NASBench101, as well as CIFAR1 dataset.", "questions": "My questions are aligned with the weakness sections\n- How could Meco be connected with the generalization capacity of the network?\n- Can the author show more results on diverse tasks beyond the image classification?\n- How does the number of input samples impact the performance of the MeCo?\n- Does MeCo generalize to other search spaces and large-scale datasets?\n- Can the author show the performance of the searched optimal network via MeCo on these benchmarks?\n- Why on SSS the correlation is negative while on TSS the correlation is positive? Based on the theoretical analysis (line 183, 184), it should be always positive.", "limitations": "Currently, the limitations are primarily the insufficient evaluation of different tasks and different search spaces. Also, some results are not clear in this paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- A novel zero-cost proxy for NAS grounded in theory is proposed\n- Good performance of the proposed method (although see below)", "weaknesses": "My concern primarily comes from the evaluation sections.\n- The author didn't show the experiments on large-scale datasets, such as ImageNet\n- The author didn't show the results on MobileNet-v2 like search space.\n- The author didn't show the performance on other types of NAS benchmarks that are beyond the image classification, e.g., TransNASBench101. \n\nI am also concerned about the theory part. \n- The author only discusses the convergence speed of the network. The generalization capacity of the network is not involved in the discussion.\n- The author shows contrasting results on TSS and SSS. \n\n\n\n\n\nMinor:\n- Typos: In line 220, the author claims that MeCo is 0.6-0.9 higher than ZiCo.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and valuable comments and suggestions! We would like to respond to your reviews point by point. \n\n**Q1: MeCo and generalization capacity:**\n\nAnswer: MeCo can also reflect the network generalization capacity. Specifically, we introduce the following theorem:\n\n**Theorem 3.** For an over-parameterized neural network, we denote the loss as $L(W)$. Let $y=(y_1, ..., y_N)^T$ ,  $\\lambda_0=\\lambda_{min}(H^{\\infty})$. Let $\\gamma$ be the step of SGD, $\\gamma = \\kappa C_1\\sqrt{y^T(H^\\infty)^{-1}y}/(m\\sqrt N)$ for some small enough absolute constant $\\kappa$. Under the assumption of Theorem 1,  for any $\\delta\\in(0,e^{-1}])$, there exists $m^\\ast(\\delta,N,\\lambda_0)$, such that if $m\\geq m^*$, then with probability at least $1-\\delta$, we have\n$$\nE[L(W)] \\leq O(C'\\sqrt{\\frac{y^T y}{p_0 N}})+ O(\\sqrt{\\frac{\\log(1/\\delta)}{N}})\n$$\nwhere $C, C', \\delta$ are constants. \nThe proof can be obtained from Corollary 3.10 of [1] and Section D.2 of [2]. Theorem 3 indicates that the generalization capacity is bounded by $p_0$. The expectation of the loss decreases when $p_0$ gets larger. This relationship is consistent with Theorem 2.\n\n**Q2: More results on diverse tasks:**\n\nAnswer: We conduct experiments on 10 tasks on TransBench-101-Micro and 7 tasks on Transbench-101-Macro to show the performance of MeCo. The results are shown in Tab 1 and 2 in the attached PDF. \n\nMeCo achieves the highest correlation on Surface Normal+Macro, Class Objection+Micro, SCifar-100+Micro, and NinaPro+Micro. MeCo also achieves competitive results on the majority of the remaining tasks. On some of the tasks, e.g., Autoencoding+Micro, MeCo only achieves 0.03 correlation. This might because the characteristics of the task per se, and the channel-sensitive trait of MeCo. Designing proxies that can be further generalized to more tasks is a promising direction. We would like to note that the existing proxies do not achieve a high correlation on all task consistently. \n\n**Q3: How does the #Samples impact the performance of MeCo?**\n\nAnswer: We add ablation experiments about #Samples v.s. MeCo performance. We randomly chose different #Samples to evaluate the architectures in the entire TSS and SSS, respectively. The results are shown in Fig 1 in the attached PDF. \n\nIt can be shown that MeCo is relatively stable when varying the #Samples. The correlation fluctuates around 0.01 throughout the experiments. These results support that MeCo only requires one data sample. \n\n**Q4: Does MeCo generalize to other search spaces and large-scale datasets?**\n\nAnswer: 1) We add experiments on NASBench-301, NASBench-201 (with extra three datasets), transformer benchmark AutoFormer, and MobileNet-like search space (OFA). The results are shown in Tab 3 in the attached PDF.\n\nOn the standard NASBench-301+CIFAR10 task, MeCo achieves the highest correlation with the model performance. On the three extra tasks, MeCo also obtains competitive results, e.g., 0.68 for SVHN, which is only 0.02 lower than SOTA baseline. \n\nWe follow the settings in NASBench-Zero-Suite and adopt MeCo on three extra datasets on NASBench-201. The results show on SVHN, MeCo is 0.11 higher than the best baseline.\n\n* MobileNet-like search space (OFA)\n\nWe follow the settings in OFA and utilize MeCo to evaluate the architectures. The correlation is **0.86**, which is relatively high. \n\n* Transformer search space (Autoformer)\n\nFor AutoFormer, we load the trained supernets and regenerate the candidate subnets. We then re-evaluate the subnets to obtain the accuracy and compute MeCo. The correlation of MeCo and model accuracy on AutoFormer is **0.45**.\n\n2）Large-scale datasets: We adopt MeCo-based NAS to ImageNet-1k on MobileNet-v2 search space. The results and comparisons are shown in Tab 4 in the attached PDF.\nWe trained the searched optimal network with six RTX 3090 for about 130 hours. The Top-1 accuracy is **77.3\\%**, which is higher than all the baseline approaches.\n\n**Q5: The searched optimal network:**\n\nAnswer: We provide the accuracy of the searched optimal networks on four benchmarks, i.e., TSS/SSS with CIFAR10/CIFAR100/ImageNet, Darts with CIFAR10/CIFAR100, and MobileNetv2 with ImageNet-1k.\nThe results of TSS/SSS/DARTS are shown in Tab 4, 5 in our paper, and Tab 4, 5, 6 in the appendix, with the visualized architecture structures in Fig 2. \nWe add the experiment of Mobilenet-v2 with ImageNet-1k, the results are presented in the answer of Q4. \n\n**Q6: Negative correlation on SSS:**\n\nAnswer: We have discussed this phenomenon in Section 4.2, p.7, ln. 235-246. More concretely, in our paper 3.2.3, we summarize that a multi-channel convolutional layer can be viewed as a multi-sample over-parameterized NN layer. This leads to the fact that MeCo is sensitive to #channels. The more channels contained, the larger the Pearson matrix, which will lead to SMALLER $p_0$. The simulated results in Fig 2 also validate this issue. On the other hand, larger #channels will normally lead to higher accuracy of the architectures (yet lower convergence rate). Thus, the variation of #channels in SSS  leads to the negative correlation on SSS. In TSS, however, all the networks share the same #channels at each stage, thus MeCo does not show negative correlation.\n\nWe would like to further point out that this phenomenon does not contradict our theoretical basis. In practice, various factors (e.g., #channels, #samples) may affect the network accuracy. Theorem 2 and 3 show the relationship between $p_0$ and the convergence rate/generalization capacity of the network, which has been proven to be effective in multiple benchmarks. \n\n[1] Cao Y, Gu Q. Generalization bounds of stochastic gradient descent for wide and deep neural networks[J]. Advances in neural information processing systems, 2019, 32.\n\n[2] Zhu Z, Liu F, Chrysos G, et al. Generalization properties of NAS under activation and skip connection search[J]. Advances in Neural Information Processing Systems, 2022, 35: 23551-23565."}, {"review_id": "loKpBKEQKM", "reviewer": "Reviewer_BGPn", "summary": "This paper introduce a new zero-cost proxy for NAS, called MeCo, which is fully independent of data and labels and requires only one data sample for a single forward pass. The paper provides a theoretical analysis of the relationship between the Pearson correlation matrix of the feature maps and the training convergence rate of the network. Meco shows high ranking correlation in NATS-Bench. ", "questions": "What are the advantages of Meco over #Param, besides the marginal improvements in ranking correlation? Is there a high correlation between Meco and #Param?\n\nHow does the correlation variation of Meco address the issue of fluctuation in ranking correlation seen in other zero-cost proxies? Can the robustness of Meco be demonstrated through providing the correlation variation?\n\nWhy does the paper claim to use NAS-Bench-101 but not provide the experimental results in the main body? Why was NAS-Bench-201, a widely-used benchmark in the NAS community, not utilized?\n\nCan Meco maintain computational efficiency when applied to larger networks with a large number of channels, considering the practical implications for neural networks?\n", "limitations": "I have concerns regarding the experimental aspects of the paper. During the rebuttal period, I hope the authors can address these concerns. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The authors theoretically reveal that the minimum eigenvalue of the correlation on the feature map is correlated with the training convergence rate. Based on this analysis, they propose Meco as a novel training-free proxy. Experiments conducted on NATS-Bench demonstrate the superiority of Meco for three small datasets.", "weaknesses": "1. As acknowledged by the authors, Meco is sensitive to variations in the number of channels, implying that Meco exhibits a similar preference as #Param when selecting an architecture from the search space. However, the paper lacks the ranking correlation of Param in Tab1 and Tab2, making it difficult to assess the correlation between Meco and Param. Besides the marginal improvements in ranking correlation, it would be beneficial to understand the advantages of Meco over Param.\n\n2. It is recommended to address the variation of correlation in Tab1 and Tab2. Many zero-cost proxies can experience fluctuations in ranking correlation when different batches with the same batch size are used. To showcase the robustness of Meco, providing the variation would be valuable.\n\n3. I have a question regarding the NAS-Benchmarks. The abstract states that NAS-Bench-101 is used in this paper; however, there are no experiments conducted on NAS-Bench-101 in the main body, only in the supplementary material. It is inappropriate to claim that experiments were performed on NB101 without presenting the results in the main body. Additionally, NAS-Bench-201 is a widely-used benchmark in the NAS community. I noticed that there are some files related to NB201 in the provided code. Why was NAS-Bench-201 not utilized?\n\n4. I noticed an inconsistency in the ranking correlation of NTK between Table3 (0.78) and Table1 (0.76). Please provide an explanation for this discrepancy.\n\n5. It should be noted that in recent years, there have been advancements in zero-shot proxies, including NASWOT, KNAS, NASI, and GradSign. However, this paper only focuses on older methods and does not consider these newer counterparts.\n\n6. I am curious about the computational efficiency of Meco when using `torch.corrcoef(fea)`. In practical neural networks, especially in later layers, the channel number can be quite large. Therefore, I am questioning whether Meco can be extended to larger networks with a large number of channels while maintaining computational efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and valuable comments and suggestions! We would like to respond to your reviews point by point.\n\n**Q1: What are the advantages of Meco over #Param, besides the marginal improvements in ranking correlation? Is there a high correlation between Meco and #Param?**\n\nAnswer: We demonstrate the performance of #Param on NATSBench-TSS and NATSBench-SSS as follows:\n\n* NATSBench-TSS:\n\n|| CIFAR-10 | CIFAR-100 | ImageNet16-120 |\n|-|-|-|-|\n| #Param| 0.72| 0.73| 0.69|\n| MeCo (Ours) | 0.89| 0.88| 0.85|\n\n* NATSBench-SSS:\n\n|| CIFAR-10 | CIFAR-100 | ImageNet16-120 |\n|-|-|-|-|\n| #Param| 0.72| 0.73| 0.84|\n| MeCo (Ours) | -0.80| -0.89| -0.88|\n\nMeCo is proved to be better than #Param on NATSBench-TSS and NATSBench-SSS benchmarks. We present the correlation between MeCo and #Param as follows:\n\n|| CIFAR-10 | CIFAR-100 | ImageNet16-120 |\n|-|-|-|-|\n| NATSBench-TSS| 0.83| 0.83| 0.85|\n| NATSBench-SSS| -0.72| -0.69| -0.68|\n\nMeCo shows a relatively strong correlation with #Param. Other than the higher correlation on various benchmarks, MeCo achieves much higher Top-1 accuracy than #Params on large-scaled datasets such as ImageNet-1k (77.3\\% v.s. 63.5\\% on MobileNet-v2). Finally, due to the theoretical basis of MeCo, we believe it can be further optimized and extended to a zero-shot NAS with better performance.\n\n\n**Q2: How does the correlation variation of Meco address the issue of fluctuation in ranking correlation seen in other zero-cost proxies? Can the robustness of Meco be demonstrated through providing the correlation variation?**\n\nAnswer: We have executed MeCo 10 times from the same/different classes to see the variation, which is shown below: \n\n* Variation using samples from the same randomly chosen class\n\n|| CIFAR-10| CIFAR-100| ImageNet16-120|\n|-|-|-|-|\n| NATSBench-TSS | 0.894 $\\pm$ 0.003 | 0.886 $\\pm$ 0.005 |0.845 $\\pm$ 0.004|\n| NATSBench-SSS |-0.79 $\\pm$ 0.02|-0.87 $\\pm$ 0.01|-0.86 $\\pm$ 0.02|\n\n* Variation using samples from different classes\n\n|| CIFAR-10| CIFAR-100| ImageNet16-120|\n|-|-|-|-|\n| NATSBench-TSS | 0.893 $\\pm$ 0.005 | 0.883 $\\pm$ 0.005 |0.838 $\\pm$ 0.007|\n| NATSBench-SSS |-0.79 $\\pm$ 0.01|-0.86 $\\pm$ 0.02|-0.86 $\\pm$ 0.03|\n\nIt can be seen that MeCo is robust when varying the input data and is irrelevant to the class label. \n\n**Q3: Why does the paper claim to use NAS-Bench-101 but not provide the experimental results in the main body? Why was NAS-Bench-201, a widely-used benchmark in the NAS community, not utilized?**\n\nAnswer: We did not provide NAS-Bench-101 in the main body due to the page limits, which is inappropriate to put in the appendix while mentioned in the abstract (thanks for pointing out). We consider moving the results to the main body if the page limit permits, or does not point out NAS-Bench-101 in the abstract part. \n\nWe did conduct experiments on NAS-Bench-201, which is represented as “NATSBench-TSS” in our paper. We also evaluated MeCo on the extended version of NAS-Bench-201 and denoted as \"SSS\". We will clarify the name of the benchmarks to avoid possible confusion. \n\n**Q4: Can Meco maintain computational efficiency when applied to larger networks with a large number of channels, considering the practical implications for neural networks?**\n\nAnswer: MeCo can be adapted to larger networks with more channels because it does not rely on the gradients and only needs one input data. For example, MeCo requires 2.52 GPU hours to evaluate 10k networks in NAS-Bench-301. In practice, the main computation bottleneck is the eigenvalue calculation of the feature maps. For now, we execute MeCo without any thread-level parallelization or optimizations. Moreover, it is possible to constrain the number of channels to make MeCo more efficient. In all, the efficiency of MeCo when applied to larger networks can be further promoted using parallelization and optimized approaches in real applications.\n\n**Q5 (Other concerns in the *Weakness* part): inconsistency in the ranking correlation of NTK between Tab 3 (0.78) and Tab 1 (0.76):**\n\nAnswer: The results in Table 1 are obtained using one data sample from the corresponding dataset (i.e., CIFAR-10/CIFAR-100/ImageNet16-120). While the results in Table 3 are obtained by random data sample generated following a Gaussian distribution. These results demonstrate that our MeCo can achieve the highest correlation even using random data, which is fully data and label-independent. \n\n**Q6 (Other concerns in the *Weakness* part): The performance of other newer zero-cost proxies such as NASWOT, KNAS, NASI, and GradSign:**\n\nAnswer: We would like to add the performance of these mentioned proxies as follows:\n\nNATSBench-TSS:\n\n|| CIFAR-10 | CIFAR-100 | ImageNet16-120 |\n|-|-|-|-|\n| NASWOT| 0.77| 0.80| 0.77|\n| KNAS| 0.20| 0.35| 0.42|\n| NASI| 0.44| 0.43| 0.63|\n| GradSign| 0.77| 0.79| 0.78|\n| **MeCo (Ours)** | **0.89**| **0.88**| **0.85**|\n\nNATSBench-SSS:\n\n|| CIFAR-10 | CIFAR-100 | ImageNet16-120 |\n|-|-|-|-|\n| NASWOT| 0.45| 0.43| 0.42|\n| KNAS| 0.25| 0.12| 0.32|\n| NASI| 0.17| 0.04| 0.20|\n| GradSign| 0.21| 0.16| 0.04|\n| **MeCo (Ours)** | **-0.80**| **-0.89**| **-0.88**|\n\n"}, {"review_id": "aYI0oxOr6D", "reviewer": "Reviewer_5B3N", "summary": "This paper proposes a new proxy ie MeCo for zero-cost neural architecture search. The proxy design aims at overcoming two important disadvantages of zero-cost proxies proposed earlier. The first one is that these proxies invoke at least one back prop and hence are still expensive. The second disadvantage is that the proxies are very much dependent on the data and labels considered.  The designed proxy is evaluated on NATS-Bench-TSS  and NATS Bench-SSS benchmarks and achieves a very high correlation with the ground truth in comparison to other SOTA proxies. Further integration of MeCO can be easily integrated with existing generation method for complete NAS and shows performance gains in comparison to other zero cost proxies. The code of the paper is open-sourced making the approach reproducible. \n", "questions": "In addition to comments in the weakness section I have the following questions:\n1. Could you evaluate the proxy on all tasks from NAS-Bench suite zero and transformer spaces?\n2. Why is the correlation coefficient negative on NATS-Bench-SSS? Could you please elaborate the explanation from line 228-246\n3. Could you compare the cost in computing MeCo v/s other zero-cost proxies? \n", "limitations": "I encourage to discuss the limitations of the designed proxy adequately, for example address the following points:\n1. Are there any important assumptions made in designing the proxy, which may not hold in practice?\n2. Evaluation of how good a zero cost proxy is, is often tied to availability of benchmarks it can be evaluated on. Hence though the proxies 3. are indeed “zero-cost”, the evaluation of the proxy quality is strongly tied to a benchmark which in the first place is very expensive to create. It would be great if the authors could comment on this in the limitations too. \n", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is very well motivated, well-written and clear. The theoretical motivation behind the MeCO is very clearly established. The idea behind the designed proxy is fairly novel to NAS and its effectiveness is established across different benchmarks and also for complete NAS. The authors adequately discuss their hyperparameter settings and release their code for reproducibility. The evaluation is fairly thorough on the NATS-Bench and the method is well-ablated.", "weaknesses": "Main weakness of the paper in my opinion is the search spaces the proxy is studied on.  [NAS-Bench Suite Zero](https://arxiv.org/pdf/2210.03230.pdf) provides easy access and evaluation on about 13 proxies and 28 tasks. Since the performance of a given proxy can vary widely depending upon the search space, task and datasets I am not convinced of the effectiveness of the proxy based on only the results on NATS-Bench and DARTS spaces. Furthermore how would one apply proxies to transformer spaces (eg [AutoFormer](https://openaccess.thecvf.com/content/ICCV2021/papers/Chen_AutoFormer_Searching_Transformers_for_Visual_Recognition_ICCV_2021_paper.pdf) , [HAT](https://arxiv.org/abs/2005.14187)) and MobileNets(eg: [OFA](https://arxiv.org/pdf/1908.09791.pdf),) which provide queryable validation accuracy based on a surrogate. Can this proxy be applied in these spaces? Since modern one-shot NAS methods are applied on transformer and mobilenet spaces too, it is important to design a proxy that does indeed generalize well. I encourage the authors to evaluate their proxy on these search spaces too. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and valuable comments and suggestions! We would like to respond to your reviews point by point.\n\n**Q1: Could you evaluate the proxy on all tasks from NAS-Bench suite zero and transformer spaces?**\n\nAnswer: Thanks for your suggestions! We conduct the experiments on all 28 tasks mentioned in NAS-Bench-Zero-Suite. For character limits, we present the results in the attached PDF, in which Table 1 is 10 tasks on Transbench-101-Micro, Table 2 is 7 tasks on Transbench-101-Macro, Table 3 is 4 tasks on NASBench-301 and 3 tasks on NASBench-201. The remaining 3 tasks on NASBench-201 and 1 task on NASBench-101 are presented in our paper. \n\nIt can be shown from the tables that MeCo achieves the highest correlation on Surface Normal+Macro, Class Objection+Micro, SCifar-100+Micro, NinaPro+Micro, NASBench-301+CIFAR10, and NASBench-201+SVHN. MeCo also achieves competitive results on the majority of the remaining tasks. On some of the tasks, e.g., Autoencoding+Micro, NinaPro+201, MeCo is relatively low. This might be because of the characteristics of the task per se, and the channel-sensitive trait of MeCo. Designing proxies that can be further generalized to more tasks is a promising direction. We would like to note that the existing proxies do not achieve a high correlation on all tasks consistently. \n\n**Q2: Why is the correlation coefficient negative on NATS-Bench-SSS? Could you please elaborate the explanation from line 228-246?**\n\nAnswer: In our paper 3.2.3, we summarize the main theoretical conclusions in which we point out that a multi-channel convolutional layer can be viewed as a multi-sample over-parameterized NN layer. This leads to the fact that MeCo is sensitive to the #channels (which will be treated as samples in MeCo). The more channels contained, the larger the Pearson matrix, which will lead to SMALLER $p_0$. The simulated results in Figure 2 also validate this issue. On the other hand, larger #channels will normally lead to higher accuracy of the architectures (yet lower convergence rate). Thus, the variation of #channels in SSS (chosen from 8 to 64) leads to a negative correlation on SSS. In TSS, however, all the networks share the same #channels at each stage, thus MeCo does not show a negative correlation.\n\nWe would like to further point out that this phenomenon does not contradict our theoretical basis. In practice, various factors (e.g., #channels, #samples, parameters) may affect the network's accuracy. Theorem 2 and Theorem 3 (provided in rebuttal) shed light on the relationship between $p_0$ and the convergence rate/generalization capacity of the network, which has been proven to be effective in multiple benchmarks.\n\n**Q3: Could you compare the cost in computing MeCo v/s other zero-cost proxies?**\n\nWe present the time cost in computing MeCo and other baseline proxies for all architectures in NASBench-201 and 10k networks in NASBench-301.\n\n* NASBench-201 (GPU Hours):\n\n||MeCo (Ours)|fisher|grad_norm|grasp|jacov|nwot|params|snip|synflow|zen|ZiCo|\n|-|-|-|-|-|-|-|-|-|-|-|-|\n|CIFAR10|**2.82**|4.65|4.45|13.59|4.46|3.53|1.56|4.48|2.80|3.51|3.17|\n|CIFAR100|**2.82**|4.68|4.43|13.58|4.44|3.50|1.59|4.47|2.18|3.50|3.73|\n|ImageNet16-120|**2.83**|4.51|4.34|6.62|4.38|3.94|2.62|4.37|3.82|3.99|3.71|\n\n* NASBench-301 (GPU Hours):\n\n| |MeCo (Ours)|fisher|grad_norm|grasp|jacov|nwot|params|snip|synflow|zen|\n|--|--|--|--|--|--|--|--|--|--|--|\n|CIFAR10|**2.52**|7.33|6.77|32.74|7.05|3.83|1.54|6.67|3.18|4.44|\n\nMeCo is efficient because it only requires one forward pass. Although it is slower than #Params, MeCo achieves a higher correlation than #Params on multiple benchmarks.\n\n**Q4 (Other concerns in ``Weakness`` part): How would one apply proxies to transformer spaces (eg AutoFormer , HAT) and MobileNets(eg: OFA,)? Can this proxy be applied in these spaces?**\n\nWe conduct the experiments on the transformer search space (AutoFormer) and MobileNets-like search space (OFA). \n\nFor AutoFormer, we load the trained supernets and regenerate the candidate subnets. We then re-evaluate the subnets to obtain the accuracy and compute MeCo. The correlation of MeCo and model accuracy on AutoFormer is **0.45**. \n\nFor MobileNet OFA, we regenerate the architectures and directly compute MeCo upon the models. The correlation of MeCo and model accuracy on OFA is **0.864**, which is relatively high.\n\nP.S., we use the AutoFormer[1] instead of the paper provided in the review link, which we carefully checked and thought it might be another paper with the same name :)\n\n**Q5 (Other concerns in ``Limitation`` part): Are there any important assumptions made in designing the proxy, which may not hold in practice?**\n\nAnswer: In our theoretical analysis, we assume there are no parallel inputs and $ c<w \\times h $, where $c$ is the number of channels, $w\\times h$ is the size of the input. Under this assumption, $p_0$ is strictly greater than zero. This might not hold in practice when there are parallel inputs or large #channels. We will elaborate on this issue in the ``Limitation`` section.\n\n**Q6 (Other concerns in ``Limitation`` part): Valuation of how good a zero-cost proxy is, is often tied to availability of benchmarks it can be evaluated on. Hence though the proxies 3. are indeed “zero cost”, the evaluation of the proxy quality is strongly tied to a benchmark which in the first place is very expensive to create. It would be great if the authors could comment on this in the limitations too.**\n\nAnswer: Thanks for your valuable suggestion. We will further comment on this in the ``Limitation`` Section.\n\n[1] Chen M, Peng H, Fu J, et al. Autoformer: Searching transformers for visual recognition[C]//Proceedings of the IEEE/CVF international conference on computer vision. 2021: 12270-12280."}, {"review_id": "AWDNLzk9Jb", "reviewer": "Reviewer_4Zmk", "summary": "This paper proposes MeCo, a new zero-shot NAS method that can rank model architectures without training, without any backward pass, and just using 1 data sample (instead of a batch of data like existing methods). The method is evaluated on multiple NAS Benches and the authors have also run NAS experiments on CIFAR-10 and CIFAR-100 datasets. Rest of the NAS runs are done directly on NAS-Benches. The authors have also presented a simple theoretical result relating Pearson’s correlation to gram matrix which is sometimes used to prove effectiveness of zero-cost proxies.", "questions": "Please see above.", "limitations": "Yes, in appendix.", "rating": 7, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper has following strengths: \n\n1. The main strength of this idea is that it uses only one data sample and no backward pass. So, the proposed zero-shot method is quick.\n\n2. On NATS-Bench-SSS and NATS-Bench-TSS, the proposed method achieves higher correlation than existing methods.\n\n3. The paper is very well-written.", "weaknesses": "The paper has following weaknesses: \n\n1. No results on zero-shot NAS runs on generic search spaces on ImageNet. Due to low search cost, many new proxies like ZiCo, ZenNAS, etc., have shown results on ImageNet and often beat multi-shot and one-shot methods by a large margin (in search time as well as accuracy). The authors should conduct this experiment with MeCo and present detailed results and comparisons to existing methods. In the current state, the total accuracy improvements compared to existing baselines like Zen, ZiCo, etc., are not too significant (e.g., see tables 4, 5, 6 in supplementary and table 4 in main paper). Significant improvements on ImageNet can make the paper's claims much more convincing.\n\n2. Between NATS-Bench-TSS to NATS-Bench-SSS, the correlation changes from highly positive correlation to highly negative correlation (see Tables 1 and 2 in main paper). Authors show some results stating that this is related to large channel widths of networks which impacts the minimum eigenvalue. However, this may also mean there may be some channel widths where the MeCo correlations may become close to zero (since it changed from highly positive to highly negative when changing channel widths or other architecture properties). In case that happens, it may be problematic since zero correlations cannot really say anything about model quality. Can the authors conduct a detailed (theoretical/empirical) analysis towards this important issue? Under what conditions would MeCo work optimally?\n\n3. It was not clear what kind of data size the authors changed in Section 5 ablation study. Did they change input feature dimensions or number of samples? If they did not ablate over number of samples used to calculate MeCo, they should conduct such a study (e.g., how does correlation vary if you use 16 samples instead of 1 sample, etc.). \n\n4. Also, if they use only one data sample to calculate MeCo, what is the variance of MeCo across multiple samples from same or different classes?\n\n5. Few other NAS-Benches are available and has been utilized in literature (e.g., TransNASBench and others used in ZiCo paper). More results can be shown on those benchmarks.\n\n6. A couple other papers authors should also discuss in related work: (1) “Layerwise Dynamical Isometry” [ICLR 2020, https://arxiv.org/abs/1906.06307] that talks about signal propagation properties via layer Jacobians to improve training convergence of highly sparse networks. (2) NN-Mass [CVPR 2021, https://arxiv.org/abs/1910.00780] which explicitly relates topological properties of deep networks to gradient flow. NN-Mass does not even require any forward pass and ranks networks purely using their architecture's structural properties (although it works in very limited settings). In fact, these two works form the earliest precursors to the zero-shot NAS domain (and came before all other training free metrics) and must be discussed.\n\n\n==== UPDATE AFTER REBUTTAL ====\nI have read the author response and other reviews. The new data and analyses provided by the authors have improved the paper compared to the initial submission. However, I still have concerns regarding some of the new data: \n\n(1) ImageNet results: Looking at table 9 in zico paper, we see that they achieve 77.1% imagenet accuracy with 600M FLOPS. However, in a comment to another reviewer, authors reveal that their MeCo found model requires nearly 884M FLOPS. This is a major increase in FLOPS with only 0.2% improvement in accuracy. Hence, this result is not convincing. Note that, there may be major differences between ZiCo and authors' training recipe and search space. If this is the case, I would encourage the authors to provide more details. \n\n(2) The negative correlation thing and the channel sensitivity indeed seems to be a major weakness of this work. I appreciate authors' analysis that if c < wxh, MeCo would work better. However, this is violated for many image classification networks (e.g., on imagenet 224x224 input resolution with final layers getting 7x7 feature map size and much higher channel counts). The new results in Table 3 of the attached pdf also confirm that on some other use cases the MeCo does start losing correlations (although, on a lot of datasets, it performs very well). Hence, this can limit the applicability of this work. Can authors explore techniques to fix this channel sensitivity issue? Given this new information about c<wxh, it may actually be better if authors can mainly focus on vision tasks with much higher input-output resolutions, e.g., image super resolution and semantic segmentation. Specifically, for such vision applications, resolutions generally go up to 1080p or even 4K, so these applications may show the most benefits of authors' approach (and thus show that under applications with c<wxh, MeCo is always well behaved and does not lead to zero values, etc.). Of note, super resolution with smaller models (e.g., SESR (MLSys 2022), https://arxiv.org/abs/2103.09404) does not take long to train.\n\nAnyways, given the improvement in clarity, new results, and new analysis, I am raising the rating to 4. I can raise the rating to 5 (or even 6 depending on how strong the results are) provided the authors (a) clearly identify the settings under which MeCo must be used (i.e., this dependence on c<wxh) right from the beginning of the paper (introduction, motivation, etc.), and (b) clearly demonstrate at least one vision application with high resolution input-output (e.g., super resolution...there have been NAS papers on this topic before: https://arxiv.org/pdf/2007.04356.pdf (ECCV 2020)). But without seeing major improvements on the above issues, I cannot increase the rating further at this time. I do think the authors are on to some interesting research. I would encourage them to continue this work and improve it further.\n\n==== FURTHER UPDATE ====\nAuthors have fixed the main weakness with the introduction of their sensitivity correction method MeCo-Opt. All negative correlations are now positive (I do recommend to let other reviewers with lower rating know about this if they have similar concerns...but I leave that decision to the authors). A few Nas benches show near zero correlations but that is to be expected since no zero shot proxy is perfect. Moreover, the new zero shot proxy correction MeCo-Opt either maintains accuracy results or significantly improves them (e.g., for Imagenet-16-120 Nas bench). I hope the authors will use the remaining time until final notification to make sure their presentation is perfect in light of these new contributions: Specifically, motivate the need for metrics that work for higher resolution input-output vision tasks like segmentation, properly introduce the sensitivity correction in the main approach, update all the results with both MeCo and MeCo-Opt, conduct a few more real world experiments showing the significant improvements under MAC constraints that go beyond Nas benches (e.g., Imagenet and other Segmentation or Detection tasks) to complete the high-resolution input output picture and also provide conclusively better results over existing proxies under MAC constraints, and cover all the related work pointed out by all reviewers. The paper (particularly after rebuttal) has made strong contributions so please ensure that they are reflected in the presentation in the next version. I believe that with good presentation, this work should be of interest to the research community.\n\nGiven that my main concern is now resolved, I raise the rating to 7. Good luck!", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and valuable comments and suggestions! We would like to respond to your reviews point by point.\n\n**Q1: Results on ImageNet.**\n\nAnswer: We adopt MeCo-based NAS to ImageNet-1k dataset on MobileNet-v2 search space. The results are shown in Table 4 in the attached PDF. We trained the searched optimal network with 6 RTX 3090 for about 130 hours. The Top-1 accuracy is **77.3\\%**, which is higher than all the baseline approaches.\n\n**Q2: Detailed analysis for the opposite results on TSS and SSS:**\n\nAnswer: \n* Under what condition may the minimum eigenvalue become zero?\n\nIn theory, for convolutional layers, $p_0$ is strictly greater than zero if $x_i \\nparallel x_j, \\forall I \\neq j$ and $c<w \\times h$, where $c$ is the \\#channel, $w\\times h$ is the input size. For ReLU activation, $p_0$ may be zero when the output matrix is singular. \n\n* In experiments, does $p_0=0$ (or $p_0$ is close to zero) affect our results?\n\nWe would like to point out that this phenomenon will not affect the effectiveness of MeCo. Although MeCo may become (close to) zero when $c \\ge w \\times h$ due to the downsampling operation, all the architectures are compared under the same criteria. Specifically, in TSS, MeCo becomes zero only happens in the last set of cells where $c=w\\times h=64$. However, all the topology has been evaluated in the previous cells in TSS. In SSS, MeCo is indeed sensitive to the #channels which leads to a strong negative correlation. However, the high correlation in Table 2 indicates that MeCo is still effective in discriminating and evaluating architectures in SSS. In fact, the most straightforward way to guarantee $c<w\\times h$ is to change the input's dimension, making the size of the output tensor larger than #channels after all the downsampling. Thus we conduct the ablation study in Section 5 to show the performance of MeCo under different dimensions of inputs. The results in Figure 4 also support our theoretical analysis and shows that the best performance can be acquired when the input dimension is around $32 \\times 32$ to $64 \\times 64$. Finally, we would like to point out that the negative correlation on SSS also indicates a high correlation of #channels and accuracy on SSS search space. \n\n* Under what conditions would MeCo work optimally?\n\nThe results of both the theory and experiments demonstrate that MeCo works best in evaluating the topology of the architectures (which again explains the good performance on TSS). To avoid MeCo from becoming zero and further improve its performance, we believe it is possible to limit #channels to satisfy the condition $c<w\\times h$. This can be done by adding a sampling method of the output channels. We will leave this as future work.\nFinally, we found that in TSS, MeCo is zero in the last set of cells yet still achieves the highest correlation with the accuracy. This indicates that it is possible to evaluate the architectures *partially* without computing upon the whole skeleton. This is also intriguing and may further improve the performance of MeCo. \n\n**Q3: The ablation of the #Samples:**\n\nAnswer: The ablation study in Section 5 is designed to demonstrate the relationship between MeCo and the dimension of the input samples, not the #Samples. \nWe add ablation experiments about #Samples v.s. MeCo performance. We randomly chose different #Samples to evaluate the architectures in the entire TSS and SSS, respectively. The results are shown in Figure 1 in the attached PDF. \n\nIt can be shown from the figure that MeCo is relatively stable when varying the #Samples. The performance of MeCo fluctuates around 0.01 throughout the experiments. These results support that MeCo only requires one data sample. \n\n**Q4: Variance of MeCo:**\n\nAnswer: We have run MeCo 10 times from the same/different classes to see the variation, which is shown below: \n\n* Variation using samples from the same randomly chosen class\n\n|| CIFAR-10| CIFAR-100| ImageNet16-120|\n|-|-|-|-|\n| NATSBench-TSS | 0.894 $\\pm$ 0.003 | 0.886 $\\pm$ 0.005 |0.845 $\\pm$ 0.004|\n| NATSBench-SSS |-0.79 $\\pm$ 0.02|-0.87 $\\pm$ 0.01|-0.86 $\\pm$ 0.02|\n\n* Variation using samples from different classes\n\n|| CIFAR-10| CIFAR-100| ImageNet16-120|\n|-|-|-|-|\n| NATSBench-TSS | 0.893 $\\pm$ 0.005 | 0.883 $\\pm$ 0.005 |0.838 $\\pm$ 0.007|\n| NATSBench-SSS |-0.79 $\\pm$ 0.01|-0.86 $\\pm$ 0.02|-0.86 $\\pm$ 0.03|\n\nIt can be seen that MeCo is robust when varying the input data and is irrelevant to the class label. \n\n**Q5: More results on other benchmarks:**\n\nAnswer: We conduct experiments on Transbench-101, NASBench-301, NASBench-201, Transformer-like, and Mobilenet-like benchmarks. The results of the first three are shown in Table 1, 2, and 3 in the attached PDF.\n\nFor Transformer-like benchmark AutoFormer, we load the trained supernets and regenerate the candidate subnets. We then re-evaluate the subnets to obtain the accuracy and compute MeCo. The correlation of MeCo and model accuracy on AutoFormer is **0.45**. \n\nFor MobileNet-like benchmark OFA, we regenerate the architectures and directly compute MeCo upon the models. The correlation of MeCo and model accuracy on OFA is **0.864**, which is relatively high.\n\nIt can be shown from the tables that MeCo achieves the highest correlation on Surface Normal+Macro, Class Objection+Micro, SCifar-100+Micro, NinaPro+Micro, NASBench-301+Cifar10, and NASBench-201+SVHN. MeCo also achieves competitive results on the majority of the remaining tasks. On some of the tasks, e.g., Autoencoding+Micro, NinaPro+201, MeCo is relatively low. This might be because of the characteristics of the task per se, and the channel-sensitive trait of MeCo. Designing proxies that can be further generalized to more tasks is a promising direction. We would like to note that the existing proxies do not achieve a high correlation on all task consistently. \n\n**Q6: Other papers in related work.**\n\nAnswer: Thanks for your suggestions! We will add these papers to the related work and elaborate more."}, {"review_id": "z1fM75VLfC", "reviewer": "Reviewer_1Ted", "summary": "This paper proposes a novel zero-cost proxy called MeCo. The proxy is data-independent, which requires only one random data with a single forward pass. It analyzed that the minimum eigenvalue of P(X) is correlated to the training convergence rate of the network. The experiments on several NAS benchmarks evaluate the effectiveness of MeCo.", "questions": "1. In the theoretical proof section, the paper mainly focuses on the network convergence rate and convolutional layer. I wonder how can the theory be connected with network generalization? And can the MeCo metric be applicable to the self-attention layer?\n2. The paper proposes to use only one random data. But the ablation experiments in Figure 4 show that the optimal result is obtained when the data size is not equal to 1. How to explain this?\n3. In Table 5, why is the search cost higher than the other gradient-based zero-cost methods? For example, Zero-Cost-PT_MeCo v.s. Zero-Cost-PT_ZiCo and Zero-Cost-PT_Snip, because the paper requires only one random data with a single forward pass which should be very low search cost. \n4. The results on ImageNet in DARTS-CNN search space should be provided.\n5. To show the effectiveness of MeCo, more ranking consistency experiments should be conducted in different search spaces, such as NAS-Bench-301.\n6. Minor Error. In line 220, \"0.6 to 0.9\" -> \"0.06 to 0.09\".", "limitations": "See the Weaknesses and Questions above.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a novel zero-cost proxy MeCo, which is theoretically guaranteed.\n2. The ranking correlation results demonstrate the superiority of MeCo compared with other proxies.\n3. The writing is good and easy to follow.", "weaknesses": "1. On Table 5, the performance gain of Zero-Cost-PT_MeCo is small compared to other Zero-Cost-PT methods. Besides,  the performance gain of Zero-Cost-PT_MeCo is lower than TE-NAS.\n2. More experimental results should be provided to demonstrate the effectiveness of the proposed method, such as the ranking results on NAS-Bench-301 and the search results on ImageNet in DARTS search space.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for your time and valuable comments and suggestions! We would like to respond to your reviews point by point.\n\n**Q1: How can the theory be connected with network generalization? Can the MeCo metric be applicable to the self-attention layer?**\n\nAnswer: 1) MeCo can also reflect the generalization capacity of a network. We present the following theorem.\n\n**Theorem 3.** For an over-parameterized neural network, we denote the loss as $L(W)$. Let $y=(y_1, ..., y_N)^T$ ,  $\\lambda_0=\\lambda_{min}(H^{\\infty})$. Let $\\gamma$ be the step of SGD, $\\gamma = \\kappa C_1\\sqrt{y^T(H^\\infty)^{-1}y}/(m\\sqrt N)$ for some small enough absolute constant $\\kappa$. Under the assumption of Theorem 1,  for any $\\delta\\in(0,e^{-1}])$, there exists $m^\\ast(\\delta,N,\\lambda_0)$, such that if $m\\geq m^*$, then with probability at least $1-\\delta$, we have\n$$\nE[L(W)] \\leq O(C'\\sqrt{\\frac{y^T y}{p_0 N}})+ O(\\sqrt{\\frac{\\log(1/\\delta)}{N}})\n$$\nwhere $C, C', \\delta$ are constants. \nThe proof can be obtained from Corollary 3.10 of [1] and Section D.2 of [2]. Theorem 3 indicates that the generalization capacity is bounded by $p_0$. The expectation of the loss decreases when $p_0$ gets larger. This relationship is consistent with Theorem 2.\n\nWe would like to point out that Theorem 3 indicates that the generalization capacity of a network is bounded by $p_0$. The expectation of the loss on the testing dataset decreases when $p_0$ gets larger. This relationship is also consistent with the impact of $p_0$ on the convergence rate.\n\n2)Intuitively, MeCo can be applied to any architecture so long as the feature maps during the forward pass can be extracted. To test this, we adopt MeCo on a transformer benchmark (Autoformer). The correlation between MeCo and the model performance is 0.45, which proves the effectiveness of MeCo to an extent. The theory of MeCo is built on the over-parameterized NN layer, which is not the same as the self-attention layer. We will leave the extension of the theory part as our future work.\n\n\n**Q2: Unclear ablation study:**\n\nAnswer: Figure 4 demonstrates MeCo v.s. the SIZE of the data sample, not the number of samples. It might be more appropriate to use the word \"dimension\" to avoid possible confusion. All the experiments on MeCo are conducted using one data sample, which would be first resized to a specific dimension. Figure 4 shows the best data dimension for SSS and TSS. We will clarify this in this section to avoid possible confusion. \n\n**Q3: In Table 5, why is the search cost higher than the other methods?**\n\nAnswer: MeCo is more resource-saving because it only requires one forward pass. In Table 5, the main computation bottleneck is computing the minimum eigenvalue of the Pearson correlation matrix. For now, we use one CPU kernel without any thread-level parallelization or optimizations. We believe the time cost can be further reduced by adopting parallelization techniques. \n\n**Q4: The results on ImageNet:**\n\nAnswer: Thanks for pointing out this issue. We agree that we should provide more results, especially on large-scale datasets. Unfortunately, it is relatively difficult to fully train the searched model in DARTS-CNN on ImageNet-1k in this short rebuttal period. So alternatively, we provide the results on ImageNet-1k with MobileNet v2-like search space. The results are shown in Table 4 in the attached PDF. We trained the searched optimal network with six RTX 3090 for about 130 hours. The Top-1 accuracy is **77.3\\%**, which is higher than all the baseline approaches.\n\n**Q5: More results on other benchmarks.**\n\nAnswer: We conducted more experiments on NASBench-301, NASBench-201, TransBench-101 (both Micro and Macro), MobileNet-like search space, etc. The experimental results can be found in Table 1, 2, and 3 in the attached PDF. \n\nFor NAS-Bench-301, we utilize three extra datasets except for the standard CIFAR-10 following the settings in NASBench-zero-suite. The results show that MeCo achieves the highest correlation on CIFAR-10 among all the baselines (e.g., 0.04 higher than Zico). MeCo also provides competitive performance on NinaPro and SVHN (e.g., 0.09 and 0.02 lower than the best method). On Spherical-CIFAR-100, MeCo has an average correlation that is 0.08 lower than grasp. Yet MeCo outperforms grasp on all the remaining tasks. MeCo also achieves SOTA results on other benchmarks, please refer to the Tables in the attached PDF for more details.\n\n**Q6: In line 220, \"0.6 to 0.9\" -> \"0.06 to 0.09\".**\n\nAnswer: Thanks for pointing this out! We will fix this typo.\n\n**Q7 (Other concerns in the *Weakness* part):The performance gain of Zero-Cost-PT_MeCo is lower than TE-NAS.**\n\nAnswer: We acknowledge that MeCo achieves marginal performance gain using Zero-Cost-PT and lower accuracy than TE-NAS. We would like to point out that MeCo is designed as an evaluation metric of the architecture, which achieves SOTA correlation on TSS, SSS, NASBench-301 (added in rebuttal), and some tasks on Transbench-101 (added in rebuttal). These results reflect the capability of MeCo and demonstrate the possibility of a resource-saving and label-independent zero-cost proxy. On the other hand, almost all the zero-cost proxies need to be integrated with an external generation strategy to form a complete NAS (e.g., Zero-cost-PT). Thus, the performance of the proxy-based NAS relies on the generation strategy. Zero-cost-PT performs unconstrained NAS, which is different from the baselines, thus should not be interpreted as objectively better (p.9 in Zero-cost-PT). We will leave the research on the more appropriate generation algorithm as our future work. \n\n[1] Cao Y, Gu Q. Generalization bounds of stochastic gradient descent for wide and deep neural networks[J]. Advances in neural information processing systems, 2019, 32.\n\n[2] Zhu Z, Liu F, Chrysos G, et al. Generalization properties of NAS under activation and skip connection search[J]. Advances in Neural Information Processing Systems, 2022, 35: 23551-23565."}]

Author rebuttal:
General Response to the Reviewers. 

We thank all the reviewers for their time and valuable comments and suggestions, which are indeed promising and can improve the quality of our paper! In this rebuttal period, we made several improvements and additions to the current version in terms of both theoretical and experimental aspects.

We summarize the main improvements here and reply to each of the reviewers respectively. 

* Experimental Aspects

    - Performance of MeCo on more benchmarks (Rev1, Rev3, Rev4, Rev5): We add experiments on NASBench-301, NASBench-201 (with extra three datasets), and MobileNet-like benchmark (OFA) to show the effectiveness of MeCo.
    - Performance of MeCo on other tasks and regions (Rev1, Rev3, Rev4): We add experiments on Transbench-101-Macro, Transbench-101-Micro (including extra three datasets), and a transformer benchmark (AutoFormer) to show the performance of MeCo for various tasks.
    - Performance of MeCo on large-scale dataset ImageNet-1k (Rev1, Rev4, Rev5): Other than the OFA benchmark (which is trained on ImageNet), we also add experiments on ImageNet-1k with MobileNet v2 and provide the Top-1 accuracy of the selected architecture.
    - Impact of #Samples on MeCo (Rev1, Rev4): We conduct a new ablation study in terms of the impact of #samples on MeCo.
    - Variation and robustness of MeCo (Rev2, Rev4): We provide the variation of MeCo for different #Samples from the same or different classes. 
    - Missing baselines and evaluation metrics (Rev2, Rev3): We add the performance of the baselines and provide the time cost comparison.  

* Theoretical Aspects

    - Generalization capacity of MeCo (Rev1, Rev5): We provide a new theorem to show the connection between MeCo and generalization capacity. 
    - Negative correlation on SSS (Rev1, Rev3, Rev4): We elaborate more on this issue respectively corresponding to each reviewer's question. 

* Clarity

  We clarify the following issues regarding the reviewer's confusion:

    - Name of the benchmarks (Rev2).
    - Goal of the ablation study (Rev4, Rev5).
    - Inconsistent results of NTK (Rev2).
    - Time cost in Table 5 (Rev5).
    - Accuracy of the selected optimal architecture (Rev1).

* Other Improvements

  - ``Limitations`` section (Rev3): We thank the reviewer for the promising insight. We elaborate more on these issues and will add them to the paper.  
  - ``Related Work`` section (Rev4): We will add the papers as references and elaborate more.
  - Typo in ln.220 (Rev1, Rev5): We will fix the typo.

We present the experimental results on Transbench-101-Micro, Transbench-101-Macro, NASBench301, NASBench201 (extra tasks), and model accuracy on ImageNet-1k in the attached PDF due to the character limits. 

Meta-review: Reviewers were enthusiastic about the paper and recognized a technically sound paper with good results. Reviewers raise some minor point in their review which have been addressed in the rebuttal. We invite the authors to take these changes into account in the camera-ready version of the paper.
Decision: Accept (spotlight)