Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 
Summary:

The authors propose a new benchmark for evaluating surrogate functions for architecture search. According to the authors, existing tabular architecture search benchmarks are insufficient for this purpose due to using overly small search spaces. The main difference of this benchmark and other existing architecture search benchmarks such as NAS Bench 101 and NAS Bench 201 is that they do not attempt to evaluate all the architectures in the search space and do so for a much larger search space (DARTS). The authors then use this new dataset to show that surrogate functions are better than tabular estimators (error wise; although some lower performance architectures were discarded to make this case). Additionally, the authors compare the proposed benchmark (based on surrogate functions) with a real benchmark and observe that the results are qualitatively similar. Finally, the authors show that reevaluate the claim that local search is state-of-the-art for architecture search and find that, using their benchmark, that local search is still state-of-the-art provided that enough computational budget is available for the experiment.

Pros:
+ The paper presents a new dataset for architecture search that does not rely on exhaustive evaluation of all architectures in the search space. The experiments conducted that compare different surrogate functions on this benchmark are solid 
+ The paper suggests that building benchmarks for different search spaces can be accomplished through the surrogate function route where first a dataset of architectures is collected and then it is used to train a surrogate model. The surrogate function is then used as an interface between the search space and the search algorithm. This approach for building benchmarks is general and is likely to be useful in the construction of future benchmarks for architecture search. 

Cons:
- The fact that existing benchmarks for architecture search are insufficient for surrogate function evaluation and lead to wrong inferences is perhaps insufficiently supported. It is well known in architecture search work that existing search spaces (DARTS being one of them) have limited performance variability and that much of the performance variation ascribed to different architecture search methods can often be ascribed to differences in search spaces. Is a single search space good enough to mitigate these problems? For example, how do we guarantee that NAS Bench 301 is not just another dataset and guarantee that addresses some of the perceived problems with existing architecture search search spaces and benchmarks?


Comments: 
- Appendices weren't included in the submission.
- It would be interesting to discuss how this benchmark should be placed in the context of other existing benchmarks for architecture search to guide future practice.
- The motivation from Section 2 is rather sparse. It would be warranted to show that this trend is consistent with other metrics such as squared error and Kendall Tau (i.e., showing the ranks of different architectures are also preserved better).
- Insufficient information about the feature representation that is used for prediction?

review_title: The benefits of introducing a new benchmark could be better established

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: ****Update after rebuttal ****
I am increasing my rating for the paper as they did all the experiments I had asked for and updated the paper accordingly.
**************************

Summary:

While NAS has made tremendous advances in recent past, benchmarking algorithms with respect to each other still remains a challenge. Tabular benchmarks like 101 and 201, take a search space and train all possible architectures in them. While this is possible to do for relatively small search spaces and datasets, this is impractical to repeat for larger search spaces (e.g. DARTS' search space which has 10^18 architectures). 

This work makes the nice observation that a tabular benchmark treats each architecture as an independent random variable and doesn't utilize any similarities between them. Due to similarities in architecture space, knowing the train/val/test accuracy of one architecture tells us a lot about other architectures nearby. So a predictive model trained on a sparse subset of architectures can actually outperform an exhaustive tabular method.  

Lots of careful experiments are reported on the DARTS search space to create predictive models which can accurately predict architecture performance (accuracy, latency) and hence can be used as a 'simulator' by NAS algorithms for rapid research and fair comparison.

Comments:

- The paper is generally well-written and has thorough clean experiments! Thanks!

- My main concern is the following: The fact that the benchmark has added architectures encountered on the trajectory of well-known performing optimizers bothers me a bit. In the ideal world a benchmark should have no knowledge of any particular solution to the problem. This is true in the case of tabular benchmarks like 101 and 201. I understand the position that a surrogate model should be very good at predicting parts of the architecture space which optimizers are most likely to visit. Can we construct surrogates without knowing anything about any particular optimizers the community may invent in the future?

One part of an ablation study answering this question has been presented in Appendix E.2 where a model has been only trained on well-performing architectures (above 92% accuracy) and in Figure 21 has been found adequate for predicting the trajectories of BANANAS and Random Search (RS). This begs the question of what if we only used random sampling to fit surrogate models? (Of course coverage methods like adaptive submodularity-based greedy algorithms may result in even better performance). But can we do the easy baselines first for which the authors already have the data:

1.  Train surrogate model using only the 23746 architectures via random sampling and plot the same figures as in Fig 4 center and right. How much worse are they from current ones?

2. (if compute allows): Use up the entire budget of ~60k architectures in Table 2 only from random sampling and plot Fig 4 center and right.  How much worse are they from current ones?

3. (to have a fair comparison of current method to baseline 1 without using much more compute): Keep the total budget 23746 but fill them up in the same proportion from each method as currently in Table 2. For example RS will have 23746/~60k ratio, DE will have 7275/~60k ratio, etc. This will create "NASBench-301-small" which will have the same budget as baseline 1 above. Then plot Fig 4 center and right with both this and 1.  

These might be competitive baselines because the Once-For-All work from Cai et al. ICLR 2020 uses a regressor trained on 16k architectures sampled from a supergraph as a surrogate model to run evolutionary search against and obtain good performance. Also in this paper itself if more than 21500 architectures on 101 are used to train (unclear from the paper whether they were randomly sampled and diverged models rejected or some other technique was used to select them, since it says "subsets of D^{train}" but I think they were randomly sampled, right?), then that itself is better than the tabular benchmark.

Happy to be convinced if these are fair baselines or not. (Also possible that these are already included and I missed them. Ther are a lot of experiments :-))

-My other worry is that the LOOO ablation may be misleading since reasonable optimizers may be visiting similar parts of the architecture space hence may give a false sense of extrapolation.


review_title: Great effort! Some remaining questions.

final_score: rating: 7: Good paper, accept
review_content: ##########################################################################

Summary:

This work filled an important gap in the NAS benchmarks. The previous benchmarks only contain small search space due to the expensive cost of evaluation of neural architecture. In this search space, random search often becomes competitive in the narrow search space. Thus, to provide meaningful comparison, this work provided a benchmark in a large NAS search space (same as in DARTS), and using  surrogate models to predict validation performance of untrained neural architecture. The empirical results suggested using the surrogate benchmarks resulted in similar optimization trajectory as real evaluations and the author also shows one can derive/validate research ideas quickly with the benchmarks.
 
 
##########################################################################

Pros: 
 
1. This work filled an important gap in NAS benchmarks. 
2. The empirical results are very solid; the observation on the noise in the training is very insightful.
3. The work also contains guidelines for using the benchmarks.
4. The paper is very well written and contains enough detail for reproducibility.
 
##########################################################################

Cons: 

I only have some minor comments:

1. In Section 3.2, first paragraph, the author mentioned that validation and test error are highly correlated. This is clear if the poor performing architectures are included. But in practice, we are only interested in the good performing region, say top 5%, is the correlation still high between validation and test there?

2. In Section 4.2, second paragraph,  I am not sure I understand "We use train/val/test splits (0.8/0.1/0.1) stratified by the NAS
methods used for the data collection".

3. Given the mean and noise estimation based on the surrogate models, is the assumption there is gaussian and every experiment will draw one value from this gaussian? If so, could you state it clearly in the paper? If not, please clarify.

=====POST-REBUTTAL COMMENTS======== 

Initially I had only minor comments and the authors addressed all of them. I will keep my score.
review_title: Recommendation to Accept

final_score: rating: 3: Clear rejection
review_content: In this work, the authors train a model on a subset of architectures (~60k) in the DARTS search space and use this model to predict the performance of architectures outside of that subset in DARTS. They then use this as a surrogate for having to perform network training for evaluating NAS algorithms.

NAS benchmarks are a good thing, given that they facilitate NAS research outside of labs with lots of resources. Saying this, I think there are serious issues with this paper.

NAS-Bench-301 is a model that predicts the performance of networks in the DARTS search space. We know from https://arxiv.org/abs/1912.12522v3 that there is a significant lack of variety in the performance of models within this space, and this work compounds that. Additionally, this paper only considers CIFAR-10. This is a step back from NAS-Bench-201 which despite its small size, did contain multiple datasets. The compute used by the authors (training 60k networks) has gone into differentiating a bunch of networks that are all quite good, within a few percentage points of error. I’m not sure how this is of practical use.

A problem with NAS-Bench-101 and 201 is that the search spaces are small (423k, 6k) as the authors point out. NAS-Bench-301 encapsulates the DARTS search space which is much bigger (10^18). However, from https://arxiv.org/abs/1912.12522v3 we see that randomly sampling within this space gives networks between 96.5% and 97.5%. I would argue that it doesn’t matter how large a space is if it is lacking in variety; Every possible network works well enough. In 101/201 we see networks across a much larger range (typically between 80-95% although there are some much lower). I believe this is more interesting from a research perspective as we would like to apply NAS to situations where networks can break (and avoid this happening). The DARTS networks do explore a slightly higher accuracy range but it is not at state-of-art levels, so the added value is not clear.

The authors are critical of random search, stating (i) `random search stagnates and cannot identify one of the best architectures even after tens of thousands of evaluations`, (ii) NAS-Bench-201 (Dong & Yang, 2020) only contains 6466 unique architectures in total, causing the median of random search runs to find the best architecture after only 3233 evaluations.  However, (i) makes random search sound like it is failing, where on Figure 4 we can see at 10^4 (s) random search is doing very well  - matching or beating all the other techniques.  We know from https://arxiv.org/abs/1806.09055  that random search works well on the DARTS  space (probably due to the lack of variety). (ii) Random search does work well on NAS-Bench-201 but the DARTS algorithm fails, even though it works on this space. The statement in the abstract that using previous benchmarks  “leads to unrealistic results that do not transfer to larger search spaces.” does not tell the whole story, as there appears to be more going on than just the size of the search space. Some results on this large DARTS search space, do not transfer to the smaller search spaces. It seems that there is more to a search space than the number of architectures within it.

In terms of presentation, this paper is well written, although the figures could be larger. I appreciate that this is problem to keep within the page limit.

NAS benchmark papers are important and shape the direction of research in the field. This paper doesn’t present a benchmark. It provides a model that represents computationally-efficient means of getting network accuracies from the DARTS search space. I appreciate this endeavour and it could be of use outside of this space — being able to map a 10^18 space with 50000 points indicates that the effective size of the space is much smaller, and is highly predictable.

This space, although large, has very little variety in terms of network accuracy. I believe NAS-Bench-101 and 201 despite their sizes represent more varied search spaces. 201 also covers multiple datasets, whereas 301 only has CIFAR-10 (which it feels like we are saturating on).  I recommend rejection for this paper, as I do not believe it represents a step forward in the way we benchmark our NAS algorithms. We need to develop more interesting search spaces,  rather than advocating exploration of uninteresting ones.

review_title: Review

Meta-review: The contributions of this paper lie in two areas: a new benchmarking dataset and a new way to generate benchmarking datasets. Overall, the reviewers are split in their assessment based on which particular area they are focusing on. Reviewers who focus more on evaluating this work as a new benchmarking dataset, correctly point out that the variation within the search space has been shown to be limited and that the evaluation focuses on an overly-studied and toy (by today’s standards) dataset such a CIFAR-10. In terms of choice of dataset, this work is indeed a step backwards from nasbench201, which includes more datasets, although it is a step forward in terms of size of the search space. As one reviewer correctly points out “This paper doesn’t present a benchmark. It provides a model that represents computationally-efficient means of getting network accuracies from the DARTS search space”. The authors argue that the combination of the DARTS search space and its evaluation on CIFAR-10 is the de-facto evaluation standard in the NAS community, which is also true. Ultimately, benchmark datasets somewhat direct the attention of the community and this attention would be better directed elsewhere, not on DARTS+CIFAR-10, as pointed out by some of the reviewers.

On the other hand, this work is as much about a new benchmark as it is about a *protocol* to generate new benchmarks. Specifically, a big part of the appeal and novelty here lie in the idea of training a predictive model from a small subset of architecture evaluations. From this perspective, the authors showed evidence that their approach is sound, economical (in terms of computational cost) and robust to sources of bias in the selection of the architectures to evaluate. The limitation here is that this was only shown in search spaces that where either small or lacking diversity and thus it’s unclear how general its findings are.

Overall, this is very much a paper that could have gone either way in terms of acceptance. It’s a step in the right direction in terms of methodology that can be used to generate reproducible benchmarks in a computationally efficient way. It’s a step backwards in terms renewing focus on measures of performance that (arguably) we have all overfit to. 

Decision: Reject