Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This work proposes a query-based NAS approach, WeakNAS, which selects the best predicted architectures at each iteration, and then updates weak predictors iteratively. By using epsilon-greedy criteria to select new query data, WeakNAS bias the training data for the predictors to good subregion of the search space, leading to better modelling of the performance of good architectures at the expense of that of bad architectures. Empirically, the authors show that WeakNAS achieves SOTA performance on a variety of search spaces. However, the novelty of the work is rather weak. As the proposed framework is behind almost every query-based NAS and can be see as a simplified BO as the authors acknowledged and the design components (sampling strategy, predictor model) themselves are not novel as well.
main_review: **Strengths**: 
1.	The proposed method, WeakNAS, achieves very impressive empirical performance i.t.o query efficiency or final test accuracy on a variety of popular search spaces and datasets. The extensive experiment efforts are highly appreciated. This gives strong evidence supporting query-based NAS.
2.	The paper is well written and the method is well explained. 


**Weakness**:
The main weakness of the approach is the lack of novelty. 
1.	The key contribution of the paper is to propose a framework which gradually fits the high-performing sub-space in the NAS search space using a set of weak predictors rather than fitting the whole space using one strong predictor. However, this high-level idea, though not explicitly highlighted, has been adopted in almost all query-based NAS approaches where the promising architectures are predicted and selected at each iteration and used to update the predictor model for next iteration. As the authors acknowledged in Section 2.3, their approach is exactly a simplified version of BO which has been extensively used for NAS [1,2,3,4]. However, unlike BO, the predictor doesn’t output uncertainty and thus the authors use a heuristic to trade-off exploitation and exploration rather than using more principled acquisition functions.  
2.	If we look at the specific components of the approach, they are not novel as well. The weak predictor used are MLP, Regression Tree or Random Forest, all of which have been used for NAS performance prediction before [2,3,7]. The sampling strategy is similar to epsilon-greedy and exactly the same as that in BRP-NAS[5]. In fact the results of the proposed WeakNAS is almost the same as BRP-NAS as shown in Table 2 in Appendix C. 
3.	Given the strong empirical results of the proposed method, a potentially more novel and interesting contribution would be to find out through theorical analyses or extensive experiments the reasons why simple greedy selection approach outperforms more principled acquisition functions (if that’s true) on NAS and why deterministic MLP predictors, which is often overconfident when extrapolate, outperform more robust probabilistic predictors like GPs, deep ensemble or Bayesian neural networks. However, such rigorous analyses are missing in the paper.


**Detailed Comments**:
1.	The authors conduct some ablation studies in Section 3.2. However, a more important ablation would be to modify the proposed predictor model to get some uncertainty (by deep-ensemble or add a BLR final output layer) and then use BO acquisition functions (e.g. EI) to do the sampling. The proposed greedy sampling strategy works because the search space for NAS-Bench-201 and 101 are relatively small and as demonstrated in [6], local search even gives the SOTA performance on these benchmark search spaces. For a more realistic search space like NAS-Bench-301[7], the greedy sampling strategy which lacks a principled exploitation-exploration trade-off might not work well. 
2.	Following the above comment, I’ll suggest the authors to evaluate their methods on NAS-Bench-301 and compare with more recent BO methods like BANANAS[2] and NAS-BOWL[4] or predictor-based method like BRP-NAS [5] which is almost the same as the proposed approach. I’m aware that the authors have compared to BONAS and shows better performance. However, BONAS uses a different surrogate which might be worse than the options proposed in this paper. More importantly, BONAS use weight-sharing to evaluate architectures queried which may significantly underestimate the true architecture performance. This trades off its performance for time efficiency.
3.	For results on open-domain search, the authors perform search based on *a pre-trained super-net*. Thus, the good final performance of WeakNAS on MobileNet space and NASNet space might be due to the use of a good/well-trained supernet; as shown in Table 6, OFA with evalutinary algorithm can give near top performance already. More importantly, if a super-net has been well-trained and is good, the cost of finding the good subnetwork from it is rather low as each query via weight-sharing is super cheap. Thus, the cost gain in query efficiency by WeakNAS on these open-domain experiments is rather insignificant. The query efficiency improvement is likely due to the use of a predictor to guide the subnetwork selection in contrast to the naïve model-free selection methods like evolutionary algorithm or random search. A more convincing result would be to perform the proposed method on DARTS space (I acknowledge that doing it on ImageNet would be too expensive) without using the supernet (i.e. evaluate the sampled architectures from scratch) and compare its performance with BANANAS[2] or NAS-BOWL[4].
4.	If the advantage of the proposed method is query-efficiency, I’d love to see Table 2, 3 (at least the BO baselines) in plots like Fig. 4 and 5, which help better visualise the faster convergence of the proposed method. 
5.	Some intuitions are provided in the paper on what I commented in Point 3 in Weakness above. However, more thorough experiments or theoretical justifications are needed to convince potential users to use the proposed heuristic (a simplified version of BO) rather than the original BO for NAS.
6.	I might misunderstand something here but the results in Table 3 seem to contradicts with the results in Table 4. As in Table 4, WeakNAS takes 195 queries on average to find the best architecture on NAS-Bench-101 but in Table 3, WeakNAS cannot reach the best architecture after even 2000 queries.  
7.	The results in Table 2 which show linear-/exponential-decay sampling clearly underperforms uniform sampling confuse me a bit. If the predictor is accurate on the good subregion, as argued by the authors, increasing the sampling probability for top-performing predicted architectures should lead to better performance than uniform sampling, especially when the performance of architectures in the good subregion are rather close.
8.	In Table 1, what does the number of predictors mean? To me, they are simply the number of search iterations. Do the authors reuse the weak predictors from previous iterations in later iterations like an ensemble?


I understand that given the time constraint, the authors are unlikely to respond to my comments. Hope those comments can help the authors for future improvement of the paper.


**References**:
[1] Kandasamy, Kirthevasan, et al. "Neural architecture search with Bayesian optimisation and optimal transport." NeurIPS. 2018.
[2] White, Colin, et al. "BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search." AAAI. 2021.
[3] Shi, Han, et al. "Bridging the Gap between Sample-based and One-shot Neural Architecture Search with BONAS." NeurIPS. 2020.
[4] Ru, Binxin, et al. "Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels." ICLR. 2020.
[5] Dudziak, Lukasz, et al. "BRP-NAS: Prediction-based NAS using GCNs." NeurIPS. 2020.
[6] White, Colin, et al. "Local search is state of the art for nas benchmarks." arXiv. 2020.
[7] Siems, Julien, et al. "NAS-Bench-301 and the case for surrogate benchmarks for neural architecture search." arXiv. 2020.
limitations_and_societal_impact: The limitation and social impacts are briefly discussed in the conclusion.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors propose a progressively sampling approach to sample architecture-performance pairs for training performance predictors. The sampling subspace shrinks guided by the previous weak predictor. Experiments are conducted on NAS-Bench-101, NAS-Bench-201, and Open Domain Search (i.e. NASNet Search Space and MobileNet Search Space)
main_review: Concerns:

1. The proposed method is not well-justified. The progressively sampling approach seems to be biased to sample good-performing architectures. It is not clear why this could yield better results since this biased sampling could cause poorly predicted performance on under-sampled regions. Does this imply a biased sampled architecture set is good for training predictors? An ablation needs to be carried out to verify this. A simple ablated experiment could be training a strong predictor on a biased sampled architecture based on oracle and comparing it with uniform sampling.

2. The authors spend quite a few sentences to motive exploitation-exploration trade-off by sampling M architectures from TopN. However, in Table 2, sampling with M=10 and TopN=100 is only 0.01 better than sampling with M=10 and TopN=10. When searching in an open domain, it incurs $\frac{TopN-M}{M}$ times computation. it is not clear how much performance gain can bring by using this exploitation-exploration strategy. And this is not evaluated in the open domain search experiments.

3. In Table 3, the proposed method is about 0.1 better than LaNAS and BONAS. For 200 queries, the standard derivation is 0.14. It is not significant enough to conclude the method is truly better.

--------- post-rebuttal 1 --------- 

I raised my score from 4 to 5. I am willing to further raise my score if the Q2 is well-addressed during the rolling discussion.

--------- post-rebuttal 2 --------- 

After reading the response to Q2, I decided to my score from 5 to 6. However, reproducibility is still my main concern since the code is not provided. If the paper is accepted, I hope all the details and reproducible GitHub repo should be released publicly.
limitations_and_societal_impact: No.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: 
This paper proposes a new NAS method, which is a crucial step to rescue the NAS community. This paper achieves state-of-the-art results on several benchmarks, especially Open Domain Search on ImageNet. Sufficient experiments have been conducted to prove the effectiveness of the proposed method. Proper principled analyses have been provided to show the validness of the proposed method.


main_review: 

(Positive) I am really convinced by the motivation of this paper, especially by the impressive curve in Figure 1.

(Weakness) The motivation section needs to be improved. In the first paragraph, the authors say, "In order to cover the entire search space, they often train and evaluate a large number of architectures, leading to tremendous computation cost." This is not true. Gradient-based approaches and SPOS families do not have this limitation. Please revise this description.

(Positive) This paper studies the architecture-performance prediction, which is a crucial step in NAS. As we know, inaccurate architecture-performance prediction is the cause of ineffective NAS in almost all existing NAS methods. Given that most current NAS methods are based on weight-sharing NAS that also use shared weights to perform architecture-performance prediction, and given that many NAS methods are not better than the random architecture selection (suggested by two ICLR 2020 papers and many ICLR 2021 submissions), analyzing the architecture-performance prediction is an important step to rescue the NAS community. This paper takes a deep insight into the architecture-performance prediction, which provides a timely metric for evaluating NAS's effectiveness. 

Overall, this paper provides a timely analysis of the current NAS's ineffectiveness.  I recommend accepting this paper to rescue the NAS community.

I believe this paper deserves acceptance. As we know, variants of efforts have been made to improve NAS's effectiveness since 2016, and a great process has been reached. Despite the high expectation and solemn devotion, NAS's effectiveness is believed to be still low. This is inconsistent with many pioneer researchers' expectations four years ago, in which NAS is expected to be another revolutionary technique similar to 2012's deep learning. Currently, there are many NAS papers published every year. But their effectivenesses are unclear. Differently, this paper comprehensively analyzes the architecture-performance prediction, which provides a timely analysis of the current NAS's ineffectiveness. I think this paper can attract the community's attention, encouraging the community to pay attention to the architecture-performance prediction in NAS, especially when reviewing a NAS paper. Therefore, I recommend an acceptance for this paper.

(Positive) The claimed improvement over its ICLR/ICML submission version is clear and significant. The improved version deserves acceptance by NeurIPS. Specifically, the authors have added discussion on the relationship with Bayesian Optimization. The paper also adds a comparison with Semi-NAS and ImageNet results in MobileNet Search Space. The improvement is indeed significant.

(Positive) This paper should also inspire Gradient-based approaches and SPOS families because weight-sharing NAS can be regarded as using shared weights to perform architecture-performance prediction. I think this paper is a timely solution to the NAS community.

(Positive) This paper achieves state-of-the-art results on several benchmarks, especially Open Domain Search on ImageNet.

(Positive) Sufficient experiments have been conducted to prove the effectiveness of the proposed method.

(Positive) Proper principled analyses have been provided to show the validness of the proposed method.


limitations_and_societal_impact: 

Please refer to and respond to the "negative" items in the above main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a simple approach to predictor-based neural architecture search. It is motivated by the observation that in NAS, we are really just interested in precisely estimating the performance of well performing architectures while less accurate estimates are tolerable for low performing architectures (as long as the predictor facilitates to discriminate between the two). Therefore the paper proposes to learn a series of performance predictors that subsequently focus on better performing architectures, where each new predictor relies of the previous one, instead of learning a single predictor in one step.  
In each step, a new sample of predicted to be well performing architectures is drawn and evaluated. The experiments show that this leads to very efficient sampling of increasingly good architectures on several search spaces inclusing NasBench 101 and NasBench201, NatNet and MobileNet Search spaces from the literature such that well performing architectures can be found with few samples.

main_review: The idea proposed in this paper is very simple. Yet, it seems to be efficient on the considered search spaces. I would expect an additional discussion on the search spaces in this respect: What assumptions do we need to make on the search space? Under which conditions would well performing architectures be discarded early on? In my understanding, this approach should work on convex search spaces and it is likely  to discard narrow optima in non-convex ones. Is that correct?

Besides the simplicity and practical effectiveness of of the idea, further strengths of the paper are:

- The paper/idea is well motivated. 
- The mathematical formalization makes sense.
- The approach is evaluated for several predictors and datasets.
- An ablation study in the number of query samples is provided.
- An ablation study on the new hyperparameters M and N is provided.
- The evaluation on the NasBench101 and 201 search spaces is thorough.

Weaknesses and questions:

- The method introduces new hyperparameters that need ti be optimzed per search space.
- In the ablation study on the number of samples, the chosen #of predictors is a bit unusual (6, 11, 91 predictors, etc).
- What is the training time per predictor?
- The Improvement over BONAS with respect to Test acc. for a give query budget is very small on NasBench101 (Table.  3)
- It would be interesting to see the same experiment as in Table 3 for NasBench 201.
- All number in tables 1 - 5 are already given as average values over 25 runs. The standard deviation should be reported as well.
- In Figure 5, the comparison to BONAS would be very helpful. 


The paper is overall well written and well structured. Yet, there are several minor language errors that should be addressed, for example:
line 56: "denoted" should be "denote"
line 105: "just imprecisely solves that" please reword
line 105: "previous methods" - please specify which methods you refer to
line 147: "can be effectively for our framework" should be "can be effective"
line 202: "choose from operator of" please reword
line 226: ", In"
line 231: "its" should be "their"
These are minor issues since the understanding is not impaired, but they should be fixed.

Similarly, in Equation (3), please check the \setminus. This does not seem to be correct. I think is should be \subseteq






limitations_and_societal_impact: With respect to the limitations, it would be good to also discuss the assumptions implicitly made on the regularity of the search space (see above). Otherwise, limitations and broader impact are appropriately addressed.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Most Neural Architecture Search (NAS) techniques rely on being able to predict the performance of a network on a task without the cost of a full training run. This paper breaks down the methods of prediction into two categories: strong predictors and weak predictors. The authors note that this assumes that we want to evaluate all samples from the search space uniformly, even if we know certain subspaces are less interesting. Overall I think this is an interesting insight and in itself quite novel. 

They therefore propose a method that attempts to improve the sample efficiency of NAS by using a series of “weaker” predictors to identify interesting subspaces, and then sample from those subspaces.
main_review: Overall I think this paper has fallen foul of unfortunate timing, since it seems like a nice idea which has potentially become less relevant in the last year with the advent of zero-cost proxies. For me, at least a comparison to [1] or discussion of how the methods compare is essential for this paper to be accepted. 

Otherwise, the paper is well written and the narrative is easy to follow but I found it quite hard to glean the specific implementation details. The idea that we can use weak predictors to select subspaces is appealing, but the mechanics of actually what that predictor looks like, what it’s predicting, and how that fits into the framework was quite hard for me to figure out.

My understanding is as follows: the typical setup here is that we have an MLP (or many MLPs?) which is going to predict a performance value for each network. We iterate between: sampling the top-N scoring networks from our predictions, and fitting the predictor

I have a few questions:
1. Do we have to start by first predicting a value for all of the networks in the space? 
2. We sample the top-N scoring networks from the predictions and fit the predictor on them. Then we “evaluate” the architectures using the predictor. What does this mean? Haven’t you just trained the networks in order to fit the predictor? Doesn’t it make more sense to just use the accuracies of the trained networks directly?
3. On the next iteration, do we sample from the whole search space again or do we just sample from the top-N architectures we ranked last iteration?
4. If we have multiple predictors, are they sampling different parts of the space? Or are they both being trained on exactly the same data? 

The authors write out predictor-based NAS as a bi-level optimization problem (sampling + predictor fitting), which feels obvious at first but actually makes for quite a nice general framework: for example, we see that predictor-based NAS methods are really doing co-ordinate descent, which is something I had never really thought of before. As a consequence of viewing it this way, the idea of having weak predictors starts to make a lot more sense, which is really nice for the reader to follow along with.

## Positive points
- The use of figures is nice and illustrative, and makes the narrative of the paper clear and easy to read
- The results are good and don’t seem cherry picked — all of the baselines/architectures look very sensible (e.g. using 1000 forests, 1000 trees, 1000 hidden units). The comparison to random search is very welcome, and the authors include error bars over 50 runs which is good to see
- Using average rank + test regret as evaluation measures makes for a compelling case 

## Points to address
5. I think the authors should be a lot more upfront about what a strong/weak predictor is (i.e. within the first page we should have some idea of what is a strong vs a weak predictor)
6. I’m a little confused by the proof-of-concept experiment in section 2.2. What is the predictor being used? In figure 3(a) I can’t wrap my head around why the predicted accuracy of the global optimal point moves. Can the authors clarify this? 
7. I know that the papers were released at very similar times, but the paper feels incomplete without a reference/comparison to [1], which proposes a range of extremely cheap predictors. From the results in tables 1 and 3 it seems like this method will be stronger (and indeed it seems like it might be possible to use the two approaches in conjunction). Some discussion on this or a convincing comparison would go a long way to improving the paper.

**Originality** Addressing the expense of neural architecture search is not particularly "new" or "novel", but I do think the idea to break the problem down into subsampling tasks is nice and not something I have seen before.   Differentiation between this work and previous contributions is clear. Related work is mostly adequately cited, though the paper is missing comparisons to the various "zero-cost" estimators listed in [1]

**Quality:** The submission seems technically sound, with a nice logical flow to the experiments. I enjoyed reading the paper and seeing the figures/tables to support the claims being made in the paper. Each claim seems well-justified.

**Clarity:** The submissions is relatively clear but I did get a little confused by the details of the sampling/resampling process (see my above questions). I'm not 100% sure I could reproduce the method from its current description.

**Significance:** The importance of the results may be slightly diminished by the development of work on cheap estimators for neural architecture search (though I do also believe the authors could address this). Otherwise, the results are nice.

## Minor typographical notes: 
- Capitalization on subsection 2.2 is strange (why is A capitalized?) 
- Figure 3 (a) accuracy is misspelt 
- “Why such “oversimplified BO" can be effectively for our framework?“ -> Why can such “oversimplified” BO be effective for our framework?

[1] Mohamed S Abdelfattah, Abhinav Mehrotra, Łukasz Dudziak, and Nicholas Donald Lane. Zero-cost proxies for lightweight nas. In Proceedings of the International Conference on Learning Representations (ICLR), 2021. 
limitations_and_societal_impact: The authors have adequately potential negative societal impact. Please see the main review above for my questions.
review_title: null

Meta-review: This paper introduces a query-based NAS method that is a simplified version of Bayesian optimization and is also very similar to BRP-NAS. Novelty is therefore low. On the upside, surprisingly, the method performs very well compared to many baselines that were requested during the rebuttal period. After the initial set of reviews, the paper had borderline scores, and the internal reviewer discussion was not moving further. I therefore recruited an emergency reviewer, who first gave a rejecting score (citing lack of novelty, and not expecting major performance improvements over the many similar previous methods). However, the authors provided strong results. If the code is made available for fully reproducing the work I am in favour of accepting the paper as this would allow studying *why* the proposed method performs better than Bayesian optimization etc, and since it would also provide a solid available baselines for future advances.
Specifically, I asked the authors to make available the following:
- Code for their NAS method, including hyperparameters and information on how the hyperparameters were tuned.
- Code for their training pipelines (i.e., including the supernet) and final evaluation pipelines for the open domain search benchmarks.
- Code/scripts used to run all baseline methods
- Code/scripts for reproducing all tables and figures
- Final architectures found by the methods
- Anything else they can think of that a reviewer/reader would need to reproduce your results.

Decision: Accept (Poster)