Variation Matters: from Mitigating to Embracing Zero-Shot NAS Ranking Function Variation
Authors: Pavel Rumiantsev
Mark Coates
Venue: Accepted by TMLR ()

Abstract: Neural Architecture Search (NAS) is a powerful automatic alternative to manual design of a neural network.
In the zero-shot version, a fast ranking function is used to compare architectures without training them.
The outputs of the ranking functions often vary significantly due to different sources of randomness, including the evaluated architecture's weights' initialization or the batch of data used for calculations.
A common approach to addressing the variation is to average a ranking function output over several evaluations.
We propose taking into account the variation in a different manner, by viewing the ranking function output as a random variable representing a proxy performance metric.
During the search process, we strive to construct a stochastic ordering of the performance metrics to determine the best architecture. 
Our experiments show that the proposed stochastic ordering can effectively boost performance of a search on standard benchmark search spaces.

Published in Transactions on Machine Learning Research (02/2025)
Variation Matters: from Mitigating to Embracing Zero-Shot NAS Ranking Function Variation
Pavel Rumiantsev
The Deportment of Electrical and Computer Engineering
McGill University
Mark Coates
mark. markk.contes&@maggll.cc
The Department of Electricol and Computer Engineering
McGill University
Reviewed on OpenReview: https: // openreview. net/ fert/formm Sd=SbGt9dd
Abstract
Neural Architecture Search (NAS) is powerful automatic alternative to manual design of neural network. In the zero-shot version, fast ranking function is used to compare architec- lures without training them. The outputs of the ranking functions often vary significantly due to different sources of randomness, including the evaluated architecture's weights' ini- tialization or the batch of data used for calculations. A common approach to addressing the variation is average ranking function output over several evaluations. We propose taking into account the variation in different manner, by viewing the ranking function output a random variable representing proxy performance metric. During the search process, we strive to construct a stochastic ordering of the performance metrics to deter- mine the best architecture. Our experiments show that the proposed stochastic ordering can effectively boost performance of a search on standard benchmark search spaces.
1 Introduction
Zero-shot Neural Architecture Search (NAS) is a way to perform selection of neural archilecture without training every candidate architecture. Recently, zero-shot NAS has been applied to a variety of practical tasks, including modical image processing (Wang et al. 2024). sequence processing (Scrianni & Kalita, 2023
language model architecture enhancements (Javaheripi al. 2022) and general image classilication (Jiang
et al. 2024 Li al. 2022).
In general, zero-shot approach consists of two parts: ranking function and scarch algorithm (Xu et al. 2021 Rumiantsev & Coates 2023 Cavagnero et al. 2023a Li et al. 2022 Jiang et al. 2024). The ranking function aims to capture the quality of particular candidate architecture in the form of scalar value, which allows two architectures to be easily compared (Abdelfattah et al. 2021). A search algorithm uses a ranking function to determine the best architecture over the given architectural search space. For this work, we view a search space as combination a feasible architecture set and a dataset of labelled training, validation, and test samples.
While the zero-shot approach is the fastest way to find architecture that performs well, it suffers from variations in the output of the ranking function. In order to assess architecture as quickly possible, most zero-shot techniques sample single batch of data, and randomly initialize the architecture. The ranking function then uses the batch of data and the initialized network to derive a scalar score. The batch selection and initialization thus induce considerable randomness in the output. There are several data-agnostic ranking functions, including SynFlow (Abdelfattah et al. (202)) and LogSynFlow (Cavagnero) et al., 2023a), which use a batch of constant unit inputs, and Zen-Score (Lin et al., (2021), which uses batch of randomly generated data input. Thus, there is still randomness, and the same problem remains.

---

Published in Transactions on Machine Learning Research (02/2025)
Typically, zero-shot techniques address this issue by averaging the outputs of the ranking function over multiple batches of data.
A zero-shot search procedure can counter some of the variation of the preferred ranking function by employing a robust search algorithm. For example, Chen et al.
(2021) use prune-based search to increase the stability of the search. In general, the performance of a search algorithm can vary considerably, depending on which ranking function is paired with it (Akhauri et al.] 2022 Rumiantsev & Coates 2023). Since it is very challenging to meaningfully analyse ranking function in isolation (independently of search algorithm), we base our experimental conclusions on pairs of ranking function and search algorithm. We focus the most popular ranking functions and search algorithms. Specifically, we select Eigenvalue score (Mellor et al. 2020), ReLU Hamming distance (Mellor et al.] 2021) and condition number of the neural tangent kernel (NTK) CChen et al.) 2021) to demonstrate how random search (Mellor et al. 2020) and evolutionary search (REA (Real et al. 2019) and FroeREA @Cavagnero al. 2023a)) achieve better performance the majority of cases (>80 percent), when enhanced with our statistical evaluation approach, for standard architoctural search spaces including NAS-Bench-101, NAS-Bench-201., and TYansNAS-Bench-1000
In this paper, we assess the variation of different ranking functions, explore how common ways to minimize the ranking function variation help to increase the zero-shot performance, and introduce way to incorporate variation into the assessment of an architecture. Our main contributions are:
We introduce a ranking function variance analysis framework for zero-shot NAS researchers to analyse cxisting and newly dosigned ranking functions.
We use the variance of ranking function to statistically compare architectures, and show that this enhances the performance of random and evolutionary search algorithms for zero-shot NAS for variety of commonly-used ranking functions and architectural spaces.
2 Background
2.1
Search Algorithms
There are three common choices of search algorithms that are used in Zero-Shot NAS: random search, prune- based search and evolutionary search. Random search is the search algorithm with the least computation overhead. It randomly samples a subset of architectures from the scarch space, and then selects the one with the highest rank according to the chosen ranking function. The size of the sampled subset is the main hyperparameter that controls the trade-off between search speed and efficacy. Due to its simplicity, it is a
common choice (Lopes et al. 2021 Xu ct al. 2021 Mellor et al. 2020 2021 Mok ct al. 2022).
Evolutionary search procedures are based on genetic algorithins. They start with randomly selected architectures, then generate mutations, and then select a subset that are ranked the highest according to the ranking function output. The procedure is then itcrated. Mutations can be based on replacement of architectural operators involve direct manipulations of the architecture encoding. Evolutionary search is slower and more challenging to implement than random search, but the results it produces are more stable. Variations of this search technique are employed more often in recent works {Lin et al. 2021 Akhauri et al. 2022 Li et al. 2022 Mok et al.) 2022 Cavagnero et al. 2023a b Yang et al.] 2023 Wang et al. 2024). Often, the ranking function is applied to multiple batches of data, with the results averaged, in order to provide a more stable score. This procedure is usually performed once, when the architecture is first encountered during the search, with the calculated score cached for later use.
The third type of search algorithm is prune- search. It iteratively removes edges from the hypergraph that can be used to represent all architectures. By estimating the difference in ranking function output for the architectures represented by the hypergraph with and without a given edge, the algorithm can choose the best edge to prune. This process is repeated until the hypergraph represents a single architecture. This type of scarch introduces significant computational overhcad as it requires to evaluate the entire hypergraph for every umpruned edge (Chen et al.) (021)). It is the most challenging implement and, therefore, is rarely adopted (Chen et al. 2021 Rumiantsev & Coates
2023 Jiang al. 2024
2

---

Published in Transactions on Machine Learning Research (02/2025)
2.2 Zero-shot ranking functions
Many zero-shot ranking functions have been proposed, and we now review some of the most prominent. Abdelfattah et al. (2021) repurposed metrics previously employed in neural network pruning. The saliency metrics Snip (Lee et al. 2019), ; Grasp (Wang et al. 2020), Fisher (Turner et al., 2020) and SynFlow (Tanaka et al. 2020 measure the impact of removing a specific parameter or operation from the network. In adapting these to construct a zero-shot ranking function, Abbdelattah et al. (2021) sum over all of the architectural parameters, and thus construct a measure of the fitness of the entire architecture. Cavagnero al. (2023a) introduced logarithmic version of SynFlow named LogSynFlox. Applying a logarithm suppresses some of the gradient explosions that can unduly influence the score.
The first two ranking functions designed specifically for the zero-shot setting were the Eigenvalue score (Mellor et al. 2020) and the Hamming distance between the ReLU regions (Mellor et al. 2021 Based on the Neural Tangent Kernel (NTK) (Jacot et al. 2018), the Eigenvalue score uses the eigen- values of the gradient correlation matrix to prodict the learning capabilitios of an architecture. The ReLU Hamming distance is constructed as a determinant of the kernel of Hamming distances betweent activation patterns of ReLU, where a pattern is represented a string of zeros and ones. An alternative measure is the number of activated ReLU regions for sampled batch of data (Xiong et al. 2020). The underlying conjecture is that activation of more regions allows the network to learn more complex data dependencies.
Similarly, [eng et al. (2024) proposes to count the number of unique ReLU activation patterns across the data dimension. The Entropic Score (Cavagnero et al. 2023b) is also based on RcLU activations.
Several othe ranking functions are based on the NTK, including (i) the mean value of the NTK (uu et al. 2021); (ii) the Frobenius norm of the NTK (Xu et al., 2021); and (iii) the negative condition number of the NTK (Chen et al., 2021]. The NTK can introduce undesirable computational overhead, so other rescarchers have explored alternative metrics. Ruuiiantsev & Coales (0223 show that the Frobenius norm of the Neural Network Gaussian Process (NNGP) kernel can act as an effective ranking function. Jiang et al. (2024) focus on the Pearson correlation kernels of the internal representations of an architecture, and compute the sum of the smallest eigenvalues of these kernels. For all of these proposed ranking functions, the required kernels are estimated using a random batch of data.
Since most benchmark search spaces focus on the classification task, some ranking functions incorporate the available label information. Gradiett Alignment (LGA) (Mok et al. 2022) constructs metric based on both the class similarity matrix and the NTK. Lopes et al. (2021 propose EPE-NAS, which uses the gradient correlation matrix, and is thus similar to the Eigenvalue score, but is computed class-wise. For practical reasons, both LGA and EPE-NAS are computed using a random batch of data.
Some ranking functions are based on the gradients of the trainable weights. SweetGrad counts the number of gradient norms in predefined interval (Yang et al. 2023). Li et al. (2022) sum the coefficients of variations associated with the weight, gradients to compute ZiCo.
3 Problem statement
A neural architecture search space can be represented as set of leasible architecutres (archx)(=11.Nas of size Nss. Associatod with the architccture space is datasct D consisting of pairs of features E X and labels y V. In this work we consider computer vision tasks where an architecture arch; is associated with final accuracy after training, labelled acc, A zero-shot ranking function assigns scalar score to each architecture: 8; = r(arch;; D). A scarch is then conducted using these scalar scores, with the goal of selecting the most accurate architecture.
As discussed above, almost every zero-shot ranking function has an element that is evaluated over a batch of input data (c.g., the NTK, gradient cocfficients of variations, or logit similarity matrix). To improve the stability of the output, most ranking functions are averaged over multiple random batches. Our goal is use the multiple ranking function outputs in more effective way.
3

---

Published in Transactions on Machine Learning Research (02/2025)
In subsequent sections, explore how sensitive different ranking functions to the random selection of the input data used in their calculation. We point out how commonly used statistical methods allow to overcome such sensitivity in order to improve the performance of a zero-shot approach.
4 Methodology
This section describes our study into the variability of ranking functions. First, we introduce variation metric for assessing the variability of a ranking function for a particular search space and batch size. Sec- ond, we present our zero-shot search setup and explain how the variation metric can be used to improve performance.
4.1 Ranking function variation
It is common for ranking functions to use a real training datasct. In order to assign a score to an architecture, batch of data is randomly drawn from the dataset. The ranking function scores vary from batch to batch, with the extent of the variation being potentially dependent the batch size, the dataset, and the task.
We measure ranking function variation over the entire search space by computing, for each architecture, an empirical coefficient of variation for the ranking function output over randomly sampled batches of input data. We then average over the architectures. To ensure the coefficient of variation is an appropriate metric, we have specified a "meaningful zero" for the ranking functions. We discuss this in detail in Appendix G
Denoting the batch size by B and the number of sampled batches by V, and recalling that there are Nes architectures in the search space, define the ranking function variation as:
Nss
Varss(r, B,V) A
Nss Σ CV (M.(B,V) for M.(B.V) (r(arche, d=))
(1)
where r ranking function, d, batch of data of size B, uniformly sampled from the dataset associated Var(X) A higher average coefficient of variation indicates greater
with the search space SS, and CV(X) = Mean(Xy. variability with respect to the selection of imput data.
Typically, if we know that a ranking function is highly variable with respect to the input data, then this motivates us to enhance the robustness by averaging over multiple random batches. On the other hand, if a ranking function exhibits less variability, then a score can be taken from a reduced number of randomly drawn batches. This leads to faster search, because ranking function evaluation tends to be the most computationally expensive element of zero-shot NAS.
4.2 Search algorithm
Zero-shot architecture scarch uses ranking function a proxy to evaluate the quality of architecture. In order to compare two architectures, selected ranking function is evaluated both of them and the outputs of the ranking function are compared. Assuming positive correlation between accuracy and the adopted metric, the architecture with the higher corresponding metric is considered to be better. The ranking function outputs are subject to randomness, due, for example, to random architecture initialization or random selected input batch. common technique to mitigate randomness is averaging: a ranking function is evaluated multiple times on the same architocture and the output averaged over the evaluations.
Instead of averaging, the key component of our approach is statistical comparison of the architectures. We treat multiple evaluations of the ranking metric multiple observations of random variable. We then test for stochastic dominance. Viewing the ranking function metrics for two compared architectures as random variables, X and Y, we test. whether p(X > k) 2 p(Y > k) for all l (and p(X > k) > p(Y > k) for some k). This test differs from comparing the mean performance, X > Y. Stochastic dominance implies X Y, but the converse not truc. Our testing process thus targets a stricter performance discrepancy. This makes the search more effective and efficient, because we navigate towards architectures that are more likely to be genuinely superior.
4

---

Published in Transactions on Machine Learning Research (02/2025)
To perform the comparison, use the U-value from the Mann- Whitney U-test (Mann & Whitney 1947). This statistical test assesses the null hypothesis that both sets of observations are drawn from the same distribution. The alternative hypothesis (for a one-sided test) is that the random variable X is stochastically greater than the random variable Y. By comparing the Mann-Whitngy U values for the two samples, we can identify one as superior architecture. We declare such superiority only if the null hypothesis can be rejected at a predctermined significance level (e.g., 0.05). Tf this is not the case, we cannot meaningfully differentiate between the architectures in terms of predicted performance. We summarise this approach tistical maximum and statistical top-k (see Algorithm D Those procedures it- eratively search for a stochastically dom- inating maximum over the given sets of ranking functions outputs. Given that we are checking for the stochastically domi- nating maximum, the output of our pro- cedure is not permutation invariant in general. As the first example, let us con- sider two sets of scores, A and B, with A stochastically dominating B. The output of Algorithm [ will be for both inputs [A, and [B.A]. As second example, let consider two sets of scores, A and B, where neither stochastic dominates the other. For input [A, B], the output will be A. For input [B, A], the output will be B. Practically, this is equivalent to a ran- dom lie breaker. As random lie break- ers are common in search functions, we do not view permutation invariance as necessary requirement.
sta-
Algorithm 1 Statistical MAX and TOP-K pscudocode
Ensure:
Each r; is a list ranking function evaluations function STAT-MAX(M,.....
max V1 for 2, do
/* Mann-Whitney U-test */
p - SLANNWWITNEYUUAE r.)
1 Threshold a significance level */
< Threshold then
max + r
end if end for return mar end function
function (TAT (1,,,,,,,..................,,... PT)
top + rS -- PT UT for 1, do STAT-TAAX STXTTMAAX(SS,, top < top U [m] rs - rs {m} end for return top end function
Pairwise search is not the only viable de- sign option For example, Dunnett's test could be used to perform multiple com- parisons. However, our experience is that search algorithms based on multiple comparison tests are much more computationally expensive. The statistical tests also tend to impose stronger assumptions. Thus, we use pairwise search to minimise computational overhead and extend the applicability of the procodure.
In our work, we use two popular search algorithms: random search and evolutionary search. Both algorithms are casy to implement for an arbitrary scarch space and require few additional considcrations when paired with a ranking function in a zero-shol setting. For random search (Mellor el al.) 2020). we sample N architectures randomly from the search space. Then we evaluate a ranking function on each sampled architecture V times. We use the Mann- WhinnWy U-test rank the candidates. In the case of ties, we select an archilecture randomly from the tied candidates.
The REA (Real et al. 2019 evolutionary search starts by sampling population of N architectures randomly from the scarch space. During each iteration, subset of n exemplars (architectures) is randomly sampled from the population. We order the exemplars using the Mann- thinnWh U-test, with random tie- breaking. The exemplar that is first in this ordering is selected and mutated. In our experiments, we use an operator replacement mutation, so that the original exemplar and the mutated exemplar have an architectural edit distance of one. We evaluate ranking function on the mutant V times and include the mutated architecture in the population, replacing the oldest ranked exemplar. After T iterations of this procedure, use the
U-test to order the population and select the highest ranked.
The FreeREA (Cavagnero et al. 2023a) evolutionary search procedure introduces a small modification to the REA algorithm. After a subset of n exemplars is randomly sampled, two exemplars with the statistically
5

---

Published in Transactions on Machine Learning Research (02/2025)
10.0
MAS-Bench-101
10.0
Normal
(CIFR-200)
0.1
1.0
MAS-Dench-201
(CIFR-110)
MAS-Bench-201
0.1
1.0
Joraw Autoenceder
Class scane
0.01
(CFAR-100)
0.01
MAS-Bench-201
0.001
(mageNNt166 200)
0.001
MAS-Bench-201
0.0001
(NinaPro)
0,0001
MAS-Bench-3311
1e-05
(CIFAR-10)
16:06
NTK con dision number
NTK frobeniut norm
ATX mean
LGA
Bienvalue score
RetU distance
EPE EPE-NAS
Fister
Group
Seip
NTK covdition number
NTK trabenius merm
NTK mean
Elganvaize score
Relu decance
Ratter
Group
Snip
(b)
Figure 1: Ranking functions variation Varss(r,B, V) for ranking function batch size B = 64, V=10 and search space S5) on da) NAS-Bench and (b) TransN ASS-Benc--00) demonstrate that different ranking functions have considerably different variations within the search space, but a specific ranking function's variation remains similar for the different search spaces.
highest rank are selected. Both exemplars are mutated and the two mutants are included in the population. Crossover is performed by splicing together parts of the two selected exemplars. Both mutated exemplars and the resultant crossover exemplar are included into the population replacing the three oldest exemplars, which increases the exploration capabilities of the search process. We provide pseudocode for the evolutionary algorithms in Appendix B
5 Experiments
5.1 Ranking function variation
In the first experiment, we show how different ranking functions are influenced by a randomly chosen batch of data and examine how consistent this behaviour is over a variety of search spaces. A lower coefficient of variation means that a ranking function is generally more reliable, provide more consistent output, and requires fewer batches.
We measure the variation Varss(r, V) by evaluating equation | Recall that SS denotes the search space, r denotes the ranking function, B is the batch size, and V the number of evaluations. In this experiment, in order focus on the most influential source of variability the input batch we initialize each network once, before the first batch is selected. We set V 10 and set = 64. An output of ranking function is averaged over 10 runs for different random batches given the same initialisation for the network.
We present results for the MAS-Bench search spaces in Fig. la and results for the TransNAS search spaces in Fig. 1b. Overall, Figenvalue score and ReLU Hamming distance are by far the most stable ranking functions. Snip is more stable than the others. Fisher exhibits stability similar to that of Snip on the NAS-Bench search spaces, which are considered easy, but performs worse on TransNAS-Bendde The performance of Fisher and NTK-based kernels are highly dependent on the dataset used by a search space. We emphasize that low variation desirable critcrion for the ranking function selection, but does not imply high performance.
For all ranking functions, the coefficient of variation of an architecture tends decrease the average accuracy increases, although this effect is more pronounced for some ranking function and search space combinations. In general, this is result of the ranking function output varying less for the higher quality architectures. Fig. 2 presents example results for ReLU Hamming distance on NAS-Bench-101 (CIFAR-10) and Eigenvalue Score on NAS--ench-2001 JImageNet16-120)) Due to the very high variability often exhibited by poorly performing architectures, we exclude the worst worst-performing decile from the analysis, and present box plots of the coefficients of variation (for individual architectures) versus accuracy on the test set. We observe negative trend in each case, although it is much more evident for Figenvalue Score.

---

Published in Transactions on Machine Learning Research (02/2025)
0.0014-
0.006
0.0010-
0.0008-
0.004
0.0006-
0.002
0.0004
0.000
87.0
87.7
86.4
89.1
89.8
90.5
91.2
91.9 92.6
93.3
94.1
16.0
20.9
23.8
26.7
29.6
32.5
35.4
38.3
41.2
44.1
47.3
Accuracy
(a)
(b)
Figure 2: Box plot (versus accuracy) of coefficients of variation for individual architectures (B) Var(M;(B.V
of V-10 ranking function outcomes for archi- tecture areh; derived from random batches of data de, each of size B The depicted ranking functions are ReLU Hamming distance on NAS-Bench-101 (CIFAR-10) (a) and Eigenvalue Score on NAS-Bench 201 (ImageNet16-120) (b). For visualization purposes, exclude ten percent of the architectures-those that exhibit lowest accuracy.
(B.VV where M,(B, V) {r(arch;, du)]v=1
Fisher
0.03
.0.04
0.05
0.05
00.6
0.22
0.03
0003
-0.09
-0.02
EPE-NAS
Grasp
0.09
00.21
0.26
-0.22
-0.12
00007
0.10
00.9
-0.19
-0.16
NTK(Frobenius)
NTK(mean)
-0.09
-0.34
-0.29
-0.31
-0.17
-0.17
-0.27
-0.26
-0.17
-0.19
Eigenvalue score
NTK(condition number)
-0.12
.0.27
.0.17
-0.11
-0.19
00.11
00.12
-0.05
-0.17
-0.23
ReLU dist
LGA
0.25
-0.22
0.11
0.02
00.15
-0.01
0.12
0.07
Snip
-0.8
NAS-Bench-101 Moanch-10110 (CIFAR-10)
NAS- NAS- NAS-Bench-200 B---ch-hh21 (CIFAR-10)
NAS-Bench-200 (CIFAR-100)
NAS-Bench-201 ImageNet16-120))
NAS-Bench-200 200nchh-2011 (NinaPro)
PransNAS-Bench-ll (Class object)
Benh----nc--1111 -10 (Jigsaw)
TransNAS BeetMAs---Beec--aee Bench-101 (Autoencoder)
SBWWASS-Bnnh-1001 101 (Class scene)
TransNAS-Bench- 101 (Normal)
Figure 3: Kendall-7 correlation coefficient between coefficient. of variation values and validation accuracy, for each ranking function and search space. EPE-NAS and LGA require classification labels and therefore cannot be computed for TransNAS-Benchhh (Autocncoder) and TransNAS-Benchha (Normal).

---

Published in Transactions on Machine Learning Research (02/2025)
Fisher
0.27
0.26
0.25
0.27
0.17
-0.12
0.01
-0.04
0.10
0.14
EPE-NAS
0.27
0.18
-0.12
-0.06
-0.20
-0.22
0.02
-0.00
Grasp
-0.25
0.00
-0.12
0.01
-0.08
-0.01
-0.20
-0.22
0.04
-0.17
NTK(Frobenius)
0.08
0.02
0.04
0.02
-0.11
0.05
-0.17
-0.17
0.39
0.40
NTK(mean)
0.17
-0.38
-0.38
-0.27
-0.19
-0.09
-0.22
-0.21
0.22
0.23
-0.2
Eigenvalue score
0.04
-0.83
-0.84
-0.79
-0.61
-0.78
-0.73
-0.73
-0.49
-0.49
NTK(condition number)
0.36
0.01
0.02
0.13
0.37
0.18
0.23
0.24
0.35
0.32
-0.4
RelU dist
-0.27
-0.58
-0.57
-0.57
-0.59
-0.42
-0.40
-0.40
-0.14
-0.14
-0.6
LGA
-0.53
-0.62
-0.29
-0.31
-0.24
-0.24
-0.21
-0.22
Snip
0.27
-0.26
-0.11
0,08
-0.13
0.02
-0.02
-0.14
0.34
0.42
00.8
BS-BBench-101 1001 (CIFAR-10)
NAS NAS- Be-cch-hc2 (CIFAR-10)
NAS-Bench-200 (CIFAR-100)
) 120)
TransNAS Bench-111 (Class scene)
Bee---Benchh--- 101 (Jigsaw)
(NinaPro)
-0hnchh-10111 (Class object)
BeaiAs---Bnch-1111 (Autoencoder)
TransNAS-Bench 101 (Normal)
NAS NAS-Bench-201 (ImageNet16-))
SrasNAS-Bennc--e
NAS-Bench-
Figure 4: Kendall-r correlation coefficient between a ranking function coefficent of variation values and rank- ing function mean value taken over 10 evaluations, for each ranking function and search space. EPE-NAS and LGA require classification labels and therefore can not be computed for TransNAA-Benchh (Autoen- coder) and TransNAS-Bench-UD (Normal).
The negative trend suggests that we could consider directly using lower coelficient of variation as an indicative variable during the search. To further investigate this possibility, we measured Kendall-T correlation between ranking function variation and architecture accuracy (sce Fig. 3) In many cases, there strong negative correlation, but there are exceptions. For example, there very weak correlation between accuracy and the coefficient of variation of the Fisher metric. On some search spaces, LGA even exhibits positive correlation, meaning that it is, average, more unstable for the better-performing architectures. We conjecture that this behaviour arises due to the use of labels in both the LGA ranking function and the accuracy evaluation. EPE- NAS, the her ranking function that uses labels, exhibits close-to-zero (and occasionally slightly positive) correlation.
We can consider naive approaches incorporate the coefficient of variation into the search process. For example, after appropriate normalization, we could sum ranking function output with its coefficient of variation. Fig. 4 depicts the Kendall-7 correlation between the cocfficient of variation of ranking function and its mean value for different search spaces. For some ranking functions such as Eigenvalue score and ReLU distance, the magnitude of the correlation is high, meaning that the coefficient of variation does not provide much additional useful information for the scarch. By contrast, for other ranking functions such as Frobenius norm of the NTK and the condition number of NTK, the magnitude of the correlation is low. In experiments (see Table f in Appendix D we observe that the search performance improvement of our approach over this naive scheme indeed considerably greater for these ranking functions. Although a naive incorporation of the coefficient of variation can improve results of the search, its impact is inconsistent; the statistical comparison approach we propose in Section 4.2 exhibits more consistent improvement and is effective for all ranking functions.
5.2 Random search
In order to demonstrate our statistical approach, we first use a random search proposed by Mellor et al. (2020p. Results are presented in Table ! We selected Eigenvalue score, ReLU Hamming distance and condition number of NTK for this experiment. The first two serve as examples of ranking functions with low variation, while the final one exhibits high variation. To evaluate an architecture we randomly sample batch of 64 and randomly initialise architecture weights. This evaluation simulates typical case of

---

Published in Transactions on Machine Learning Research (02/2025)
Table 1: Random search on N sampled architectures with averaging (Avg) and statistic (Stat) evaluation.
Hann-Whitned U-test is used for statistical evaluation. Each ranking function is evaluated 10 times for the architecture. We provide mean values and standard deviations over 100 runs. For each pair of evaluations, the best score is highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
Eigenvalue score
ReLU dist
NTK
Search Space
Avg Stat
Avg
Stat
Avg
Stal
N= 10
NASS 1AS--Bechh-101 (CIFAR-10)
91,51+444
91.71#2.22
91.28+1.80
91.63=1.51
90.91 1.42
91.24+1.63
MAS-Bench-201 (CIFAR-10)
91.33+1.57
92.21+1.66
91.80+1.33
92.34=1.14
91.1+1966
91.92+2.15
NAS MAS-Bench-221
(CIFAR-100)
63.61
69.13+2.93
71.76+1.92
71.68+2.03
68.05+4.42
69.47+3.17
NAS
1---Bencc-221
(ImageNet 16-16-100)
40.59+5.005
41.22:t4.66
40.69
3..24+3.33
40.91
41.64+4.76
NAS-Bench-201 (NinaPro)
90.13+1.30
90.40:11.40
90.34+1.83
90.76=1.89
90.77+1335
90.9911.38
TransNAS-Bencch Bench-101 (Jigsaw)
90.72+4.55
91.88:+4.76
87.28:15.74
89.11=11.73
90.97+4..3
92.4843.18
TransNAS-Bench-JD0 (Class object)
47.33+2.47
48.26+2.84
47.65=2.50
48.71=2.69
47.91#2.11
48.48+2.46
TransNAS-Bench-101 (Class scene)
59.94.15.30
60.52.5.14
60.87.15.09
61.70.4.11
60.90113.5
61.58.1.73
N= 100
NAS-Bench-101 (CIFAR-10)
91.71:11.22
92.06:11.15
91,9812.08
91.98 2.01
89.6712..2
90.0611..98
24S-Bench-201
(CIFAR-10)
91.10+1.61
91.73+1.43
92.11
92.52+1.10
91.09+1.84
91.75+2..8
24S-Bench-201 (CIFAR-100)
68.43:2.82
69.0542.64
1.77
70.75
69.39+4.50
70.01:4..50
NAS- Bench-201 1mnageNet161222
40.3411.66
40.96:14.98
3..54
2.44
41.04:14.99
41.5011.42
NAS- 14S-Bench-201 (NinaPro)
90.00=1.91
90.22+1.86
89.18+1.72
89.53=1.55
91.29+1.00
91.36+1.055
TransNAS- 1ennhhh--1 (Jigsaw)
$9.95+5.57
90.59+4.10
90.58+3.55
85.33+2.21
92.00=2.78
91.99-2.96
TransNAS-Bench (Class object)
47.04+4.006
49.46+4.56
48.25+3.111
48.87=2.96
49.48+0.97
49.81+1.77
TransNAS-Renche (Class scene)
60.94+3.23
61.12:4.114
61.19
61.50+4.32
01.56:0.56
21.29-22.85
N= 1000
NAS-Bench-101 (CIFAR-10)
91.4+1.36
91.57:1.31
92.12+2..45
92.60=1.78
90.54+2.35
90.92-2.40
MAS-Bench-201 (CIFAR-10)
91.25:11.6
92.08:1.64
92.04:1..22
92.69
91.0011..07
91.8812.16
NAS- MAS-Bench-201 (CIFAR-100)
69.32.13.1
70.63.1.68
70.78.1..66
71.52
69.8311..2
70.4012.55
MAS-Bench-201 (ImageNet66-12)
41.4214.56
42.17.1.111
42.9612..78
43.79
41.5911.41
42.2412.03
NAS-Bench-201 (NinaPro)
90.59-1..73
90.6112.19
90.47:1.25
J0.2111.34
91.49:1.65
91.5710.89
TransNAS 10n (Jigsaw)
88.63:+4.22
90.81+3.93
90.60:t3.00
88.52+11.35
92.40+0.98
92.57+1.51
(Class object)
44.6413..2
45.46:14.21
44.99:3.331
45.82:1..77
44.98111.15
45.36
TransNAS- TransNAS-Bench-101 Bench-101
(Class scene)
61.42.13.37
61.5013.55
61.4713.09
61.7614.30
61.74.10.43
62.29
Table 2: Evolutionary search results. Results with averaging (Avg) and statistical (Stat) ovaluation are provided.
U-test used for the statistical evaluation. Each ranking function evaluated times for the architecture. For each evaluation pair, the best score highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
Eigenvalue score
ReLU dist
Ensemble
Search Space
Search Alg.
Avg
Stat
Avg
Stat
Avg
Stat
Greedy
92.76:10.00
92.86:10.66
92.3610.31
92.5410.59
92.54+1.01
92.82110777
NAS-Bench-101
(CIFAR-10)
REA
93.02+0.32
93.11+0..30
93.15120.15
93.31+0.09
92.99-0.42
93.28-:0.25
FreeREA
93.2311.47
93.51
93.29.10.58
93.4610..33
93.32.10.53
93.52.10.38
Greedy
09.54+0.13
70.01=0.42
70.00+0.03
70.06=0.02
71.03+0.46
71.12#0.58
NAS-Bench-201
(CIFAR-100)
REA
71.64+0.80
72. 72.14+0.69
71.83+0.61
72.25+:0.44
72.06+00.6
72.40++0.75
FreoREA
71.98:0.26
73.13-10.07
71.6311.35
72.4311.04
71.80-10.97
72.15:10.76
NAS-Bench-201
Greedy
42.68+
44.0
44.78+1.34
45.90+10.71
1..11
45.21+0.80
(ImageNNet16-1200
REA
44.90+0.76
45.18:10.66
43.82 13.82+1.53
44.4511.06
04.23:10.84
44.76:10.94
FreeREA
1..8441.17
45.52-10.7
43.82+1.23
44.38+0.92
44.26+1.46
45.22=0.77
Greedy
92.49:1..11
93.68.10.c
92.23.10.4
92.98 1..69
93.06
94.29.1.44
TransNAS- PransNAS-Benchh100
(Jigsaw)
REA
91.88.10.31
00.25
92.12.10.39
93.29 29..2..0.299
93.80.10.41
95.06
FreeREA
91.79+00118
93.26++0.11
92.03++0.17
92.97+0.18
93.42+0..8
94.99+0..58
Tra Bench-101 10 (Class object)
Greedy
43.89.1.73
45.16.11.4
46.04.1.007
46.0110.00
46.2013.34
47.1911.112
REA
46.10-0.09
46.4410.07
45.99-10.09
46.86:10.14
46.26-1.08
46.52-10.20
FreeREA
46.7340.09
46.8110.08
46.97-0.06
46.97-0.07
47.09-0.11
47.1440.09

---

Published in Transactions on Machine Learning Research (02/2025)
Table 3: Experiemental results on SWAPNAS, MeCo, SynFlow and LogSynFlow for evolutionary search. Results with averaging (Avg) and statistical (Stat) evaluation are provided. Mann-White Sann-Whitney U-test used for the statistical evaluation. Each ranking function evaluated 10 times for the architecture. For each evaluation pair, the best score is highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
NAS-Bench-IO 101 (CIFAR-10)
NAS- Ben--Benc-222 (ImageNet Net1-22)
Ranking function
Method
Avg
Stat
Avg
Stat
REA
93.05+00.12
93.37+0.11
44.39+00.98
45.74+1..2
SWAPNAS
FreeREA
93.42=#0.36
93.71+0.32
44.75=11.15
45.89+1.00
REA
93.13+0.54
93.5210.44
42.47=20.84
42.81=0.81
McCo
FreeREA
93.21+00.45
93.51+0.39
42.88+00.79
43.23+0.85
REA
93.69=0.38
93.5610.31
44.29#1.02
44.57=0.99
SynFlow
FreeREA
93.80=0.24
93.74+0.32
44.9810.89
44.74=1.21
REA
93.76-0.36
93.6210.28
45.0310.82
44.91
LogSynFlow
FreeREA
93.7640.25
93.77+0.36
45.06+0.90
45.16+0.95
ranking function usage. A ranking function is evaluated ten times every queried architecture. In order to reduce the number of experiments we do not test combinations of ranking function. We provide results for averaged rank value and for the proposed statistical ranking approach. The 5% significance level is used for rejecting the null hypothesis when conducting the Mann- Whan-Whitncy U-test. We repeat each experiment 100 times, computing the mean value of the accuracy for the selected architecture and its variation. Our findings demonstrate that our statistical approach a better way to use the multiple outcomes than simple averaging. As we can see in Table [ the proposed statistical method leads to improved performance for almost every ranking function and search space. The average accuracy improvement is 0.49. The improvement is small, but there is negligible additional computational overhead. Our experiments do not expose a significant difference between the improvement for low- versus high-variance ranking functions. We observed that the largest search improvement is achieved on the NAS-Bench-201 search spaces, but that could be due to the fact that those search spaces are small. Less improvement is observed for the largest search space 1AS-Bench-101 (CIFAR-10).
5.3 Evolutionary search
We also compare the performance of the standard averaging approach with that of the proposed statistical evaluation when cach is used in conjunction with evolutionary scarch. As before, the 5% significance level is used for rejecting the null hypothesis of the Mann-Whilney U-lest. We apply caching for both approaches. In the case of averaging, we cache the average of the ranking function output over 10 evaluations. For the statistical evaluation we cache the individual outcomes of the 10 ovaluations. Whenever two architectures are statistically compared, we store the outcome, that the procedure does not need to be repeated.
Table 2 presents the evolutionary search results on the NAS-Bench and TransNAS-Bench search spaces. We demonstrate results on Eigenvalue score and ReLU Hamming distance. We also include an ensemble of those that formulated as a sum with components individually MinMax normalized over the observed architecture ranks. We observe that statistical evaluation consistently improves the search quality. Although the particular improvement depends on the combination of the search space and ranking function, we did not observe case where applying statistical evaluation leads to poorer search result. We do not observe a significant difference between the improvement for low- versus high- high-variance ranking functions. In our experiments with cvolutionary scarch, Eigenvalue score (low variance) has the average improvement of 0.73, whereas for RELU dist (high variance) the average improvement. is 0.60. We observed that FreeREA demonstrates the best results in most cases, thus emphasising the importance of crossover in evolutionary search. However, the averaging case the difference between FrecREA and REA is typically less than one standard deviation. This may make REA more suitable for some practical applications as it requires only to define a mutation operation. FreeREA experiences the largest performance increase with statistical
10

---

Published in Transactions on Machine Learning Research (02/2025)
evaluation, and clearly outperforms REA. In some cases, observed that the greedy algorithm outperforms the others. It is not an expected outcome, but we assume it is due to randomness of the experimental setup. Similar to other zero-shot works (Cavagnero et al. 2023a, Wang et al.) 2024), our experiments demonstrate that evolutionary search is more stable and efficient than random search. The only search space where random and evolutionary search exhibit similar performance is TransNAS-Bench-100.. and we attribute this to the extremely small size of this search space (sce Appendix A
In Table we demonstrate that our approach is generalisable to more recently proposed ranking functions. SWAPNAS (Peng al.) 2024) and MeCo (Jiang et al.) 2024) are Zero-Shot ranking functions that aim to achieve the highest correlation with the accuracy of the architecture in the NAS-Bench scarch spaces. Table 3 shows that the proposed methodology can easily be adapted to the new ranking functions. In addition, we provide results on alta-agnostic SynFlow (Abdelfattah et al., 2021) and LogSynFlow (Cavagnero et al, 2023a). Unlike any other ranking functions presented this paper, the variation of SynFlow and LogSynFlon is induced only by random initialisation of the evaluated architecture. The data-agnostic approaches present challenge for our statistical evaluation. Averaging demonstrates performance comparable or higher to that of our statistical evaluation on them. More results for SWAPNAS, MeCo, SynFlow and LogSynFlow are demonstrated in the Appendix C
6 Conclusion and Future work
In this work, we proposed a statistical approach for comparing architectures during a NAS zero-shot search procedure. Through experiments using both random and evolutionary search, we provided evidence that the proposed approach leads to better search results than simply averaging the outcomes of a batch of evaluations. We also investigated the variation of a wide selection of zero-shot ranking functions for several search spaces and observed that those which exhibit less variability tend to produce better and more stable search outcomes. Given these observations, we can recommend that zero-shot search is conducted using statistical architccture comparison.
Every ranking function evaluation for a given architecture can be considered equivalent to sampling from the distribution. In our work, we handled such sampling with statistical testing in order to retain compatibility with the existing pipelines and scarch agorithms. Formulating a zcro-shot neural architecture scarch as a stochastic optimisation problem that interprets the output of a ranking function not as score, but distribution could be potential research direction.
We have observed that the statistical method does not consistently benefitial for data-agnostic SynFlow and LogSynFlow, while their performance is competitive with other ranking functions discussed in the paper. This suggests that an alternative strategy to the statistical approach is to develop techniques that are minimally affected by the data batch and initialisation.
An additional important source of performance variability that we have not discussed is the search space. Our experiments show that the suitability of ranking function is highly dependent on the search space. For one search space, particular ranking function might be the best choice; on different search space, it might perform poorly. Due to this variability, we cannot predict how our conclusions will generalise to a new search space.
References
Mohamed S. Abdelfattah, Abhinav Mehrotra, Fukasz Dudziak, and Nicholas D. Lane. Zero-Cost Proxies for Lightweight NAS. In Proc. Int. Conf. Learn. Representations (ICLR), May 2021.
Yash Akhauri, Pablo Munoz, Nilesh Jain, and Ravi Iyer. Evolving zero cost proxies for neural architecture scoring. arXiv preprint ar arXiv:2209.074118, Dec. 2022.
Manfredo Atzori, Arjan Gijsberts, Simone Heynen, Anne-Gabriella Mittaz Hager, Olivier Deriaz, Patrick Van Der Smagt, Claudio Castellini, Barbara Caputo, and Henning Müller. Building the NinaPro database: A resource for the biorobotics community. In Proc. IEEE Int. Conf. Biomed, Robot. Biomechatronics (BioRob). TEFE, Jun. 2012.
11

---

Published in Transactions on Machine Learning Research (02/2025)
Niccolò Cavagnero, Luca Robbiano, Barbara Caputo, and Giuseppe Averta. FreeREA: Training-fri -free evolution-based architecture search. In Proc. IEEE Winter Conf. Appl. Compul. Vis. (WACV), Jan. 2023a.
Niccolò Cavagnero, Luca Robbiano, Francesca Pistilli, Barbara Caputo, and Giuseppe Averta. Entropic Score metric: Decoupling topology and size in Training-free NAS. In Proc. Int. Conf. Compud. Vis. (ICCV), Oct. 2023b.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang- Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. In Proc. Int. Conf. Learn. Representations (ICLR), May 2021.
Patryk Chrabaszez, llya Loshchilov, and Frank Hutter. A downsampled variant of imagenet alternative to the cifar datasets. arXiv preprint 1xXi::107.0880 08819, Jul. 2017.
Xuanyi Dong and Yi Yang. NAS-Bench-201. Extending the scope of reproducible neural architecture search. In Proc. Int. Conf. Learn. Representations (ICLR), May 2019.
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li. TransNAS. bench-101: Improving transferability and generalizability of cross-task neural architecture search. In Proc. IEEE Conf. Comput. Vis. & Pattern Recoguit. (CVPR), Jun. 2021.
Charles R Harris, K Jarrod Millman, Stéfan J Van Der Walt, Ralf Gommers, Pauli Virtanen, David Cour- naреau; Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J Smith, et al. Array programming with NumPy. Noture, Sep. 2020.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Adv. Neural Inf. Process. Syst. (NeurIPS), Dec. 2018.
Mojan Javaheripi, Gustavo de Rosa, Subhabrata Mukherjee, Shital Shah, Tomasz Religa, Caio Cesar Teodoro Mendes, Sebastien Bubeck, Farinaz Koushanfar, and Debadeepta Dey. siteerransfoneeSSaarcc Training-free Neural Architecture Search for efficient language models. In Adv. Neural Inf. Process. Syst. (NeurIPS), Nov. 2022.
Tangyu Jiang, Haodi Wang, and Rongfang Bie. MeCo: Zero-Shot NAS with one data and single forward pass via minimum cigenvalue of correlation. In Adv. Neural Inf. Process. Syst. (NeurIPS), Dec. 2024.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, U. Toronto, 2009.
Jachoon Lee, Lechao Xiao, Samuel Schocnholz, Yasaman Bahri, Roman Novak, Jascha Sohl-Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Adv. Newral Inf. Proc. Syst. (NeurIPS), Dec. 2019.
Guihong Li, Yuedong Yang, Kartikeya Bhardwaj, and Radu Marculescu. ZiCo: Zero-shot nas via inverse coefficient variation on gradients. In Proc. Int. Conf. Learn. Representations (ICLR), Apr. 2022.
Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xinyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen- NAS: A Zero-Shot NAS for high-ppeffrmance deep image recognition. In Proc. Int. Conf. Comput. Vision (ICCV), Oct. 2021.
Vasco Lopes, Saeid Alirezazadeh, and Luís Alexandre. EPE-NAS: Efficient performance estimation without training for neural architecture search. In Proc. Int. Conf. Artif. Neural Netw. (ICANN), Sep. 2021.
Henry B Mann and Donald R Whitney. On test of whether one of two random variables is stochastically larger than the other. Ann. Math. Statist., 18:50-60, Mar. 1947.
Yash Mchta, Colin White, Arber Zela, Arjun Krishnakumar, Guri Zabergja, Shakiba Moradian, Mahmoud Safari, Kaicheng Yu, and Frank Hutter. Nas-bench-suite: Nas evaluation is (now) surprisingly easy. In Proc. Inl. Conf. Learn. Representations (ICI.R), Apr. 2022.
12

---

Published in Transactions on Machine Learning Research (02/2025)
Joe Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley, Neural Architecture Search without training. In Proc. Inl. Conf. Mach. Learn. (TCML), Jul. 2021.
Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J Crowley. Neural architecture search without training. arXiv preprint ar Xrv:20006.00 0464704 7e1, 2020. URL
1ttp://aabb/0000044441
Jisoo Mok, Byunggook Na, Ji-Hoon Kim, Dongyoon Han, and Sungroh Yoon. Demystifying the neural tangent kernel from a practical perspective: Can it be trusted for neural architecture search without training? In Proc. IEEE Conf. Comput. Vis. & Pattern Recognät. (CVPR), Jun. 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeminng Lin, Natalia Gimelshein, Luca Antiga, et al. PyTorch: An imperative style, high-performance deep learning library. In Adv. Neural Inf. Process. Syst. (NewrIPS), Dec. 2019.
Yameng Peng, Andy Song, Haytham M. Fayck, Vic Ciesiclski, and Xiaojun Chang. SWAP-NAS: Samplo-wisc activation patterns for ultra-fast NAS. In Proc. Inl. Conf. Learn. Representations (ICLR), 2024.
Estcban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Lc. Regularized evolution for image classifier architecture search. In Proc. Conf. Artif. Intell. (AAAI), Jan. 2019.
Pavel Rumiantsev and Mark Coates. Performing neural architecture search without gradients. In Proc. IEEE Int. Conf. Acoust. Speech, Signal Proc. (ICASSP), Jun. 2023.
Aaron Scrianni and Jugal Kalita. Training-fros free neural architccture search for RNNs and transformers. In Proc. Annu. Meeling Assoc. Comp. Linguistics (ACL), Jul. 2023.
Hidenori Tanaka, Daniel Kunin, Danicl L. K. Yamins, and Surya Ganguli. Pruming neural networks without any data by iteratively conserving synaptic flow. In Adv. Neur. Inf. Proc. Syst (NeurIPS), Dec. 2020.
Renbo Tu, Nicholas Roberts, Misha Khodak, Junhong Shen, Frederic Sala, and Ameet Talwalkar. NAS- Bench-360: Benchmarking neural architecture search on diverse tasks. In Adv. Neural Inf. Process. Syst. (NeurIPS), Nov. 2022.
Jack Turner, Elliot Crowley, Michael O'Boyle, Amos Storkey, and Gavin Gray. Blockswap: Fisher-guided block substitution for network compression on a budget. In Proc. Int. Conf. Learn. Representations (ICLR), Jul. 2020.
Pauli Virtanen, Ralf Gommers, Travis Oliphant, Matt Haberland, Tyler Reddy, David Cournapean, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. SciPy 1.0: fundamental algorithms for scientific computing in python. Nature methods, Feb. 2020.
Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by prescrving gradient flow. In Proc. Inl. Conf. Learn. Representations (ICLR), Jul. 2020.
Yan Wang, Liangli Zhen, Jianwei Zhang, Miqing Li, Lei Zhang, Zizhou Wang, Yangqin Feng, Yu Xue, Xiao Wang, Zheng Chen, et al. MedNAS: Multi-Scale Training- Free Neural Architecture Search for medical image analysis. IEFE Thans. Evol. Comput., Jan. 2024.
Huan Xiong, Lei Huang, Mengyang Yu, Li Liu, Fan Zhu, and Ling Shao. On the number of linear regions of Convolutional Neural Networks. In Proc. Int. Conf. Mach. Learn. (ICML), Jul. 2020.
Jingjing Xu, Liang Zhao, Junyang Lin, Rundong Gao, Xu Sun, and Hongxia Yang. Knas: green neural architecture search. In Proc. Int. Conf. Mach. Learn. (ICML), Jul. 2021.
Longxing Yang, Yanxin Fu, Shun Lu, Zihao Sun, Jilin Mei, Wenxiao Zhao, and Yu Hu. Sweet Gradient matters: Designing consistent and efficient estimator for Zero-shot Architecture Search. Neural Netu., 168:237 255, Nov. 2023.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. NAS-Bench- 101: Towards reproducible neural architocture search. In Proc. Int. Conf. Mach. Learn (ICML), Jun. 2019.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Amir R. Zamir, Alexander Sax, William Shen, Leonidas J Guibas, Jitendra Malik, and Silvio Savarese. Taskonomy: Disentangling task transfer learning. In Proc. IEEE Conf. Comput. Vis. & Pattern Recognäl. (CVPR), Jun. 2018.
A NAS search space benchmarks
NAS-Bench-10h Ying et al. (2099] includes the performance and training statistic of the 423k architectures CIFAR-10. It. has three cells. Each cell containing nodes each with pool of operations consists of: "3x3 conv", "1x1 conv" and "3x3 max-pooling..
MAS-Bench-2000 (Dong & Yang, 2019 has 15625 architectures in the search space and provides performance for CIFAR-10, CIFAR-100, and ImageNet-16-122
It has 5 cells. Every cell has 4 nodes. The list of operations includes "zeroize", which is equivalent to cutting the connection, "skip connection", "3x3 conv", "Ixl conv" and "3x3 avg-pooling". This the most popular benchmark as it is relatively small and contains measurements for several datasets. AAS-Bench-360 (Tu et al. 2022) extends this benchmark by additional datasets. In this work, we are using the NinaPro DB5 dataset from NAS- MAS-Bench--36. For consistency, we refer to it as JAS-Bench-200 (NinaPro).
TransNAS A.S-sNASSBBES -S--ench--1-11 (Duan et al., 2021 is tabular benchmark that consists of two search spaces evaluated on seven tasks. The architecture of the neural network in the benchmark is a composition of a searchable encoder and a decoder tailored to specific tasks. The macro search space suggests searching for the number of blocks, the size for downsampling, and the count of output channels per block. The micro search space composed of four nodes, similarly to NAS-Bench-201. Four operations are used: "zeroize", "skip connection", "3x3 conv block" and "Ixl conv block", where every convolution block is a sequence of ReLU, convolution, and batch normalisation. In our project, only using the micro search space that consists of 4096 graphs.
B Evolutionary search algorithms
Here we present pscudocode for all evolutionary algorithms used in this project. Since the greedy evolutionary algorithm and FreeREAA primarily based on REA, we provide full pseudocode for REA (see Algorithm 2 and parts that are different for FreeREA (see Algorithm 4 and greedy evolutionary search (see Algorithm 3 The core notation for all the algorithms is chosen to be close to REA notation, presented by [Real et al. (2019). For the standard implementation, the highest ranked candidate and the top-2 are computed by maximizing over the averaged ranking function output. For our implementation, we use statistical comparison with stat-max and stat-top-2 from Algorithm [
We designed greedy evolutionary search algorithm in order to further demonstrate how ranking function variance influences evolutionary search algorithm performance. The primary difference between greedy evo- lutionary search and REA lies in the mutation operation. Instead of randomly mutating parent candidate as in REA, it greedily explores a list of all possible mutations. Therefore, it is expected to experience a greater impact from the variance introduced by ranking function.
In all our experiments, we are utilising an ovaluation budget (C at line 9 of Algorithm 2 that defines how many architectures can be evaluated in total. As one can see, the three evolutionary algorithms are spending the budget different rates. REA evaluates single candidate per iteration. FreeREA evaluates three and greedy scarch evaluates all the mutations (i.c., the neighbourhood the scarch hypergraph).
C Additional experiments with ranking functions
In this section, we present an evaluation with SWAPNAS Peng et al. 2024), MeCo (Jiang et al. 2024 SynFlow (Abdelfattah et al. (201)) and LogSynFlow (Cavagncro et al. 2023a). SWAPNAS and McCo are recent Zero-Shot ranking functions that aim for the highest correlation with the architecture accuracy the NAS-Bench search spaces. SynFlow and LogSynFlow are data-agnostic ranking functions. Due to
14

---

Published in Transactions on Machine Learning Research (02/2025)
Algorithm Regularised evolutionary algorithmi (REA)
1: population t-O
2: history t-
3: while |population] < do arch + ARCHSAMLE()
Initialize population of size P Randomly sample archilecture
rank EvALARcH(arch)
Evaluate ranking function for architecture
history < history U f(arch, rank))
population < population U ((arch;rank))
8: end while
9: while |historyl < C do
> Evolve for C cycles
10: random_ random_candidates candidates +- 0
11: for 1, do
12:
condidate RANDoM(population)
Sample random element from population
13:
random random_candidates candidates U {candidate)
14: end for
15:
parent +- highest rank candidate out of random random_ccadiiatee condidates
16:
child + MUTATE(parent)
Sample one of all possible mutations Evaluate ranking function for the child
17:
rank + EVALARCH(child)
18:
history < history U {(child, rank)]
19:
population < population {(hiild rank))
20: remove the oldest. member of the population
21: end while
22: best + highest rank candidate out of history
23: return best
Algorithm 3 Greedy evolutionary search algorithm difference with Algorithm 2
15: parent + highest rank candidate out of caaddom_annddattes
16: children +- MuparEAAu.pparet)
b Get list of all possible mutations
17: child + highest rank candidate out of children
Evaluate all children and get the highest rank 19: add all mutations and their respective ranks to the history
18: rank <- FvvI.ArcHcchill
/* Proceed to line 19 of Algorithm 2 *
Algorithm 4 Free regularised evolutionary algorithm (FreeREA) difference with Algorithm
15: parenti, parenty < top-2 highest rank candidates out of random_candidan
16: child, + MUTATE(parentt)
17: rank; + (VALARCH(childd)
18: child2 +- MUTxTT((parenta)
19: ranka + EvALARch(childd))
20: child3 CRossovER(pareentt,pon
Perform crossover between two parents' genes
21: rank; +- EVALARCH(
22: history +- history U (child), (child2, rank2), (childz, ranks)}
23: population + population U ((child, ranki ), (child2, rank2), (childs, rank3)}
24: remove top-3 the oldest member of the population
* Proceed line 21 of Algorithm
15

---

Published in Transactions on Machine Learning Research (02/2025)
Table 4: Evolutionary search on SWAPNAS and MeCo. Results with averaging (Avg) and statistical (Stat) evaluation provided. Mann-Whitne, U-test is used for the statistical evaluation. Each ranking function is evaluated 10 times for the architecture. For each evaluation pair, the best score is highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
SWAPNAS
McCo
Search Space
Search Alg.
Avg
Stat
Avg
Stat
NAS-Bench-101
REA
93.05 12
93.37 H..1
93.13+0.54
08.52-00.44
(CIFAR-10)
FreeREA
93.42+10.36
93.7110.32
93.21+0.45
93.51=:039
NAS-Bench-201
REA
71.77=00.49
72.54+0.56
71.31+1.37
71.54+1.11
(CIFAR--100)
FreeREA
71.70+1.02
72.81+0.98
71.8
71.86+00.99
NAS-Bench-201
REA
44.39++0.98
45.74+1.22
42.47+0.84
42.81+0.81
(ImageNet16-12)) 120)
FreeREA
44.75:t1.15
45.89-11.01
42.88:10.79
43.23
TransNAS AaannnnhS-Beech----- 101
REA
92.3610.44
93.1710.30
92.43:10114
93.64=0.13
(Jigsaw)
FreoREA
92.29+0.18
93.04+0.21
91.68+0.20
93.55+00.09
TransNAS MaansNAS-BBech----
REA
45.96+0.11 46.80=0.12
46.73+0.09
46.99
(Class object)
FreeREA
47.01+0.07
47.09+00.5
46.60+00.10
47.11+0.12
Table 5: Evolutionary search on SynFlow and LogSynFlow. Results with averaging (Avg) and statistical (Stat) evaluation are provided. Mann-Whitney U-test is used for the statistical evaluation. Each rank- ing function is evaluated 10 times for the architecture. For each evaluation pair, the best score is high- lighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
SynFlow
LogSynl low
Search Space
Search Alg.
Avg
Stat
Avg
Stat
NAS-Bench- (CIFAR-10)
REA
93.69-0.38
93.56+10331
93.76+0036
93.62=00228
FreeREA
93.80-10224
93.74400.2
93.76-10.25
93.77-0..36
NAS-Bencc-201 (CIFARR-100
REA
0..52
71.34+0.47
71.94+0.50
71.53
FreeREA
71.62:10.73
72.4641.04
72.2310.68
73.14+0.39
NAS-Bench-201
REA
44.29+1.02
44.57:0.99
45.03+0.82
44.91+1.04
(1mageNee16-120)
FroeREA
44.98+0.89
44.74+1.21
45.06+00.00
45.16+10.95
TransNAS-Benchh.
REA
91.8440.117
92.7110.44
91.92+0.33
92.49+00.28
Jigsaw)
FreeREA
91.46+0.22
92.2210.53
91.464:.20
91.89::0.62
TransNAS AS---AA-----eeehh
REA
46.5110.03
46.8210.10
46.5010.06
46.82+0.10
Class object)
FreeREA
46.75+0.00
47.12+0.05
46.66+00.0
47.03+0.09
16

---

Published in Transactions on Machine Learning Research (02/2025)
Table 6: Random search on N sampled architectures; coefficient variation (CV) is used as a ranking function. Statistical evaluation of the ranking function (Stat) is provided for the reference. Each ranking function is evaluated 10 times for the architecture on a batch of 64, We provide mean values and standard deviations over 100 runs. Each ranking function is evaluated 10 times for the architecture. For cach pair of results, the best score is highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
Eigenvalue score
ReLU dist
NTK(cond)
Search Space
CV
Stat
CV
Stat
CV
Stat
N= 10
NAS- MAS--Benh--10 (CIFAR-10)
91.30+3.04
91.71+2.22
91.74+1.74
91.63+1.51
91.15+1.68
91.24=1.65
NAS-Bench-201 (ImageNet66-120)
39.58.16.11
41.22.14.66
37.02.15.80
41.24.3.33
42.59
41.64.14.76
TransNAS-Bench-- 101 (Class object)
47.2415.00
48.26:12.44
48.72:12.32
48.7112.69
46.72:5.44
48.48-2.48 2.46
N= 100
105 (0)
91.36+1.56
92.06:11.15
91.61122.68
91.98:12.01
90.18+1. 1.83
90.06 1.98
NAS- NAS-Bench-201 (ImageNett66 Net 120)
35.98:5.59
40.96-14.99
35.97
43.34:12.47
38.21
41.50
4.42
1ransNAS-Bencc-101 1ench-101 (Class object)
43.27:16.20
49.46 14.56
45.3016.37
48.87.12.99
48.2412.77
49.81
1.77
N 1000
WAS-Bench-Ie (CIFAR-10) 10)
91.21+1.51
91.57+1.33
92.64+1.51
92.60+1.73
89.04+1.89
90.92-2.40
NAS- AAS-Bench-201 (ImageNet 16- 120)
35.26+5.50
42.17+4.11
35.51+5.35
43.79-22.92
35.
42.24-2.00
CBassNAS-Bench-Dl (Class object)
44.79:16.22
46.46:14.21
47.3913.83
47.82:15.97
45.20:16.40
49.36=0.89
constant input, SynFlow and LogSynFlow have no randommess induced by the input, therefore, resulting in less overall variation. Note, however, that there still variation due to the initialization of the architecture. We present evolutionary search results for averaging over = 10 evaluations and the batch size B 64 for SWAPNAS and McCo. We used REA and FreeREA evolutionary search algorithms for these experiments. For statistical evaluation with Algorithm | the
U-test is used with the confidence threshold set to 0.05. In Table | we present the means and standard deviations for SWAPNAS and MeCo calculated over 10 runs. These results show that the proposed methodology can easily be adapted to recently published ranking functions that exhibit high correlation with architectural accuracy. The proposed statistical approach outperforms all but one setting, with statistical significance in several cases. In Table 5 we present the means and standard deviations for SynFlow and LogSynFlow calculated over 10 runs.
We see that the statistical approach is not consistently advantageous for these data-agnostic approaches. This is in part due to the reduction in variability by the removal of dependence on the data batch. A secondary factor is that with the existing (author-provided) implementations of SynFlow and LogSynFlow we observe occasional dramatic lutliers due to gradient explosion for some initializations. This could potentially be addressed by an alternative implementation. When these outliers arise, both the statistical and averaging approaches can become equivalent to a random architecture selection, inhibiting the effectiveness of the search. Since SynFlow and LogSynFlow are competitive with other ranking functions that we present in the paper, this suggests that an alternative strategy to the one we present in this paper is to develop techniques that are minimally affected (or even not affected) by the data batch and initialisation.
D Coefficient of variations as ranking function
A naive way to incorporate coefficient of variation into the scarch process is to utilise it ranking function. Given a ranking function r(arch, d) we construct coefficient of variation estimator as
lavcarch, D)- = Mean(M) + CV(M) for = fr(arch, do)
(2)
where dy is a batch of data and CV
Var(X) Mx)
As shown in Fig. 3 the ranking function coefficient of variation exhibits considerable Kendall-r correlation with accuracy. Moreover, in almost all cases this correlation is negative, which makes cocfficient of variation suitable ranking function for many metrics.
17

---

Published in Transactions on Machine Learning Research (02/2025)
-1
Accuracy
-2
NAS-Bench-101 (CIFAR-10)
NAS-Bench-201 (CIFAR-100)
NAS-Bench-201 (ImageNet16-120)
TransNAS-Bench-101 (igsaw)
TransNAS-Bench-101 (Class object)
0.010
0.025
0.050
0,075
0.100
Threshold
Figure 5: Significance level ablation of the p-value threshold. The Eigenvalue score is used with FreeREA search algorithm. The accuracy presented with respect to the accuracy of 0.05 threshold (see Table 2).
To explore this further, we conduct an experiment for several scarch spaces whore we use random search and sample N architectures. To stabilize search performance, we use Min-Max normalization individually for the mean term and the CV term when computing rov in equation
We demonstrate some results in Table Although in cases on NAS-Bench-101 rev exhibits perfor- mance comparable to statistical evaluation, its performance is consistently worse other search spaces, in some cases by a considerable margin. In many cases, modification of the ranking function is harmful to performance compared to simply using the mean. We attribute this to the correlation between the coeffi- cient of variation and a ranking function averaged value (see Fig. +. We have noticed that the Kendall-r correlation between the coefficient of variation of a ranking function and mean value is the highest for the low-variance ranking functions that are the most suitable for zero-shot search (see Fig. 4 For those ranking functions, the coefficient of variation does not provide much additional useful information for the search, but can introduce additional variability, thus making the results inconsistent.
E Significance level ablation
the main body of the article we use the siguificance level of 0.05 for the Algorithm threshold. This value was selected as the most commonly used for statistical testing. However, this threshold is a hyperparameter that can be optimised. Fig. shows that the optimal threshold lies within the range from 0.025 to 0.075. The lower threshold seems to be excessively stringent, resulting in reduced performance. Conversely, the higher threshold is overly lenient, permitting false cases of stochastic dominance.
F Caching in the evolutionary search
We would like to demonstrate the importance of caching. Unlike random search, where all architectures are sampled once, in evolutionary search, the same architecture can be encountered multiple times due to mutation crossover. Due to the variations in the ranking function output, reevaluation of previously encountered architecture can lead to performance degradation in the search. We demonstrate this in Table 7 We report mean values and standard deviations for accuracies over 10 runs. A randomly sampled batch of 64 with randomly initialised architecture weights is used to evaluate an architecture. In the case of caching, we evaluate the architecture only once, when is first encountered, and then save the ranking function output. Subsequently, if the architecture encountered again, the cached value of the ranking function used in comparisons. In the 'on-the-fly fly' alternative, the architecture is reevaluated every time it is encountered. We evaluate architecture with ranking function 10 times and average the outputs in
18

---

Published in Transactions on Machine Learning Research (02/2025)
Table 7: Accuracy comparison between cached rank mapping (Cached) and computation on-the-fly (On-the- fly). Variation of ranking function inftuence on deviations over 10 runs. For each comparison pair, the best score is highlighted in bold; if the higher score is statistically significant with p-value below 0.05, it is highlighted in bold underlined.
101/ We provide mean values and standard
Eigenvalue score
ReLU dist
Search Space
Search Alg.
Cached
Hybrid
On-the-By
Cached
Hybrid
On-the-fl
N0S-Bench-201
Greedy
92.76=0.900
92.1241.11
92.30-0.90
92.36=0.31
91.65:14.29
91.911388
(CIFAR-10)
REA
93.02=0.32
92.56:2.88
91.98=4.11
93.15=0.15
91.77+1.45
90.7444.21
FreeREA
93.23+0.47
1..5
92.43+2.09
93.29=0.58
91.94+4.02
91.2747.50
Greedy
69.54#1.01
17.21+1.48
65.42=1.37
70.00=0.03
66.90#1.78
65.8342.11
NAS-Bench-201
(CIFAR-100)
REA
71.54+0.80
67.64+1.09
67.42=1.37
71.83=0.61
67.95+1.07
68.02+1.50
FreeREA
71.98+0.26
19.43+1.03
69.44+1.10
71.63=1.35
18.44+1.40
1..89+1.42
Greedy
42.68+1.00
39.68+4.40
41.14#3.29
44.78
41.75=t5.22
42.54+4.75
NAS-Bendh-201
(ImageNet166120)
REA
04.90+0.76
43.51 24.22
43.55=t4.71
43.82
1.53
42.12
41.3447.19
FreeREA
44.84:1..17
42.33:1..52
5..62:15228
43.82 1.23
42.71122.0
42.5815.24
both cases. In addition, we introduce 'hybrid' method where evaluations are accunulated. The first time we encounter an architecture, we add 10 evaluations. Every subsequent time an architecture is encountered, three new evaluations search. To consistently compare evolutionary algorithms, we use an evaluation budget and cap it at 1000 evolution cycles. We would like to highlight that we limit the number of evolution cycles and not the number of architecture ovaluations (sec line 21 of Algorithm 2 In this setting, REA has no exploration advantage over Greedy search, which evaluates significantly more architectures per cycle. Both methods explore a similar number of architectures, because the search process of REA is more effective.
added. Thus, our setup is similar to the most typical case of evolutionary
In addition to REA and FreeREA evolutionary searches, we also report results for a greedy evolutionary search. It is similar to REA, but evaluates all possible mutations of the sampled exemplar architecture and selects the best according to the ranking function value. We specially designed it to exclude the randomness introduced by the mutation process. Greedy evolutionary search is only used for benchmarking purposes and is impractical in a real-world setting. See Appendix
B for details.
We observe that caching, which is typically applied primarily with the motivation of reducing computational overhead, always improves the search performance. Morcover, caching makes the results more stable in the majority of the cases, i.e., reduces the standard deviation. We conjecture that this performance improvement arises because the use of caching means that previous search decisions of 'on-the-fly' evaluation, the search can initially decide that an architecture is inferior, but then reverse that decision when the architecture is encountered second time. That can be clearly seen for a greedy evolutionary search, which is designed to maximise the number of re-evaluations. The 'hybrid' approach improves the stability, but results in poorer performance compared to the 'cached' approach. The efficiency of the search is improved by committing to a decision. The observed performance improvement is less for low-variance ranking functions, as their output is more consistent, leading to fewer changed decisions. Table 7 also shows how the selection of low variance ranking functions can significantly improve the quality of search results.
not overturned. In the case
G Discussion on meaningful zero for ranking functions
In our work, a coefficient of variation (see equation D was used to compare the variability of the commonly used ranking functions (see Fig. D The coefficient of variation requires that each ranking function has a meaningful zero. In our work, we use the following ranking functions: Frobenius norm of NTK, mean value of NTK, Label-Gradient Alignment, Eigenvalue score, ReL.U Hamming distance, condition number of NTK, EPE-NAS, Fisher, Snip, MeCo, SynFlow, and LogSynFlow.
We have assessed the concept of a meaningful zero for each ranking function listed above. Here are our findings.
19

---

Published in Transactions on Machine Learning Research (02/2025)
The Frobenius norm of NTK is always bigger than zero, and since it is norm, it clearly has meaningful vero.
The mean value of NTK is a mean of all elements for positive semidefinite matrix. Since the NTK is positive-semidefniite (Jacot et al. 2018), the mean value always non-negative, implying that there is mcaningful zero.
Label-Grase Gradient Alignment is computed from the NTK И E RBxB and label-alignment matrix L E {0, RxB (sce (Mok et al. 2022) for details). Since the NTK positiv--emiddefiiee, LGA is bounded from below. The metric has meaningful zero.
The Eigenvalue score is computed using the eigenvalues of NTK H, which are all non-negative. The Eigenvalue score has a meaningful zero (corresponding to the extreme case of a valu-valued kernel).
The ReLU Hamming distance is based on the comparison of ReLU activation patterns for different inputs. Since it is evaluated based on distances, it has a meaningful zero corresponding to the case when the activations match exactly for all inputs.
EPE-NAS score is the class-wise sum of absolute values, which is non-negative. It has meaningful zero.
The condition number NTK always positive and greater than or equal to one. Although the zero value cannot be achieved, is a meaningful value the sense that the zero point not arbitrary. We can shift scale the condition number and retain its fundamental meaning.
Fisher is a layer-wise sum over squares. It is non-negative and has a meaningful zero.
Snip is layer-wise over absolute values that is non-negative and has meaningful zero.
The implementations of both SynFlow and LogSynFlow use the layer-wisc summation of absolute values. These values are non-negalive, and they both have a meaningful zero.
McCo is layerwise sum of the smallest cigenvalues of Pearson correlation matrices for feature maps; the matrices are positive-semidefnitt by design (see (Jiang et al. 2024) for details), MeCo is non-negative and has a meaningful zero.
Assets
In this work, we used the following software:
automl/NASLib
(Mehta al.
2022
available GitHub under Apache 2.0 Licence
PyTorc Paszke et al.
2019
available via PyP1 under a custom BSD licence
NumPy Harris et al.
2020
available via PyPI under a custom BSD licence
SciPy Virtanen et al.
2020
available via PyPI under a custom BSD licence
The following dataset were used:
CIFAR-10/100 (Krizhevsky 2009 under CC BY 4.0 Licence
ImogeNet-166t 16-1200
(Chrabazzzz et al. 2017 under CC BY 4.0 Licence
NinaPro Atzori et al.
2012 under CC BY-ND Licence
Five datasets from Taskonomy collection Zaairr et al. 2018 under CC BY 4.0 Licence
20


Reviews:
[{"review_id": "cTZ5bnrBzs", "reviewer": "Reviewer_5g6C", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The paper is well written, and the motivation is clear and easy to follow. \n* Statistical MAX/TOP-K is a generalized method for noisy proxy measurement, so potentially a border community might be interested in applying this trick.\n* The author did comprehensive experiments with consistent results, showing the effect of mitigating noise with statistical methods.\n\nWeakness:\n* The notation used in the paper is not consistent which leads to some confusion that I e.g.:\n(a) In algorithm 1, K refers to top K architectures while in section 4.1 K seems to refer to the number of batches\n(b) In algorithm 1, N refers to how much ranking function measurements, however in Table 1 N refers to how much search budget?\ncan the author clarify these and fix the consistency of the notation? \n\n* The improvement is quite marginal for all zero-cost-proxy: almost all improvements are within 1 standard deviation. Why is this the case, can the author shed some light on this?\n\n* In all the experiments, the author seems to use the same number of ranking function evaluations for the architecture (10 times). How would the performance of average estimation and Stat estimation change with different evaluation budgets? I guess this is to answer the important practical question: how much budget of zero-poxy evaluation do I need if I estimate the stochastic dominance?\n\n* The author selected 3 zero-cost metrics and evaluated them on 8 datasets, however, it's not clear to me which metric benefits the most from statistical estimation compared to average estimation. Is it bringing more improvement to weaker or more noisy zero-shot metrics? I t would be nice if the author can show straightforward relative improvement between stat and avg for different rank functions (e.g. showed in Figure 3)", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper focuses on mitigating the randomness of NAS Zero-shot ranking methods. To enable noise robust evaluation of architecture with the zero-shot metrics, the paper propose to use statistical TOP-K method where Mann–Whitney U test is used to identify statistically better architectures. The author conducted experiments using random and evolutionary searches to justify the effectiveness of their method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weakness above.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1a1f55gEh8", "reviewer": "Reviewer_HmzA", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths \n- To my understanding, the characterization of ranking function variability within and across many architectural search spaces is a novel and useful contribution to the field. It is interesting to observe that ranking functions generally become less variable on better performing architectures within a search space, and this is a phenomena which would be interesting to describe to the community.\n- The benchmark evaluation results demonstrating the impact of integrating statistical testing into search algorithms are interesting. These results demonstrate that variability in the ranking function does appear to have a meaningful impact on the performance of many zero-shot NAS setups, and the authors essentially describe a method of improving zero-shot NAS which is is orthogonal to existing methods which seek to develop improved ranking functions or search algorithms. \n- Finally, I found the description of the literature in the field to be fairly thorugh and well suited to contextualize the results here. \n\n# Weaknesses \n- The main weakness I observe in the work is an omission of the role of non-stochastic ranking functions in zero-shot NAS. I have requested changes related to this point below. \n- Beyond this point, I believe the work could benefit from some minor points of clarification around the methods used as well as a more thorough discussion of implications of this work for the field. I have described my requested changes corresponding to this point below.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "- The authors provide a detailed overview of previous work in the zero-shot NAS field. They formalize work in the field as the development of new search algorithms and ranking functions which can be paired to find the best candidates within an architectural search space. I found their exposition to be thorough and easy to follow. They argue that variability in the ranking functions due to evaluation on a randomly chosen minibatch is a pervasive issue that will impact results across the field.\n- The authors then demonstrate that many commonly used ranking functions demonstrate significant levels of stochasticity as a function of the minibatch they are evaluated on. Furthermore, they show that 1) this variability appears to be a feature of each ranking function that is fairly stable across different architectural search spaces and 2) in general, within a search space, ranking functions exhibit lower variability on more performant architectures. \n- The authors then describe a drop-in method to integrate awareness of ranking function variability into search algorithms. In particular, they suggest using a Mann-Whitney U test to test for stochastic dominance of ranking function evaluations from one architecture vs. another. With random tie-breaking, this method easily integrates into a variety of existing search algorithms.\n- For random and evolutionary search, using this hypothesis testing framework generally leads to the selection of more performant architectures, regardless of the underlying ranking function or search algorithm. \n- The authors also observe that in the evolutionary setting, caching of ranking function score samples (as opposed to reevaluation of previously seen architectures) leads to better performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Changes critical for securing my acceptance recommendation. \n- Neither SynFlow and LogSynFlow as presented in Abdelfattah et al. 2021 and Cavagnero et al. 2023a use randomly generated data as input. Instead, these metrics calculate gradients relative to constant unit input. I have two requested changes with respect to this point: \n\t- Please correct the corresponding descriptions of these algorithms in the third paragraph of the introduction.  \n\t- SynFlow is competitive with the eigenvalue score on several of the benchmarks evaluated in Abdulfattah et al. 2021. To better contextualize your results, I believe it would be important to consider how architectures selected via SynFlow (i.e. a non-stochastic ranking function) compare to architectures selected by stochastic ranking functions with the Mann-Whitney U test, as considered here. \n\n## Changes that would strengthen this work. \n\n- One of the biggest take-home messages of this work is that there is significant variability in ranking function evaluation which can meaningful influence the the outcome of zero-shot NAS procedures. This finding suggests that zero-shot NAS may be fruitfully considered as a stochastic optimization problem. Evaluating ranking function evaluations using a Mann-Whitney U test has been shown to be an method to handle this variability, but one could also imagine others performing well based on the properties of the noise (e.g. reinforcement learning, bayesian optimization, etc.) I believe a discussion of this point more generally would be useful to contextualize the findings of the paper, especially as some of these other methods have been previously applied to zero-shot NAS. \n\n- It would be interesting to know if there is any relationship between 1) variability in the ranking function across minibatches and 2) variability in trained model performance (e.g. if one were to use those same minibatches as \"test\" data). Concretely I am asking:\n\t- For a fixed architecture, across the same set of minibatches, how correlated is the variability between different ranking functions? \n\t- If you were to then train this fixed architecture (excluding the evaluated minibatches from the training set), how would test performance on minibatches correlate with the variability of each ranking function? \n\nIf ranking function variability reflects something about variability in model performance, it may be possible to design zero-shot NAS strategies which use this varibiability to target objectives beyond average case performance. Such a study may also relate to the observation that better performing architectures within a search space exhibit less variability in their ranking functions. \n\n- Please clarify how the Relu Hamming Distance differs from eigenvalue score. If both are derived from Mellor et al. 2021 I am unclear on how the Relu Hamming Distance maps onto the material described there. \n\n- A subtle but interesting ablation would be to consider how the form of the ranking function comparison (i.e. comparison of means vs. Mann Whitney U statistic) influences architecture choice, independently of statistical significance testing. For example either increasing the threshold (i.e. more lenient testing criteria) of the Mann Whitney U test, or performing a t-test instead of simple average comparison would be interesting to consider in addition to the evaluation criteria studied here.", "broader_impact_concerns": "I do not have concerns on the ethical implications of the work that would require discussion in a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SueeDrwZel", "reviewer": "Reviewer_6fJQ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n* The paper is clearly-written, easy to follow and well-structured. The idea of stochastic ordering seems intuitive and experiments show that it works consistently (even if the performance gains are marginal)\n* The idea is generalizable, meaning that it theoretically can be applied to any proxy or search space, which offers an opportunity to improve the robustness of the search process.\n* This work generally, is appealing to researchers in NAS, mainly because it can be used to boost any proxy (theoretically).\n\n**Weaknesses**\n* Although the paper considers some well-established proxies, some additional newer proxy comparisons would be beneficial. Especially, it would be interesting to see the behaviour of proxies like ZiCo [1], MeCo [2], and SWAPNAS [3] when the additional stochastic ordering is implemented. \n* The comparative analysis (in Table 1) seems to be insufficient as it just considers three proxies, and out of them, two are just marginally better with the proposed ranking function variation inclusion. This, I believe, is not sufficient to prove the general claim that the method really works with all zero cost proxies. Thus, in the current state, the paper claims and evidence don’t match.\n* I think the authors should reformulate the claims in the paper to consider a specific search space and specific proxies, where this method works. Stating that “..this enhances the performance of existing zero-shot architecture search algorithms” is too general and is not experimentally evident.\n\n**References**\n[1] Li, G., Yang, Y., Bhardwaj, K., & Marculescu, R. (2023). Zico: Zero-shot nas via inverse coefficient of variation on gradients. arXiv preprint arXiv:2301.11300.\n[2] Jiang, T., Wang, H., & Bie, R. (2023). MeCo: Zero-Shot NAS with One Data and Single Forward Pass via Minimum Eigenvalue of Correlation. Thirty-Seventh Conference on Neural Information Processing Systems. Retrieved from https://openreview.net/forum?id=KFm2lZiI7n \n[3] Peng, Yameng, et al. \"SWAP-NAS: Sample-Wise Activation Patterns For Ultra-Fast NAS.\" arXiv preprint arXiv:2403.04161 (2024).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work focuses on analysing the variance in the zero-cost proxy in zero-shot NAS (also referred to as ranking function) subject to different network initialisation, and different inputs. They then, use the variation to slightly improve the random and evolutionary search processes. Intuitively, the more robust a proxy score is (or less the variation), the better the architecture found would be. The experiments show that including the information of variance improves over the standard mean calculation method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see the Weakness section", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "quPZrMS7zf", "reviewer": "Reviewer_pja4", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The idea of explicitly addressing ranking function variation through statistical comparison is novel in zero-shot NAS, to my knowledge. The experiments cover a range of ranking functions, tasks, and archtoectural search spaces, covering a breadth of empirical evidence for the proposed method.\n\nHowever, not all claims are are well-supported with evidence, whether thorough/clear explanation, results, and/or citations. The specific ones that need better evidence are listed in Requested Changes. I have also noted some issues with clarity and consistency.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new method for improving zero-shot Neural Architecture Search (NAS) by explicitly considering the variation in ranking function outputs. As fast ranking functions are inherently noisy, the authors propose to use statistical comparisons for the distribution of ranking function scores across batches, rather than simple comparing menas as done previously. Algorithms to incorporate this statistical comparisons within random and evolutionary searches are included. Experimental results across ranking functions, architectural search spaces, and hyperparameter values support the utility the proposed methods.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have listed specific changes following, with rough labels of Clarity, Evidence, Consistency, and Typos. In the paper's current state, I do not recommend acceptance. If all of the following changes are sufficiently addressed, I will change my answer for Claims and Evidence and recommend this work for acceptance.\n\n[Clarity] Abstract: \"In the zero-shot version, we use...\"- Because you later use \"we\" to refer to what is done in this paper, avoid using it here to help distinguish that you referring to the general community of zero-shot NAS. For example, \"In the zero-shot version, fast ranking functions enable the comparison of architectures without training them.\"\n\n[Clarity] Section 2.1, paragraph 1: \"Random search is the fastest search algorithm\"- \"Fastest\" could imply \"least compute to find an acceptable solution\". I think you rather mean that the algorithm itself has the least amount of overhead or is the simplest. \n\n[Evidence] Section 2.1, paragraph 1: \"Random search suffers the most from variability in the ranking function\" - Why? Do you have evidence, whether explanation and/or citations, to support this?\n\n[Evidence] Section 2.1, paragraph 3: \"This type of search ... in the ranking function.\" Again, why? Do you have evidence, whether explanation and/or citations, to support this?\n\n[Clarity] Section 2.1, paragraph 3: \"...requires that the architectural search space is specified as a hyper-graph\" - Why is this a problem? Are some architectural search spaces not specifiable as a hyper-graph? \n\n[Typo] Section 2.2, paragraph 2: \"...for a sampled batch of data Xiong et al. (2020).\" should be a parenthetical citation.\n\n[Clarity] Section 3, paragraph 1: \"A neural architecture search space can be represented as a graph...\" - Do you need to define it as a graph here, especially when graph-based search is not done in this work?\n\n[Typo] Section 4.1, paragraph 1: \"...a score to an architecture a batch of data...\" ->  \"...a score to an architecture, a batch of data...\" \n\n[Typo] Section 4.1, paragraph 1: \"the data set,\" -> \"the dataset,\"\n\n[Clarity] Section 4.1, paragraph 1: \"with the extent of the variation being dependent on ... and the task\" - Some ranking functions may not be affected by the task (beyond the dataset). For example, ReLU distance is not affect for different tasks on the same dataset, such as using MNIST as the input dataset and predicting the digit label or the parity as the task.\n\n[Consistency] Section 4.1, paragraph 2: The coefficient of variation requires that the ranking function has a meaningful zero. Is this true of all ranking functions considered?\n\n[Evidence] Section 4.2, Algorithm 1: You seem to use a greedy sequential application of the Mann-Whitney-U test. Are you sure this is rigorous? Will it always give the same output given different orderings? Could there be other statistical tests designed for more than pairwise comparison?\n\n[Typo] Section 4.2, paragraph 2: Extraneous newline between \"...for all k\" and \"(and ...\".\n\n[Consistency] Section 4.2, paragraph 4: Is $M$ different from the $K$ used in Section 4.1? Also, before $N$ seemed to be all architectures in a search space while here it is only sampled architectures?\n\n[Consistency] Section 4.2, paragraph 5: \"...removing the lowest ranked exemplar...\" In Appendix B, the oldest population member is removed?\n\n[Clarity] Section 4.2, paragraph 6: You should explicitly write that 3 population members are removed when the new 3 are added.\n\n[Clarity, Consistency] Section 5, Table 1-3: These tables are very dense and hard to quickly parse. I would recommend, for each pair (Avg vs Stat or Cached vs. On-the-fly), bolding the side that has a higher mean and underlining it if it is statistically significantly better. It seems like most of your results have a better mean than the baselines, but likely aren't statistically significantly better. This is an important caveat that you should explicitly address, especially sinc eyour proposed methods are statistics-based.\n\n[Clarity] Section 5.1, Figures 1-2: Why is $B$ repeatedly defined and $K$ is not?\n\n[Evidence] Section 5.1, last paragraph: \"In experiments (see Appendix C) we observe that the search performance improvement of this naive scheme is indeed considerably greater for these ranking functions.\" If I understand correctly, this is only true for 1 experiment pair out of 9, and that only 1 of \"these\" ranking functions have results shown. \n\n[Clarity, Evidence] Section 5.3, paragraph 1: I would recommend moving this section after the results and discussion in the second half of this subsection, since Table 3 is more of a main result than Table 2, which is more of an ablation study. Additionally, this study seems rather contrived: given an evaluation budget, the cached method should intuitively work better than the on-the-fly method. What if you compare them with a model budget instead? Also, what about a hybrid method, where when an architecture is revisited, it is re-evaluated K more times and these are appended to the existing evaluations?", "broader_impact_concerns": "No broader impacts statement is included, but I don't think it is necessary in this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers mostly reached an agreement recommending acceptance of the paper and believed that most of the concerns have been sufficiently addressed in the revisions and authors replies. As mentioned above, there were some concerns on the applicability of the method since it addresses a rather specific problem (randomness of metrics in zero-shot NAS) -- while the AE believes that the paper meets the two TMLR criteria (soundness and audience) and thus recommends acceptance as-is, the authors are still encouraged to at least add some qualitative discussions (e.g., similar to their reply to Reviewer 5g6C) about this point in their camera-ready version which I believe would also increase the impact of their work.
Decision: Accept (poster)