Evaluating Efficient Performance Estimators of Neural Architectures
Authors: Xuefei Ning
Changcheng Tang
Wenshuo Li
Zixuan Zhou
Shuang Liang
Huazhong Yang
Yu Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Neural architecture search (NAS)
Parameter sharing
One-shot NAS
Zero-shot NAS

Abstract: Conducting efficient performance estimations of neural architectures is a major challenge in neural architecture search (NAS). To reduce the architecture training costs in NAS, one-shot estimators (OSEs) amortize the architecture training costs by sharing the parameters of one supernet between all architectures. Recently, zero-shot estimators (ZSEs) that involve no training are proposed to further reduce the architecture evaluation cost. Despite the high efficiency of these estimators, the quality of such estimations has not been thoroughly studied. In this paper, we conduct an extensive and organized assessment of OSEs and ZSEs on five NAS benchmarks: NAS-Bench-101/201/301, and NDS ResNet/ResNeXt-A. Specifically, we employ a set of NAS-oriented criteria to study the behavior of OSEs and ZSEs, and reveal their biases and variances. After analyzing how and why the OSE estimations are unsatisfying, we explore how to mitigate the correlation gap of OSEs from three perspectives. Through our analysis, we give out suggestions for future application and development of efficient architecture performance estimators. Furthermore, the analysis framework proposed in our work could be utilized in future research to give a more comprehensive understanding of newly designed architecture performance estimators. The code is available at https://github.com/walkerning/aw_nas.

Evaluating Efficient Performance Estimators of Neural Architectures
Xuefei Ning!t
Changcheng Tang"
Wenshuo Li'
Zixuan Zhou'
Shuang Liang?
Huazhong Yang
Yu Wang
Department of Electronic Engineering, Tsinghua University?
Novauto Technology Co. Ltd.²
Ffoxdoraame @ gmail.com, yanghz @wwe@@iiiisshuu..oo "yu-wang @lsinghua.edu.cn
Abstract
Conducting efficient performance estimations of neural architectures is major challenge in neural architecture search (NAS). To reduce the architecture training costs in NAS, one-shot estimators (OSEs) amortize the architecture training costs by sharing the parameters of one "supernet" between all architectures. Recently, zero-shot estimators (ZSEs) that involve no training are proposed to further reduce the architecture evaluation cost. Despite the high efficiency of these estimators, the quality of such estimations has not been thoroughly studied. this paper, we conduct an extensive and organized assessment of OSEs and ZSEs on five NAS benchmarks: S-S---Bncc-100 101/201/301, and NDS ResNet/ResNeXt-A Specifically, employ set of NAS-oriented criteria study the behavior of OSEs and ZSEs, and reveal their biases and variances. After analyzing how and why the OSE estimations unsatisfying, explore how mitigate the correlation gap of OSEs from three perspectives. Through our analysis, we give out suggestions for future application and development of efficient architecture performance estimators. Furthermore, the analysis framework proposed in our work could be utilized in future research to give more comprehensive understanding of newly designed architecture performance estimators. The code is available at /http:://// ptttps:/giitee /tt//ggibbbbbbt thub com/walkerning /aw aa_nas nas
Introduction
Neural architecture search (NAS) can automatically discover architectures that outperform the hand-
crafted ones for various applications [48] [10 [1]. Early NAS methods 48 30 suffer from
extremely heavy computational burden, and can take tens of thousands of GPU hours to run. One of the major reasons for the computational challenge of NAS is that evaluating each candidate architecture is slow, which includes a full training and testing process. In the past years, studies 2
27 3
45 20 M have been focusing on developing more efficient performance estimators of g
neural architectures.
conduct costly separate training process to acquire the suitable parameters to evaluate each candidate architecture. To make NAS computationally tractable, ENAS (27) proposes the paramiter-sharing technique accelerate the architecture evaluation. Following this work, the parameter sharing technique is widely used for architecture search in different search spaces (39 [6] or incorporated with different search strate- gies [19 16. 23 40). We refer to the parameter-sharing estimations as the "one-shot" estimations since it requires the training cost of one supernet.
One-shot Estimator (OSE) Traditional NAS methods 48 30
How well the ohe-shot estimations are correlated with the standalone architecture performances is essential for the efficacy of NAS methods. Despite the widespread use of OSEs, studies 433 have
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

revealed that the OSE estimations might fail to reflect the true ranking of architectures. However, their experiments are conducted in a toy search space with only 32 architectures. In this work, we conduct more comprehensive study on OSEs in five search spaces with distinct properties, including three topological search spaces INAS-Benche 101 (41), 20n- 19), and NAS-Bench-300 (32),
and two non-topological search spaces 29 (NDS ResNet, and NDS ResNeXt-A). We further analyze how and why OSE estimations have bias and variance, and explore how to improve OSEs.
Zero-shot Estimator (ZSE) More recently, in order to further reduce the architecture evaluation 26 introduce "zero-shot" estimators that involve no training. In this work, we study various ZSEs on several benchmarks and reveal their properties and weakness.
cost, several studies 220 1 15
17
Knowledge Our work reveals pieces of knowledge OSEs and ZSEs. First of all, some behaviors of OSFs and 7SEs vary across search spaces (Appendix 1.1.1, Sec. 4.2). Some of the common knowledge for OSEs revealed by our work include 1) OSEs bias towards architectures with lower complexity in the early training phase [18]. And this bias can be alleviated to various extents with sufficient training in different spaces (Sec. [.1]). 2) OSEs have variance and can be mitigated some extent (Sec. 5.3 Sec. 6.1b. 3) Reducing the sharing extent of OSEs can potentially improve their
ranking qualty 47 (Sec. 6.
As for ZSEs, we reveal that 1) Current ZSEs cannot benefit from one-shot training. The ranking qualities of ZSEs utilizing high-order information (i.e., gradients) even degrade a lot after one-shot training (Sec. 4.2) 2) Parameter-leve ZSEs adapted from pruning literature are not suitable for ranking architectures, and their ranking qualities cannot surpass those of parameter size (#Param) or #FL.OPs (Sec. (.2). 3) Existing ZSEs have improper biases, some overestimate linear architectures without skip connections, and some overestimate architectures with smaller kernel sizes and receptive fields (Sec. (Sec. 4) The relative effectiveness of ZSEs varies between search spaces, relu_logdet [21] the best on the three topological search spaces, and synflow (33) is better on the two non-topological search spaces (Sec. 4.2). 5) Most ZSEs are not sensitive to the input data distribution: They get similar architecture rankings when using random noises as the input (Appendix B.
Suggestions Based on our experiments and analyses, we give out suggestions for future OSE applications. For example: 1) Longer training makes one-shot estimations better (Sec. 4 2) Using one-shot loss instead of accuracy significantly improves the ranking qualities in the DARTS space [6 (Sec. 4.1 ; 3) One should use enough validation data for OSEs, instead of merely several batches as in ZSES (Sec. [4T]): 4) Using temporal ensemble helps reduce the ranking instability, and brings non-negative improvements the ranking quality in different search spaces S.cc.66.1p ; 5) In search space with isomorphic architectures, augmenting the sampling strategy to improve the sampling fairness is essential avoid overestimating simple architectures (Sec. 6.2); 6) Affine operation should not be used in batch normalization (BN) during supernet training (Sec. 6.3).
As for ZSEs, point out several open research problems: 1) Is there general ZSE suitable for different types of search spaces? 2) Do we need to make ZSEs utilize the input data information better, and how we do that? 3) Can develop ZSEs that distinguish top architectures better? We also list out some technical suggestions for improving ZSEs: 1) Future ZSEs should conduct architecture-level analysis instead of using parameter-level analysis (Sec. 4.2). 2) According some prominent bias of existing ZSEs, we can add some structural knowledge into ZSE voting ensembles, e.g., receptive field analysis seems promising for improving jacob_cor rovob_covoo or relu_logder (Sec. (.2). 3) In future developments of ZSBs, researchers should add two simple comparison baselines, #Params, and #FLOPs, they are actually very competitive baseline ZSEs (Sec. 4.2)
Our work provides strong baselines and diagnosis tools for future research of architecture perfor- mance estimators, and we suggest future research to utilize these baselines and tools for more comprehensive understanding of newly designed performance estimators.
Analysis Framework Our analysis framework of efficient architecture performance estimators organized as follows. We first introduce the evaluation criteria for estimator quality in Sec. [3] And Sec. 4 presents the quality evaluation of multiple OSEs and ZSEs. Then, we conduct an organized analysis on how and why the OSE and ZSE estimations have biases and variances in Sec. 5 Specifically, their complexity-leeel operation-level. and architecture-level biases are demonstrated and analyzed. And the stability of OSE accuracy and ranking along the training process are analyzed. And in Sec. 6 based on analysis framework, we present several case studies improving OSEs from three perspectives: i.c. reducing the variance, bias, and parameter sharing extent.
2

---

2 Related Work
2.1 Efficient Performance Estimators of Neural Architectures
One-shot Estimators The vanilla NAS method [48] trains each architecture for 50 epochs to acquire its suitable parameters, which makes the NAS process prohibitively costly. As remedy, ENAS [27] proposes to amortize the separate training costs by sharing parameters among architectures. Specifically, ENAS constructs evaluated using its parameter subsets. Throughout the search process, the shared supernet parameters updated on the training set, and an RNN controller is updated alternatively the validation set.
werrpaarametrized supernet such that all architectures can be
There are two types of parameter-shane sharing methods: 1) One-shot NAS methods B 13 that first train a supernet and then conduct architecture search without further supernet tuning. 2) Non-one-shot
methods (27 16 40) that conduct supernet training and architecture search (i.e. controller update) jointly. And this work focuses on evaluating the estimations of the "one-shot" supernet, since it is the cleaner case without the complexity of varying controller settings and possible controller-supernet co-adaption. In each supernet training step, S architectures are randomly sampled to process a batch of training data. Here S denotes the number of Monte- Carle architecture samples. Then, the gradients of these architectures averaged to update the supernet.
Correlation of One-shot Estimators There exist some studies that carry out correlation evaluation for one-shot estimators. Zhang et al. 45 compare the correlation of OSEs and their proposed hyper-network- -based estimator. However, their work is not aiming for a large-scale scale evaluation of OSEs and ZSEs, thus they only evaluate the OSE correlations on one search space, and do not conduct further analysis. Yu et al. [4] conduct parameter sharing NAS in toy RNN search space with only 32 architectures in total, and discover that the parameter sharing rankings do not correlate with the true rankings of architectures. Zela al. [44 also report that the correlation of parameter-sharing estimations is not satisfying with Spearman correlation coefficient between -0.25 and 0.3 on larger search space with around 15k architectures. Pourchot et al. (28) evaluate the Spearman's 's ranking correlation of OSEs on MAS--ench--00 Yu et al. 442 provide analysis on how the heuristics and hyperparameters influence the supernet training on three benchmarks (i.c. PAS--Bench-- 101, NAS-Bench-200 and DARTS-NDS). But they only use the variants of Kendall's Tau as the evaluation criteria, and do not further explore the biases and failing reasons of OSEs. Zhang et al. [47] point out the instability and poor ranking correlation of OSEs, and claim that the high extent of parameter sharing causes the unsatisfying performance. However, they only conduct experiments on a small search space with about 200 architectures.
In this paper, we conduct a more comprehensive study of OSE behaviors across five search spaces, and further investigate how and why the OSE estimations are not satisfying. We also propose and compare several techniques to mitigate the OSE correlation gap.
Zero-shot Estimators More recently, in order to further reduce the architecture evaluation cost, several researches 20 propose "zero-shot" estimators that conduct no training and use random initialized models to estimate architecture performances. Based on the observation that good ar- chitectures have distinct local jacobian on different images, Mellor et al. [20] propose an indicator based input jacobian correlation. Lopes et al. [17] improve the above indicator by calculating the jacobian correlation with respect to the class. Abdelfattah et al. 1 adapt several ZSEs from the pruning literature, and claim that these adapted 7SSSs can perform well on NAS-Bench-200 Lin et al. [15] define the expected Gaussian complexity to measure the network expressivity, and efficiently discover architectures with state-of-the tte--at accuracy on ImagetNet. With a small training overhead, Ru et al. [II] propose to evaluate an architecture's 's performance by its training speed. Concurrent to our work, White et al. (38 also evaluate various performance estimators on multiple benchmarks.
2.2 NAS Benchmarks
NAS benchmarks are proposed to enable researchers verify the effectiveness of NAS methods efficiently. NAS-Bench- 101 (NB101) 41 provides the performances of the 423k valid architectures in cell-based search space. OSE cannot be easily applied for the whole NB 101 search space due shot1
to its specific channel number rule. To reuse NB 101 for benchmarking OSE, (NB1 ssott 44 picks out three sub-spaces of NB 101, and supernet can be easily constructed for these sub-spaces. In this work, we use the largest sub-space in NB Ishot: NB Ishot-3, and use the name
3

---

"NB101" to refer to it. Another benchmark, of all the 15625 architectures a single-cell search space. Previous tabular benchmarks exhaustively train all architectures in a search space much smaller than commonly-usee ones (e.g. DARTS [16] with size over 1018). Recently, MASS-ench-301 (NB301) [32 proposed as a benchmark in the DARTS space. It adopts surrogate-base based methodology that predicts architecture performances with the performances of about 60k anchor architectures.
(NB201) 99 provides the performances
Besides these benchmarks on cell-based topological search spaces, we also experiment with two non- topologiaal benchmarking search spaces [29]. NDS ResNet, and NDS ResNeXt-A. The architectural decisions in these search spaces are the non-topological hyper-parameten of pre-defined blocks, including kernel size, width, depth, convolution group number, and so on. The properties of these benchmarking search spaces are summarized in Appendix Tab. Al.
3
Evaluation Criteria
This section introduces the major evaluation criteria used in our analysis framework, while the analysis criteria and methods of ranking bias and variance will be introduced in Sec. [ We denote the total number of architectures as M, the true (ground-truth, GT) performances and approximated estimated scores of architectures (a:)==,,-...k .M as {ui)=e, .M and (s.))=1.....MA ,M. respectively, and
the ranking of the true and estimated score ye. 8, as Ts: R2 E {1,-.. J. respectively (r; = 1 indicates that a; is the best architecture). The correlation criteria used in our framework are
Pearson coefficient of linear correlation (LC): corr(y. s)/ co corr(y. v)corr(ss
Kendall's Tau ranking correlation (KD 7): The relative difference of concordant pairs and discordant pairs Σie, sgn(y: - yy (sggs s; -,y/
Spearman's 's ranking correlation (SpearmanR): The pearson correlation coefficient between the ranking variables corr(r, n)/ /oor(r, r n)).
Since the ability of differentiating between good architectures matters than differentiating between bad ones, criteria that emphasize more on the relative order of architectures with good performances are desired. Denoting Aς {ai|n KM} the set of architectures whose estimated scores are among the top K portion of the search space, we use two set of criteira [25]:
#ilr, A k.M,MM, The proportion of true top-K KM proportion architectures in the top-K architectures according to the scores.
Precision @ K (P@topK) E (0,
BestRanking @ K (BR@) ()) E (0, arg min r The best normalized ranking among the top K proportion of architectures according to the scores (Lower is better).
Corresponding to P@topK, we also compare P@bottomK = (()rs>(11 K)M A (1>(1-KMM) to
reveal how the worst architectures are distinguished. And corresponding to BR K, we inspect WorstRanking @ K (WR@K) = arg max.,eAg rr/M to reveal how the supernet is likely to regard bad architecture to be good (Lower is better). Note that the rankings and architecture numbers are all relative numbers normalized by the total architecture number M.
4 Evaluating Efficient Performance Estimators
4.1 Evaluation of One-shot Estimators
Trend of Different Criteria
We inspect how these proposed criteria evolve during the training process. Unless otherwise noted, MC sample 5=1 used the experiments. And all training and evaluation settings are summarized in Appendix D. Fig. T and Appendix Fig, A24 show the criteria trend on topological and non-topological search spaces, respectively. We can see that the convergence speeds of criteria different, and on all search spaces except NB 101, all criteria show rising trend as the training goes on, indicating that OSE gives better rankings with sufficient training.
Another fact is that on all search spaces except NB101, OSEs are better at distinguishing bad architectures (higher P@ @oottoo5%% %) than distinguishing good ones (lower %. This indicates that, although identifying the exactly optimal architecture might be difficult for OSEs, using

---

MAS MMS-Bench-100 (1shot sub 3)
NAS-Bench-200
NAS Bench
0.6
0.75
0.50
Oneshot
Linear correlation
0.00
500
0.00
Spearman corretation
Kandall's tau
0.66
0.6
1.2
P@top5%.
0.4
2.0
0.75
0.4
1.0
Pgbottom55
0.2
0.8
0.2
0.25
0.0
0.6
250
500
750
1000
250
500
1000
200
000
600
000
1000
Figure I: Top /Bottom: Criteria of using OS accuracy OS loss as the estimations (right Y-axis: OS
loss value). "Oneshot average" means the average oneshot score (accuracy or loss).
them to filter bad architectures or warm-up sample-based NAS be very effective. The results of more criteria are shown in Appendix Fig. A1.
In the NB301 (DARTS) space, OS loss gives significantly better estimations than OS accuracy. For example, at epoch 1000, the KD of OS acc and loss are 0.381 and 0.512, respectively, while their @@ top5% are 13.8% and 31.0%. This is because the loss value considers the network's output distribution rather than a single label prediction, it has less concentrated distribution and is more informative in ranking architectures. Fig. shows that the OS accuracy distribution is indeed more concentrated than the OS loss on NB301.
Oneshot Accuracy
Oneshot Loss
NAS bench-201
Bench
Oneshot Acc/Lass@ Top 5%
Lcc/Loss@ioo
0.05
0.00
0.00
1.011
Figure 2: The distribution of OS accuracy and loss.
Effeet of the Validation Data Size We inspect OSEs' ranking quality when using different numbers of validation data batches to evaluate the OS scores, and find that on both NB201/NB301, using more compute the average OS accuracies
data improves the estimation quality. Specifically, validation batches, where each batch contains 128 examples. And the effect of the batch number N on the ranking quality is shown in Fig. B and Appendix Fig. A3. Fig. shows that on NB301, criteria get better when the batch number increases from to 10 at epoch 1000. Interestingly, when the training sufficient (epoch 200), the criteria decrease with more data batches (especially those of the OS acc). To explain this, Fig. Jupeer right) shows the intra-"level" KD histogram, where architectures with the same OS accuracy using one validation batch are said be the same level. We can see that when the supernet is under-trained, it is not good at distinguishing between intra-level architectures (negative intra-level KDs). Therefore, using more validation data might bring negative impacts, while giving tie scores can avoid making wrong comparisons between similar architectures.
N
4.2 Evaluation of Zero-shot Estimators
Our work evaluates six parameter-level ZSEs and two architecture-level 7SEs. The six parameter- level 7SEs are grad_norm norm, plain [22 snip [14,, grasp fisher [34 35 and syuflow 3k] These 7SEs are named after sensitivity indicators initially designed for fine-grained network pruning that measure the approximate loss change when certain parameters or activations are pruned. A recent work [1] proposes to sum up parameter-wise sensitivities of all parameters to evaluate an architecture. And architecture-level ZSEs measure the architecture's discriminability by inference differences between different input images: jacob_con [20 uses the input jacobian correlation, and relu flodet (1 uses activation differences.
5

---

Intra-(1-
Oneshot
Oneshot
10 batch
0.3
0.4
20
0.2
0
1..0
-0.5
0.0
0.5
1.0
correlation Spearman
seed 20
(74/88)
0.1
Kendall's tau
seed (78: (8))
P0
2
4
6
10
PoboottomiO
0.6
0.7
50
0.6
0.4
-1.0
-0.5
0.0
0.5
1.0
0.4
seed 20 (64 (8))
0.2
0.2
Seed 202020 (59)
2
10
Figure 3: Criteria vary on NB301 as the batch number (X-axis) changes. Right: The histogram of intra-level KDs using 10-batch OS acc, the "levels" are partitioned according to 1-batch OS acc. Since natch_size=128, at most 128 levels can exist. The legend gives out the actual number of levels in 1-batch evaluation with format "#acc levels with #arch>1 / #total".
The full evaluation results of 7SEs are shown in Appendix B and C, and Fig. g shows some of the results on NB201 and NB301. We can see that the ranking correlations of ZSEs except relu Jogdet are even worse than the GT-Param correlation. Also, the relative effec- tiveness of ZSEs varies between search spaces. For example, NB301, Figure 4: KD between GT, FL.OPs/Params, OSEs (1k epoch) and 7SEs. Left: NB201; Right: NB301.
KM
60
425
AJD SACD
JAM
plain performs better than other ZSEs except relu hogdet, while on NB201, plain performs worst among all ZSEs. And jacob __vv and synflow give relatively good estimations with KD of 0.61 / 0.57, but they do not perform well NB301 (KDs are 0.23 0.2). Also, as shown in Appendix Tab. A12, the best-performing ZSE on topological search spaces, relu_logdet, does not perform well non-topological NDS ResNet and ResNeXt-A.
The vote 7SE conducts a majority vote between various metrics to compare each pair of architec- tures. We choose three best-performing ZSEs the voting experts, and find that this simple form of voting does not bring improvements over the best constituent ZSE, Better ways of ensembling different ZSEs need to be developed.
a natural idea to apply ZSEs on trained networks. Thus we explore whether ZSEs can benefit from one-shot training. According to Appendix Tab. A11, current ZSEs cannot benefit from one-shot training. The ranking qualities of ZSEs except relu fotudooeet even degrade a lot after one-shot training. A possible explanation is that these 7SEs utilize the gradient information, and the gradient magnitudes in trained supernet are too small and obscure for architecture ranking.
How & Why the Estimations Are Not Satisfying
5.1 Bias of One-shot Estimators
Complexity-level Bias To identify which architectures are under- or overestimated, we investigate the relationship of the true-estimated Ranking Difference (RD) n;; = 1,....M . and the architecture complexity (i.e. Params, FL.OPs.. RD serves as an indicator of overestimation for arch i: A positive RD indicates that this architecture is overestimated. Otherwise, it is underestimated.

---

Sub-architectures have different amounts of calculation and might converge with a different speed. Thus, we conduct the complexity-level bias analysis. In Fig. 5 we divide the architectures into five complexity groups according to the amount of calculation (FIOPs), and show the KD and average RD in each group. In the early training stages (the 1st row), the average RD shows decreasing trend, which means that the larger the model, the easier it is to be underestimated. This is because larger models converge at a slower speed. As the training goes on (the 2nd and 3rd rows), the absolute average RD decreases, indicat- ing that the issue of underestimating larger models gets alleviated. And on both spaces, the decreasing intra-group KD indicates that it is harder for OSEs to compare larger models than comparing smaller ones.
0.0
-01
Rank DIf
-0.
-0.2
20%
40%
60%
00%
100%
22%
40%
60%
00%
100%
0.05
0.05
Exoch
6
0.00
0.-
-0.05
0.5
20%
60%
90%
100%
Toach 1200
0.7
0.00
0.00
0.1
5.00
0.2
00002
0.04
20%
40%
50%
100%
100%
20%
40%
60%
00%
300%
Figure 5: Complexity Average RD within the complexity group. X-axis: Complexity groups (the group with the smallest FL.OPs is at the leftmost).
bias. Left/right Y-axis: KD
Op-level Bias We inspect the changes of GT and OS accuracy when one operation is mutated to another (edit distance=1) 1). On NB301, we examine 23476 mutation pairs and find that the OSE estimations overes- timate the effects brought by dilation (Dil) convolutions (Convs): All mutation types from other operations to DilConvs witness a higher OS increase ratio than the GT one. And the skip_connes operation is underestimated: All mutation pairs from skip_ ciipcconectt cause the OS increase ratio be higher than the GT one. For example, when mutating one akip_conned operation to dil_conv_5x5 only 39.0% out of 2336 pairs get GT increases, while 94.9% get OS increases. This phenomenon is more remarkable when we only consider mutation pairs within the largest complexity group (grouped by Param): Only 15.3% of 569 pairs get GT increases, while 92.3% get OS increases. On NB201, based on a similar inspection of the mutation pairs, we find that OSE estimations slightly overestimate avgpool3x3 and underestimate conv3x3 3x3. Generally speaking, the op-level bias on NB201 is not as large as that on NB301. See Appendix A.2.2 for the figures and more results.
5.2 Bias of shro Estimators
Synflow
Jacob_ DOv
MAS.Banch-200
57%044495
NAS Banch-hhh-33 (normal cell
Preferlargest largest architectures
Prefer architectures with gradient explosion
Prefer 1xl over 3x3 on NB201 Prefer shallower architectures NE301
Figure 6: The best architectures ranked by several ZSEs NB201 and NB301.
Arch-level Bias By inspecting the best and worst architectures indicated by ZSEs, we find that existing ZSEs have improper biases. Fig. 6 shows that synflow has an excessive preference for large architectures. snip, grad_norm and fisher give similar rankings of architectures (see Fig. 4. and show improper preferences for architectures with gradient explosion: On NB201, they show a clear preference for architectures without skip connections, which are far from optimal. This is because gradient magnitudes in these architectures get exploded, and the absolute parameter wise sensitivity is high. In a word, the parameter-level ZSEs adapted from the fine-grained pruning literature are not very suitable for ranking architectures, since they are designed to reflect the relative parameler-wise sensitivity. And due to their sensitivity to scales and gradient explosion, a simple form of adding up the parameter- wise sensitivity provides improperly biased estimations for architecture performances.
7

---

In contrast, architecture-leve ZSEs (jacob cov, relu foodulloggr are more reasonable attempts that mea- sure the architectures' discriminability by inference differences between input images. Nevertheless, as shown in Fig. Gand Appendix B.2, these two 7SEs prefer architectures with smaller receptive fields (prefer smaller kernel sizes or shallow architectures). Consequently, although these two 7SEs have relatively good ranking correlations on topological search spaces, they have difficulties in picking out top architectures (Poor P@topKs, see Appendix Tab. A9).
5.3 Variance of One-shot Estimators
Accuracy Forgetting Due the parameter sharing and the random sample training scheme, the training of subsequent architectures overwrites the weights of previous ones, thus degrades their OS accuracy. This imulli-mode forgetting" phenomenon 4 46 accounts for the variance of OS accuracies. Appendix Fig. A14 verifies the existence of the forgetting phenomenon. For each architecture in one epoch, we define its forgetting value (FV) as acC2 acci, where acci refers to its valid accuracy right after its training, and acc2 refers to its accuracy after all the architectures in this epoch have been trained. Appendix Fig. A14 shows that the forgetting phenomenon exists in the early training stages, where the FVs are negative. As training progresses, the variance of the FVs decreases, which natural due to the learning rate decay. Also, the mean FV becomes positive, indicating that training other architectures can have positive transferring effects on previous architectures instead of negative ones (i.e. forgetting). This observation can be explained by the increasing trend of inter-architecture gradient similarity in Appendix Fig. A15.
Ranking Stability We demonstrate the ranking stability in Fig. 7 since it plays an important role that influences the NAS process more directly than the accuracy stability. The criteria in this figure (i.e. relative KD, relative P@top/bottomk) calculated with two sets of adjacent OS estimations, while the estimations of the latter checkpoint are taken as the GT one. We can see that the ranking stability increases with sufficient training and the OS rankings of bad architectures relatively stable (relP@ (relP@bottomiy bottomk). On NB301, even with rather sufficient training (Ik epoch) where the mean OS accuracy already saturates (Fig. D the ranking stability of top architectures is still not high (relP@ top 00.46.. This is reasonable since that the accuracy differences between architectures in the DARTS space are smaller. And as expected, averaging the OS accuracy of multiple supernets stabilizes OSE estimations. Also, the temporal weight ensemble of multiple checkpoints can stabilize the estimations (Sec. 6.1
Tenking
6.0
NasRench-201 (measured every 40 epach)
are
0.5
3.4
0.2
ad2
200
437
12
X23
1592
(b) NasBench-301 (measured every 100 epoch)
Figure Ranking stability of OSEs.
How to Improve One-shot Estimations
Since different architectures require different values for supernet parameters, as the side effect of acceleration, parameter sharing serves as the intrinsic reason for the OSE correlation gap. Appendix Fig. A15 shows the gradient similarity distribution between architecture pairs on NB201. We can see that the inter-architecture gradient similarities vary in a large range, and one common phenomenon on NB201 and NB301 is that the mean similarity between architecture pairs lower in the middle-stage layers and the architectures' gradients in the very first and last layers more similar. Another
8

---

slightly counterintuitive fact is that the gradient directions become more similar as the training goes on, especially on NB201. This can explain the positive transferring effect the latter training stages.
Due to parameter sharing, the random sample training scheme of OSE causes estimation variances. On the other hand, improper sampling distribution causes estimation biases. There are two types of reasons for the bias: 1) Some archi-
tectures (e.g. with larger complexity)
Oneshot aco
PSttop/bottorn 5%
might need higher sampling probabil- ity to match their relative performance in standalone training. 2) Architectures are sampled from an unfair distribution, i.e. some architectures have undesirable higher equivalent probabilities.
Pgtep 3h
0.5
0.8
0.5
0.4
0.2
mubii seed essumbi racd
0.2
cempprni encemble oesigtt ceats
Echoing the above analysis, this sec- tion conducts case studies to improve 0.8
200
400
600
800
1000
200
400
600
800
1000
the OSE estimations from 3 perspec- tives, i.e. reducing the variance, bias, and parameter sharing extent. Sec. 6. experiments with techniques that can reduce the OS estimation variance. And in Sec. 6.2 we demonstrate that using de-isomorphic sampling in space with isomorphic architectures (NB201) helps improve the sampling fairness, thus re- duce the estimation bias.
<Stes 5h
0.4
0.1
0.2
0.0
200
400
600
800
1000
200
400
600
800
1000
Figure 8: Effect of ensemble techniques on OSEs. Top: NB201; Bottom: NB301.
6.1 Variance Reduction
Temporal Variance Reduction Sec. 5.3 shows that averaging OS scores of several supernets stabi- lizes the estimations. However, this technique is not practical due to its linearly enlarged consumption, as training k supernets takes k-times more computation. As a remedy, Guo et al. [12] propose to only train one supernet, and stabilize OS estimations by temporally averaging weights of supernet checkpoints. Besides the variance reduction effect shown in Fig. Fig. [ shows whether ensembling techniques can bring other ranking quality improvements. We can see that temporally ensembling or 5 checkpoints brings improvements on NB201 but brings no bias improvements on NB301.
Sampling Variance Reduction We compare the results of using different MC sample numbers S in supernet training. We also adapt Fair-NAS 7 sampling strategy to NB201 and NB301. Using multiple MC architecture samples has different influences in different spaces: It is beneficial for the estimation quality on NB301, while the estimation quality on NB201 decreases slightly as the MC sample number increases. See Appendix A.3.2 for more detailed results.
6.2 Sampling Fairness Improvement
Besides the complexity-leve and op-level biases shown in Sec. 5.1 OSEs also have some evident architecture-leva biases. The NB201 search space contains many isomorphic architectures with different representations, and there are 6466 unique structures (out of 15625) after de- de-isomorphism. We find that even after sufficient training, the supernet still overestimates some simple architectures significantly. Fig. Ieeft) shows the top-2 ranked architectures by the average of 3 supernet's OS scores at epoch 1000. With vanilla sampling (Iso), OS estimations bias towards simple architectures (a single Conv) with many isomorphic counterparts (Iso group size=31). We find that this is because isomorphic architectures have identical gradients w.r.t. shared parameters, so that the shared parameters tend to be optimized towards the gradient directions of architectures with many isomorphic counterparts.
We compare the results of sampling w. or w.o. isomorphic architectures in Fig. righht). We can see that using the de-isomorphism (deiso) sampling strategy helps pick out top architectures and brings significant improvements on B.55% and P@5% (1.9% to 0.23%, 21.3% to 46.7%). We also experiment with a nost-de-somorpphis (post-deiso) technique, in which the estimations of architectures in an isomorphic group are averaged during testing, while no changes are made during training. We can see that "post-deiso" brings slight improvements BR @ Ks and P@ @topss

---

Iso sampling
0.7
Rank 83.55/92.55,
0.6
Rank 83.51/91.96
Jig coMtec
average
Parttop
Kendal's
Pg 10pp
delso sompling
200
400
600
BDC
600
603
800
2000
Deiso sampling
no post-deiso
BRig
WRigosp5%
0.03
Un ungghop
0.5
Wiggepp1%
Rank 78.28/93.4,
0.4
Rank 78.28/93.67
0.01
0.2
0.00
200
000
000
8000
1000
200
600
0.00
800
1000
Comparison of Iso / Deiso sampling strategy. Left: Top-2 ranked architectures when the supernet is trained with Iso Deiso sampling strategy, the legend's format is "OS acc (%)GT acc (%), Iso group size". Right: Criteria comparison along the training process.
Figure 9:
compared with "no post-deiso", which might to the decreased estimation variances. Actually, the deiso sampling strategy is to find a de-isomorphic representation space and conduct uniform sampling in it, and our study provides another evidence for the statement made by (37 that representations can be critical for NAS methods. More detailed results and discussions are in Appendix A.3.3.
6.3 Sharing Extent Reduction
Operation Pruning We remove one or two operations in the search space (SS) and conduct supernet training on the resulting sub-SS. After training the supernet, we compare the OS estimations on the sub-SS provided by the supernet trained on full SS and the sub-SS. The detailed results and analyses can be found in Appendix A.3.4. And the conclusion is: Sharing extent reduction by removing operations can bring improvements to the average OS scores of the remaining architectures in the sub-SS, especially in the early training stages. However, whether the improved absolute OS scores can bring ranking quality improvements is questionable, and the results vary across SSes.
One-shot Pruning We conduct SS pruning on NB201 by selecting the top 10%, 25%, 50% architec- tures ranked by the OS scores of supernet (epoch 600), and continue to finetune the supernet to 1000 epoch with these architectures. The good news is that on NB201, OS pruning brings improvements on both the average OS score and ranking quality in the sub-SS: 2.2% 1/0 16/00.15 % average OS score increases and 0. 18900 2.189/000660.0000 046/0.086 KD increases when the sub-SS contains 10%/25%//50% architec- tures, respectively. The results reveal the potential of dynamic SS pruning for improving the OSE quality, especially for good architectures. However, this per-architecture hard pruning scheme is practical since it needs an exhaustive test of the full search space. To explore practical dynamic SS pruning methods, we conduct a case study on per-architecture soft pruning with a jointly-trained controller, where the controller gives higher sampling probability to the architectures with higher OS scores. The results and analyses are shown in Appendix A.3.4.
Remove the Affine Operation in BN We compare using not using BN affine operations, and give out the comparison results in Appendix A.3.4. And the suggestion is that one should not use BN affine operations in the search process.
7 Conclusion
We present an analysis framework of efficient architecture performance estimators in NAS, containing carefully developed criteria and organized analyses. Within the framework, we conduct an in-depth analysis of OSEs and ZSEs on five benchmarking search spaces with distinct properties. Our work reveals the properties, weaknesses (variance and bias) of current architecture performance estimators. For OSEs, we further conclude three directions for their improvements and experiment with several mitigations accordingly. Our work gives out suggestions for future NAS applications and points out research directions to further improve current OSEs and ZSEs. Besides the take-away knowledge, our work also provides strong baselines for future research of efficient performance estimators, and the analysis framework could be utilized to diagnose new performance estimators.
10

---

Acknowledgements
This work was supported by National Natural Science Foundation of China (No. U19B2019, 61832007), Tsinghua EE Xilinx AI Research Fund, Beijing National Research Center for Information Science and Technology (BNRist), and Beijing Innovation Center for Future Chips. We thank Zinan Lin, Tianchen Zhao, and Hanbo Sun for their valuable discussions. Finally, we thank all anonymous reviewers for their constructive suggestions.
References
[1] Mohamed S. Abdelfattah, Abhinav Mehrotra, łukasz Dudziak, and Nicholas D. Lane. Zero- Cost Proxies for Lightweight NAS. In International Conference on Learning Representations, 2021.
[2] Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. In International Conference on Learning Representations Workshop, 2018.
[3] Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Under- standing and simplifying one-shot architecture search. In International Conference on Machine Learning, pages 550-559, 2018.
[4] Yassine Benyahia, Kaicheng Yu, Kamil Bennani Smires, Martin Jaggi, Anthony C Davison, Mathieu Salzmann, and Claudiu Musat. Overcoming multi-model forgetting. In International Conference Machine Learning. pages
PMLR, 2019.
[5] Andrew Brock, Theodore Lim, James Millar Ritchie, and Nicholas J Weston. Smash: One-shot model architecture search through hypernetworks. In International Conference on Learning Representations, 2018.
[6] Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A thcoretically inspired perspective. In International Conference on Learning Representations, 2021.
[7] Xiangxiang Chu, Bo Zhang, Ruijun Xu, and Jixiang Li. Fairnas: Rethinking evaluation fairness of weight sharing neural architecture search. arXiv preprint arXiv: 00845,, 2019.
[8] Xuanyi Dong and Yang. One-shot neural architecture search via self-evaluated template network. In Proceedings of the IEEE International Conference on Computer Vision, pages 3681-3690, 2019.
[9] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
[10] Thomas Elsken, Jan Hendrik Metzen, Frank Hutter, et al. Neural architecture search: A survey, The Journal of Machine Learning Research, 20(55):1-21, 2019.
[11] Golnaz Ghiasi, Tsung- Yi Lin, and Quoc Le. Nas-fpn: Learning scalable feature pyramid architecture for object detection. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 7036-7045, 2019.
[12] Ronghao Guo, Chen Lin, Chuming Li, Keyu Tian, Ming Sun, Lu Sheng, and Junjie Yan. Powering one-shot topological nas with stabilized share-parameter proxy. In Proceedings of the European Conference on Computer Vision, pages 625-641. Springer, 2020.
[13] Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling. In Proceedings of the European Conference on Computer Vision, pages 544-560 Springer, 2020.
[14] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip HS Torr. Snip: Single-shot network pruning based on connection sensitivity. arXiv preprint 11x1v:1810002340, 2018.
[15] Ming Lin, Pichao Wang, Zhenhong Sun, Hesen Chen, Xiuyu Sun, Qi Qian, Hao Li, and Rong Jin. Zen-nas: A zero-shot nas for high-performance deep image recognition. In Proceedings of the IEEE International Conference on Computer Vision, pages 347-356, 2021.
[16] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv:1806 09055, 2018

---

[17] Vasco Lopes, Saeid Alirezazadeh, and Luis A Alexandre. Epe-nas: Efficient performance estimation without training for neural architecture search. arXiv preprint arXiv:2102.08099 2021.
[18] Renqian Luo, Tao Qin, and Enhong Chen. Balanced one-shot neural architecture optimization. arXiv preprint arXiv: 10815, 2019.
[19] Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie Liu. Neural architecture optimiza- tion. In Advances in Neural Information Processing Systems, pages 7816-7822 2018.
[20] Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley, Neural architecture search without training. arXiv preprint urXiv:2006. 04647, 2021.
[21] Joseph Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley. Neural architecture search without training. In International Conference on Machine Learning, 2021.
[22] Michael C Mozer and Paul Smolensky. Skeletonization: A technique for trimming the fat from a network via relevance assessment. In Advances in Neural Information Processing Systems, pages 107-115, 1989.
[23] Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, and Lihi Zelnik. Xnas: Neural architecture search with expert advice. Advances in Neural Information Processing Systems, 32:1977-1987, 2019.
[24] Xuefei Ning. Changcheng Tang, Wenshuo Li, Songyi Yang, Tianchen Zhao, Niansong Zhang, Tianyi Lu, Shuang Liang, Huazhong Yang, and Yu Wang. aw_nas: A modularized and extensible nas framework. arXiv preprint arXiv:2012. 103388, 2020.
[25] Xuefei Ning, Yin Zheng, Tianchen Zhao, Yu Wang, and Huazhong Yang. A generic graph-based neural architecture encoding scheme for predictor-based nas. In Proceedings of the European Conference on Computer Vision, 2020.
[26] Daniel S Park, Jachoon Lee, Daiyi Peng, Yuan Cao, and Jascha Sohl-Dickstein. Towards nngp-guided neural architecture search. arXiv preprint arXiv:2011 1,00066, 2020.
[27] Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, pages 4095-4104. PMLR, 2018
[28] Alois Pourchot, Alexis Ducarouge, and Olivier Sigaud. To share or not to share: A comprehen- sive appraisal of weight-sharing. arXiv preprint wxXiv2002..02289 2020.
[29] Iliaa Radosavovic, Justin Johnson, Saining Xie. Wan-Yen Lo, and Piotr Dollár. On network design spaces for visual recognition. In Proceedings of the IEEE International Conference on Computer Vision, pages 1882-1890) 2019.
[30] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence. volume 33, pages
2019.
[31] Binxin Ru, Clare Lyle, Lisa Schut, Miroslav Fil, Mark van der Wilk, and Yarin Gal. Speedy performance estimation for neural architecture search, 2021.
[32] Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas-bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008.0 09777, 2020.
[33] Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint arXiv:2006.05450 2020.
[34] Lucas Theis, Iryna Korshunova, Alykhan Tejani, and Ferenc Huszár. Faster gaze prediction with dense networks and fisher pruning. arXiv preprint
2018. [35] Jack Turner, Elliot J Crowley, Michael O' O'Boyle, Amos Storkey, and Gavin Gray. Block- swap: Fisher-guided block substitution for network compression on budget. arXiv preprint
1906.4/906.04/3 2019.
[36] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. arXiv preprint arXiv:2002.07376, 2020.
[37] Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. Advances in Neural Information Processing Systems, 2020.
12

---

[38] Colin White, Arber Zela, Binxin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? arXiv preprint arXiv:2104.011 10000400177 077, 2021.
[39] Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang. Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: aardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10734-10742, 2019.
[40] Zhaohui Yang, Yunhe Wang, Xinghao Chen, Boxin Shi, Chao Xu, Chunjing Xu, Qi Tian, and Chang Xu. Cars: Continuous evolution for efficient neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattrn Recognition, pages 1829-1838, 2020.
[41] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pages 7105-7114. PMLR, 2019.
[42] Kaicheng Yu, René Ranftl, and Mathieu Salzmann. How train your super-net: An analysis of training heuristics in weight-sharing NAS. abs/2003.042111 2020.
[43] Kaicheng Yu, Christian Sciuto, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. In International Conference Learning Representations, 2020.
[44] Arber Zela, Julien Siems, and Frank Hutter. Nas-bench- Ishotl: Benchmarking and dissecting one-shot neural architecture search. In International Conference Learning Representations, 2020.
[45] Chris Zhang. Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. In International Conference on Learning Representations, 2019.
[46] Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, and Steven Su. Overcoming multi-model forgetting in one-shot nas with diversity maximization. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2020.
[47] Yuge Zhang, Zejun Lin, Junyang Jiang, Quanlu Zhang, Yujing Wang, Hui Xue, Chen Zhang, and Yaming Yang. Deeper insights into weight sharing in neural architecture search. arXiv preprint arXivv2001.0143/ 2020.
[48] Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations, 2017.
13


Reviews:
[{"review_id": "mB3C3Q_9nz5", "reviewer": "Reviewer_SU6e", "summary": "Neural Architecture Search aims to identify neural network architectures from a human-designed search space which have good accuracies, or good accuracy/size tradeoffs. The submission explores how a number of different design choices affect how well existing heuristics can identify/rank promising architectures from a search space. The submission focuses on two classes of heuristics:\n* One-shot models/estimators, which use a single shared set of weights to evaluate/rank many different candidate architectures,\n* Zero-shot estimators, which try to evaluate/rank different candidate architectures without any training at all.\n\nExperiments are conducted on the NASBench-101, NASBench-201, and NASBench-301 benchmark tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Overview\nThe submission conducts a variety of experiments on NASBench-101/201/301, with the goal of understanding how different design choices affect the ability of one-shot models and zero-shot estimators to rank different candidate architectures in a NAS search space.\n\nThe submission is an analysis paper, and does not claim to propose a new method. It feels like a large collection of results related to one-shot / zero-shot architecture search, which may be useful for practitioners.\n\nOn the positive side, the submission presents some interesting and surprising findings, and provides plausible explanations. For example, in Section 4.1, the authors observe a counterintuitive effect where evaluating on more examples leads to lower one-shot model accuracies, and provide a plausible explanation (basically: this may be a quirk in the way their metrics are defined; evaluating on fewer examples increases the likelihood of ties, or cases where two architectures will have exactly the same estimated accuracy).\n\nOn the negative side, I frequently had the feeling that the submission was trying to pack too much information into too little space, with some unfortunate consequences. For example:\n* I didn't see details about how one-shot models were trained in the main paper. Some additional information was provided in a zip file in the supplementary material, but unless I missed something, this seems like a surprising and unfortunate omission.\n* In a few plots, the legends occlude/cover up relevant data points (Figures 3, 8, and 10).\n* A few plots have a large number of overlapping lines, which made them difficult for me to interpret (e.g., Figure 1, Figure 8, Figure 10, Figure 11).\n* Textual descriptions of plots and results are sometimes very short and a bit hard to follow, perhaps because of space constraints. I'm particularly confused about how to interpret Figure 3 (right).\n\n\n\nHighlights of experimental results for one-shot models:\n* Effect of training time on one-shot model performance for different NABench-101/201 (Section 4.1 / Figure 1) and NABench-301 (Section 4.1 / Figure 3).\n* Effect of increasing the number of evaluation examples used to estimate accuracy when using a one-shot model to evaluate a candidate architecture.\n* Analysis of one-shot models on different slices of the search space (e.g., ability of a one-shot model to rank large vs small architectures; ability of a one-shot model to identify the top vs. bottom 5% of network architectures, bias towards low-FLOPs vs. high-FLOPs architectures).\n* Some experiments related to ensembling multiple one-shot models (Section 5.3 / 6.1).\n* Experiments with sampling heuristics proposed by the FairNAS paper (Section 6.2), although I'm not sure exactly which sampling heuristic the submission was referring to.\n* Experiments on how restricting the search space affect one-shot model quality (Section 6.3).\n\nHighlights of experimental results for zero-shot estimators:\n* Section 4.2 evaluates five different (previously proposed) zero-shot estimators on NASBench-201/301: \"plain, snip, grasp, synflow, and fisher\".\n* The paper's main results for zero-shot estimators seem to come from Table 2, which measures how strongly correlated the zero-shot estimators' outputs are with each other, as well as with other metrics such as \"ground-truth\" accuracies, FLOPs, and parameter counts, and one-shot estimators.\n* The submission also touches on experiments evaluated zero-shot estimators for trained vs. untrained networks, although data is only provided in an appendix.\n* Some discussion/analysis of biases of zero-shot estimators (e.g., favoring architectures with more parameters, or which do not have skip-connections).\n\n\n# Detailed Comments\nL94:  \"However, the correlation [reported by Zhang et al. [32]] is evaluated using 100 architectures randomly sampled from a large search space, which is not a convincing and consistent benchmark metric.\"\n\nIt would be helpful if the authors could provide more details to support their assertion that this approach is not \"convincing and consistent,\" since this isn't obvious to me. Or else rephrase their claim. I agree that the submission's analysis is complementary to Zhang et al.'s. But it seems like using benchmark datasets like NASBench-101/201/301 (which the submission focuses on) comes with a different set of pros and cons (e.g., artificially small search space size in NASBench-101/201; model quality is estimated using a surrogate predictor instead of a ground-truth measurement in NASBench-301).\n\nL107: \"Mellor et al propose ta indicator based on [...]\"\nWhat is \"ta indicator\"? Is this a typo?\n\nDoes the submission provide details about the training setup used for Section 4?\n\nFigure 1 (\"Criteria of using OS accuracy/loss as estimations\"):\n* It's not clear to me what \"Oneshot Average\" refers to. I didn't notice any reference to it in the \"Evaluation Criteria\" section.\n* It's not clear to me what learning rate schedule is used. I think this needs to be documented, since it can potentially affect the paper's conclusions. For example: if a model is trained with cosine or linear decay, we may need to adjust the learning rate schedule if the number of training epochs is reduced.\n\nL165: \"Another fact is that one-shot (OS) estimations are better at distinguish bad architecture (higher P@bottom5%) than distinguishing good ones (lower P@top5%).\"\n\nLooking at Figure 1, it seems like this is true for NASBench-201 and NASBench-301 but just the opposite is true for NASBench-101 (1shot sub 3)?\n\nL182: I initially had trouble parsing the following text: \"For example, as shown by NB301 results in Fig. 3, criteria get better when the batch number increases from 1 to 10 at epoch 1000.\" My current interpretation is that the authors are computing average model accuracies over N batches, where each batch contains 128 examples. But if so, it would be helpful to update the phrasing to clarify what the \"batch number\" is.\n\nLayout of Figure 3 should be adjusted, since the plot legend currently obscures some of the results.\n\nI don't understand the \"Intra-Level KD\" plot in Figure 3.\n\nL322: \"As expected, averaging the OS accuracy of multiple supernets stabilizes OSE [one-shot] estimations.\"\nI had trouble understanding figuring out which data supports this claim. Figure 8 (b) - middle shows relP@top/bottom 5% for single models vs. ensembles, and these results seem consistent with the authors' claim. But for some reason, relative Kendall's tau only seems to be reported for single models in Figure 8 (b) - left.\n\nL367: \"Sec. 5.3 shows that averaging OS scores of several supernets stabilizes the estimations, but this is not practical due to the linearly enlarged consumption.\"\n\nIt's not clear to me what the authors mean by \"linearly enlarged consumption\", or why the authors believe that this approach is not practical. (If the authors' argument is that temporal ensembling has lower training cost than training separate models, the claim seems reasonable. But if this is the case, I'd suggest updating the phrasing to make the meaning clearer.)\n\nFigure 10:\n* The plot in the lower right-hand corner is partially obscured by the legend.\n* Temporal ensembling clearly outperforms single-model estimation at the start of training. But it's not clear to me from the figure whether it's actually any better at the end of training (after 1k epochs). The blue (\"single\") and green (\"temporal ensemble 5 ckpts\") lines seem quite close together at the end of training.\n\nL374: \"We also adapt Fair-NAS sampling strategy to the NB201/301 spaces (a special case of MC sampling 5/7 for 201/301).\"\n\nI'm a bit unsure of the terminology (\"sampling 5/7\") and it's not clear to me whether \"Fair-NAS sampling strategy\" refers to the paper's notion of \"Strict Fairness\" or something else. It would be helpful to clarify this.\n\nI found Figure 11 (top left) difficult to read because the \"post-deiso\" [post-deisomorphic sampling] and \"no post-deiso\" lines are basically on top of each other, it looks like there's just a single line in the plot (with a symbol that doesn't appear in the legend). I'm a bit unsure of whether this supports the submission's claim that \"Post-deiso achieves slight improvements over \"no post-deiso\".\n\n## Post-Rebuttal Update\nI've updated my review score from 6 to 7. Please see my response below for a detailed rationale.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "In order to avoid training/evaluating many network architectures from scratch, experiments are conducted only on NASBench-101/201/301. On its own, each of these benchmark tasks has significant limitations (listed below). However, since the different benchmark tasks have different strengths and weaknesses, I think reporting results on all three (as the submission does) should be sufficient for a NeurIPS paper.\n* NASBench-101 and NASBench-201 are -- by design -- very small search spaces (e.g., there are around 423,000 unique architectures for the full NASBench-101 dataset, and much less for NASBench-201), which could skew the conclusions.\n* NASBench-301 uses a much larger search space containing 10^18 architectures. However, so-called \"ground-truth accuracies\" from this dataset actually come from a surrogate regression model. This introduces a different type of skew, since we can penalize a model whose performance is underestimated by the surrogate (i.e., has low predicted performance according to the surrogate but would perform better if we were to actually train/evaluate it).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "bpHPokJNxeL", "reviewer": "Reviewer_WA1h", "summary": "Weight sharing is a very important technique in NAS to speed up the search and reduce resources.\nHowever, such technique suffers from performance drop, and attracts a lot of interset from the community to investigate into it.\nThis paper is one of the works that investigate the behavior and underline principles of such weight sharing technique (aka one-shot). Besides it also investigate current popular zero-shot estimators.\nThe paper analyzes the one-shot and zero-shot estimators from multiple perspectives on three benchmark datasets, with sufficient experiments and further suggestions. \nThough some of the points/findings are not novel and well-known, the sufficient experiments still make a convening verification on these.\nIt will bring much to the community. The findings and suggestions will make using one-shot and zero-shot NAS easier for practitioners.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Weight sharing is a very important technique in NAS to speed up the search and reduce resources.\nPrevious works analyzed the issues/problems in one-shot estimators with weight sharing from several handful points.\nThis work conducts a more comprehensive study on one-shot estimators, as well as recent popular zero-shot estimators, from a quantative way, with metrics such as KD, SpearmanR, Precision, BR, etc.\nIt contains multiple aspects within the estimators that affect the performance, compared to previous works.\nThough some points are not new and well-known, the paper still conducts experiments across three representative benchmark datasets to further verify them.\nOverall, this paper conducts broad and comprehensive study on one-shot and zero-shot estimators, that would benefit the community a lot.\n\nHowever, there are still some issues/questions:\n1. Line 51, \"knowledge revealed by our work include\", however, 1) and 3) are not only revealed by you.\n2. Line 58, what does \"inter-parameters sensitivity\" mean?\n3. Line 62, what does \"inter-architecture difference\" refer to?\n4. Line 140, the A_K is a set of architectures rather than the indices. The subscript of argmin_{i\\in{A_K}} seems not correct. if i\\inA_{K}, then i is an architecture here, and cannot be used to index r_i.\n5. The same to point 4 in Line 144.\n6. In Figure 1 caption, if left Y axis if the OS loss value, then what is the right Y axis? The right Y axis cannot be metrics since the scales are large than 1.0. Is this a typo？\n7. In Line 170, the finding is interesting. Do you have explanation or guess for this, because this is really important to guide the future work and practical use of NAS in different tasks.\n8. In Line 190-192, what do \"levels\" and \"smaller resolution\" mean here? BTW, if 1 batch gives many ties at early epochs, it means the architectures are hard to be distinguished and ranked propersly. Then how can the metrics be higher than that of 1- batches?\n9. Figure 3. It would be better if the values on the X axis are integers. Just a suggestion.\n10. In Line 315-316, why is the latter one taken as the GT? I think taking the ground-truth ranking as the GT is more reasonable.\n11. Line 333, how many architecture pairs do you select?\n12. Line 371, what is 3/5 here? Do you mean \\frac{3}{5}? If so, how does the number come?\n13. Line 373, what does MC mean? It is mentioned without explanation.\n14. Some points are not new to the community. Though the authors further verify them through extensive and convincing experiments, the authors should refer to those works (e.g., training longer leads to better ranking, complex network converge slower than simple ones in one-shot training, skip connections are overestimated in supernet training.)\n15. Some metrics or points differ across the three benchmark datasets. Then the authors should summarize or analyze the common/different points/underline principles of the three search spaces that lead to the different behaviors. This shall be a big contribution to the community for the practitioners to apply the tricks to their tasks regarding the search space they design.\n16. Why your one-shot Kendall tau results on NAS-Bench 201 in Figure 1 and Table A1 in Appendix can reach 0.744? As far as I know, previous work can only reach 0.54 [1][2] (even few-shot [2] can only reach 0.752 with 125 supernets).\n17. In Appendix A.3.4, you provide two views for pruning: per-architecture and per-decision. Can you provide more explanations of their differences?\n18. Figure 2 presents the accuracy/loss distribution where accuracy distribution is more concentrated than loss. But I cannot figure out why it indicated the loss carries more information about prediction confidence. Can you provide more insights or explanations?\n\nReferences:\n[1] Hu, Yiming, et al. \"Angle-based search space shrinking for neural architecture search.\" European Conference on Computer Vision. Springer, Cham, 2020.\n[2] Zhao, Yiyang, et al. \"Few-shot neural architecture search.\" International Conference on Machine Learning. PMLR, 2021.\n\nI would consider my final rating based on the authors` responses and other reviewers' comments.\n\nTypos/Grammar:\n1. Line 35, supernets -> supernet\n2. Line 107, ta -> a\n3. Line 137, is -> are", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "XZ6RTdtDCkS", "reviewer": "Reviewer_Q7zt", "summary": "This paper gives evaluations of methods to evaluate the performance of a neural network before it is fully trained. This has applications to neural architecture search (NAS). Specifically, the authors study two types: one-shot estimators (OSEs) and zero-shot estimators (ZSE) which have both been popular recently. The authors give a large study of various aspects of these methods. They give several new insights about biases in their performance and ideas to mitigate them. All experiments are conducted on three popular search spaces: nas-bench-1shot1, nas-bench-201, and nas-bench-301.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n- The authors give some good insights into OSE’s and ZSE’s. The ones I find particularly interesting are\n   - Improving OSE performance by de-isomorphic sampling. The sampling routine is not studied much in NAS, and the authors find that sampling by weighting all isomorphisms equally, improves performance.\n   - The fact that some of the ZSE’s consistently overestimate larger architectures and underestimate smaller architectures is interesting and can lead to better NAS methods. They also show this is true in OSEs.\n   - The analysis for OSEs on overestimating vs underestimating based on nparams flops and ops is also interesting.\n- The type of analysis in this work is very beneficial to the NAS community, so this paper can have high impact.\n\n### Weaknesses\n- For this type of project, novelty is low. On the other hand, I think that the field of neural architecture search is greatly in need of this type of analysis, so this type of project is more important than yet another novel algorithm.\n- There are some papers that also evaluate performance estimators which overlap with some experiments conducted by the authors. These should be added to the related work, with a short discussion of the differences. Since there is some overlap, this reduces the paper’s impact a little.\n   - [1], [2], [3], and [4] attempt to run large evaluations of performance estimators. In particular, [2] ran experiments with several zero-cost methods on nas-bench-101, nas-bench-201, and nas-bench-301. [3] has experiments with ZSE’s on nas-bench-201, and other search spaces as well. So the impact for ZSE experiments is reduced. [4] runs evaluations of super-net training, so it would be good to explain the differences.\n   - As a side note, [5] also has overlap, since it shows ZSE’s perform worse as the model is trained, but this is concurrent work so it does not count against the authors.\n- Some of the insights mentioned by the authors are a bit shallow or need more justification.\n   - Line 56, it is expected that ZSEs would perform worse than OSEs, since ZSEs take less time to run. \n   - Line 61, it is expected that training for longer would make one-shot estimations better. \n   - The authors claim that OSEs are better at ranking worse architectures, but the distribution of architecture accuracies is skewed left, so this is a big confounding factor in that claim.\n   - Line 153, \"on larger search spaces, the training time should be longer\", cannot really be concluded after looking at just 2 or 3 search spaces.\n- For this type of project that evaluates popular methods in the field of NAS, citing and describing all of the related work is important. But there are some methods missing.\n   - ZSE’s: [6] [7] [8] [9]\n   - OSE’s: [10] [11] \n- Unfortunately, the authors only provided some of their code, and left a note saying that it was too challenging to anonymize their code. Therefore, this project does not yet have high reproducibility unless they include the full code. During the rebuttal period, if they have time, they can upload the anonymized code. The following type of linux command is helpful to remove a phrase from all files in a repo: \n```\ngrep -rl John\\ Smith . | xargs sed -i '' ’s/John\\ Smith/xxxx\\ xxxxx/g’\n```\nI believe this paper can be impactful in the NAS community, but there are currently several weaknesses. I am giving this paper a weak reject, but I am willing to increase my score if the weaknesses are partially or fully addressed.\n\n### Additional minor feedback\n- Fig 5 is hard to understand. The y axis is labeled, and the caption also labels the y axis? What is the x axis?\n- Section 4.1 jumps into an experiment without explaining the methodology; They should refer back to it\n- What is linear correlation in fig 1?\n- Line 167 “as shown in the appendix figure” Which appendix figure?\n- The text (titles, axes, legends, etc) in fig. 4, 6, 7, 8, 9, 11 are too small and need to be increased \n- Line 268, “actually, this is evident from the formula” should be explained in a bit more detail\n\nReferences\n- [1] https://arxiv.org/abs/2008.03064 (A Surgery of the Neural Architecture Evaluators)\n- [2] https://arxiv.org/abs/2104.01177 (How Powerful are Performance Predictors)\n- [3] https://arxiv.org/abs/2006.04492 (Speedy Performance Estimation)\n- [4] https://arxiv.org/abs/2003.04276 (How to Train Your Super-Net)\n- [5] https://arxiv.org/abs/2106.04010 (FEAR)\n- [6] https://openreview.net/forum?id=Cnon5ezMHtu (NTK)\n- [7] https://arxiv.org/abs/2011.06006 (NNGP)\n- [8] https://arxiv.org/abs/2102.08099 (EPE-NAS)\n- [9] https://arxiv.org/abs/2102.01063 (Zen-NAS)\n- [10] https://arxiv.org/abs/2002.04289 (To Share or not to Share)\n- [11] https://arxiv.org/abs/2001.01431 (Deeper Insights into Weight Sharing)\n\n=====================\n\nUpdate: After discussion, the authors have addressed my concerns and I am raising my score from 5 to 6. The most notable changes the authors claim are (1) releasing the full code, (2) additional related work discussion, (3) theoretical motivation that synflow prefers larger architectures, (4) making sure important information such as experimental setups are in the main paper, and (5) revising the claim that all ZSEs are outperformed by the param baseline.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors answered yes to 1.b, but I do not see a discussion of limitations anywhere. Can the authors point it out to me? Also, the authors only discuss the societal impacts in the checklist itself. The NeurIPS call for papers said that “the page limit was increased to ensure that the authors have space to address the checklist questions” so these should have been addressed in the main body.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "QCDmp3989X", "reviewer": "Reviewer_ekzD", "summary": "This work analyzes several one-shot and zero-shot NAS methods on multiple NAS benchmark datasets. The authors inspect NAS algorithms from various aspects, including training bias, stability, variance, loss ranking v.s. accuracy ranking, etc. . The authors conclude that one-shot methods and zero-shot methods might fail to work due to multiple reasons and propose several solutions to alleviate these issues.", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Strength]\n\nThe paper is well-written and very easy to follow. The authors did an excellent job in analyzing one-shot and zero-shot NAS methods, with deep insight and comprehensive ablation studies. These results provide a clear picture of when and why one method works or fails under a specific setting. I believe this study will inspire more future works in one-shot and zero-shot NAS works.\n\nThere are many empirical studies showing that one-shot NAS is unstable. However, I am still impressed by the analysis presented in this work. The authors give a much clear picture of how these NAS methods fail to work systematically. Especially, the authors analyze the behavior of NAS methods by grouping them in different size, FLOPs and accuracy, and report their performance by various indices. While some characteristics of one-shot/zero-shot NAS methods have been analyzed in previous works, a majority of them are revealed for the first time. \n\n[Weakness]\n\nIt is hard to point out obvious weakness of this work. The following are suggestions for potential improvements:\n\n1) While this work focuses on one-shot NAS more than zero-shot NAS, it is more interesting to investigate why zero-shot NAS fail to match the performance of one-shot NAS and how to fix these issues in zero-shot NAS. Is it possible that zero-shot NAS can outperform one-shot NAS under a particular setting?\n\n2) Most experiments in this work are conducted via passive sampling (uniform sampling or random sampling on existing architectures). In recent zero-shot NAS methods, the algorithm can actively sample structures. This will make the two distributions considerably different. For example, a zero-shot method might work well in high-accuracy regime but poorly in low-accuracy regime. Since networks of high accuracy are difficult to sample via uniform sampling, the evaluation of zero-shot NAS in this work might be incomplete.\n\n3) No validation on ImageNet. It is not clear whether the conclusions of this work still hold on ImageNet or other large-scale datasets.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No foreseeable risk of negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper goes deep into the issues of one-shot supernet based NAS methods as well as recent zero-cost NAS methods. The authors have done an excellent job analyzing empirically the various issues and suggesting improvements to one-shot estimators like de-isomorphic sampling and the fact that zero-cost ones consistently overestimate the performance of larger networks (and the short proof of it) and so on.

During the rich discussion phase one concern that consistently came up was that the paper was packing a lot of dense information (see concerns of reviewer SU6e) and at times it was hard to read because of that. But the reviewers and authors have excellent suggestions on improving the readability. Please incorporate those aspects into the manuscript. 

Reviewer Q7zt has suggested a number of improvements including citations to other relevant work and even concurrent work that should be included in the next version. Also the new results using the original implementation 'relu_logdet' and the changed conclusion with respect to number of params. 

Overall this paper presents valuable insights to the NAS community!
  
 
Decision: Accept (Poster)