Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: Weight sharing is a very important technique in NAS to speed up the search and reduce resources.
However, such technique suffers from performance drop, and attracts a lot of interset from the community to investigate into it.
This 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.
The paper analyzes the one-shot and zero-shot estimators from multiple perspectives on three benchmark datasets, with sufficient experiments and further suggestions. 
Though some of the points/findings are not novel and well-known, the sufficient experiments still make a convening verification on these.
It will bring much to the community. The findings and suggestions will make using one-shot and zero-shot NAS easier for practitioners.
main_review: Weight sharing is a very important technique in NAS to speed up the search and reduce resources.
Previous works analyzed the issues/problems in one-shot estimators with weight sharing from several handful points.
This 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.
It contains multiple aspects within the estimators that affect the performance, compared to previous works.
Though some points are not new and well-known, the paper still conducts experiments across three representative benchmark datasets to further verify them.
Overall, this paper conducts broad and comprehensive study on one-shot and zero-shot estimators, that would benefit the community a lot.

However, there are still some issues/questions:
1. Line 51, "knowledge revealed by our work include", however, 1) and 3) are not only revealed by you.
2. Line 58, what does "inter-parameters sensitivity" mean?
3. Line 62, what does "inter-architecture difference" refer to?
4. 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.
5. The same to point 4 in Line 144.
6. 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？
7. 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.
8. 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?
9. Figure 3. It would be better if the values on the X axis are integers. Just a suggestion.
10. 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.
11. Line 333, how many architecture pairs do you select?
12. Line 371, what is 3/5 here? Do you mean \frac{3}{5}? If so, how does the number come?
13. Line 373, what does MC mean? It is mentioned without explanation.
14. 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.)
15. 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.
16. 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).
17. In Appendix A.3.4, you provide two views for pruning: per-architecture and per-decision. Can you provide more explanations of their differences?
18. 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?

References:
[1] Hu, Yiming, et al. "Angle-based search space shrinking for neural architecture search." European Conference on Computer Vision. Springer, Cham, 2020.
[2] Zhao, Yiyang, et al. "Few-shot neural architecture search." International Conference on Machine Learning. PMLR, 2021.

I would consider my final rating based on the authors` responses and other reviewers' comments.

Typos/Grammar:
1. Line 35, supernets -> supernet
2. Line 107, ta -> a
3. Line 137, is -> are
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: ### Strengths
- The authors give some good insights into OSE’s and ZSE’s. The ones I find particularly interesting are
   - 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.
   - 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.
   - The analysis for OSEs on overestimating vs underestimating based on nparams flops and ops is also interesting.
- The type of analysis in this work is very beneficial to the NAS community, so this paper can have high impact.

### Weaknesses
- 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.
- 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.
   - [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.
   - 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.
- Some of the insights mentioned by the authors are a bit shallow or need more justification.
   - Line 56, it is expected that ZSEs would perform worse than OSEs, since ZSEs take less time to run. 
   - Line 61, it is expected that training for longer would make one-shot estimations better. 
   - 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.
   - 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.
- 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.
   - ZSE’s: [6] [7] [8] [9]
   - OSE’s: [10] [11] 
- 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: 
```
grep -rl John\ Smith . | xargs sed -i '' ’s/John\ Smith/xxxx\ xxxxx/g’
```
I 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.

### Additional minor feedback
- Fig 5 is hard to understand. The y axis is labeled, and the caption also labels the y axis? What is the x axis?
- Section 4.1 jumps into an experiment without explaining the methodology; They should refer back to it
- What is linear correlation in fig 1?
- Line 167 “as shown in the appendix figure” Which appendix figure?
- The text (titles, axes, legends, etc) in fig. 4, 6, 7, 8, 9, 11 are too small and need to be increased 
- Line 268, “actually, this is evident from the formula” should be explained in a bit more detail

References
- [1] https://arxiv.org/abs/2008.03064 (A Surgery of the Neural Architecture Evaluators)
- [2] https://arxiv.org/abs/2104.01177 (How Powerful are Performance Predictors)
- [3] https://arxiv.org/abs/2006.04492 (Speedy Performance Estimation)
- [4] https://arxiv.org/abs/2003.04276 (How to Train Your Super-Net)
- [5] https://arxiv.org/abs/2106.04010 (FEAR)
- [6] https://openreview.net/forum?id=Cnon5ezMHtu (NTK)
- [7] https://arxiv.org/abs/2011.06006 (NNGP)
- [8] https://arxiv.org/abs/2102.08099 (EPE-NAS)
- [9] https://arxiv.org/abs/2102.01063 (Zen-NAS)
- [10] https://arxiv.org/abs/2002.04289 (To Share or not to Share)
- [11] https://arxiv.org/abs/2001.01431 (Deeper Insights into Weight Sharing)

=====================

Update: 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.
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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.
main_review: [Strength]

The 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.

There 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. 

[Weakness]

It is hard to point out obvious weakness of this work. The following are suggestions for potential improvements:

1) 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?

2) 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.

3) No validation on ImageNet. It is not clear whether the conclusions of this work still hold on ImageNet or other large-scale datasets.

limitations_and_societal_impact: No foreseeable risk of negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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:
* One-shot models/estimators, which use a single shared set of weights to evaluate/rank many different candidate architectures,
* Zero-shot estimators, which try to evaluate/rank different candidate architectures without any training at all.

Experiments are conducted on the NASBench-101, NASBench-201, and NASBench-301 benchmark tasks.
main_review: # Overview
The 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.

The 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.

On 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).

On 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:
* 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.
* In a few plots, the legends occlude/cover up relevant data points (Figures 3, 8, and 10).
* 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).
* 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).



Highlights of experimental results for one-shot models:
* 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).
* Effect of increasing the number of evaluation examples used to estimate accuracy when using a one-shot model to evaluate a candidate architecture.
* 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).
* Some experiments related to ensembling multiple one-shot models (Section 5.3 / 6.1).
* 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.
* Experiments on how restricting the search space affect one-shot model quality (Section 6.3).

Highlights of experimental results for zero-shot estimators:
* Section 4.2 evaluates five different (previously proposed) zero-shot estimators on NASBench-201/301: "plain, snip, grasp, synflow, and fisher".
* 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.
* The submission also touches on experiments evaluated zero-shot estimators for trained vs. untrained networks, although data is only provided in an appendix.
* Some discussion/analysis of biases of zero-shot estimators (e.g., favoring architectures with more parameters, or which do not have skip-connections).


# Detailed Comments
L94:  "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."

It 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).

L107: "Mellor et al propose ta indicator based on [...]"
What is "ta indicator"? Is this a typo?

Does the submission provide details about the training setup used for Section 4?

Figure 1 ("Criteria of using OS accuracy/loss as estimations"):
* It's not clear to me what "Oneshot Average" refers to. I didn't notice any reference to it in the "Evaluation Criteria" section.
* 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.

L165: "Another fact is that one-shot (OS) estimations are better at distinguish bad architecture (higher P@bottom5%) than distinguishing good ones (lower P@top5%)."

Looking 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)?

L182: 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.

Layout of Figure 3 should be adjusted, since the plot legend currently obscures some of the results.

I don't understand the "Intra-Level KD" plot in Figure 3.

L322: "As expected, averaging the OS accuracy of multiple supernets stabilizes OSE [one-shot] estimations."
I 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.

L367: "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."

It'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.)

Figure 10:
* The plot in the lower right-hand corner is partially obscured by the legend.
* 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.

L374: "We also adapt Fair-NAS sampling strategy to the NB201/301 spaces (a special case of MC sampling 5/7 for 201/301)."

I'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.

I 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".

## Post-Rebuttal Update
I've updated my review score from 6 to 7. Please see my response below for a detailed rationale.
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.
* 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.
* 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_title: null

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)