Neural Architecture Search (NAS) has seen an explosion of research in the past few years. A variety of methods have been proposed to perform NAS, including reinforcement learning, Bayesian optimization with a Gaussian process model, evolutionary search, and gradient descent. In this work, we design a NAS algorithm that performs Bayesian optimization using a neural network model. We develop a path-based encoding scheme to featurize the neural architectures that are used to train the neural network model. This strategy is particularly effective for encoding architectures in cell-based search spaces. After training on just 200 random neural architectures, we are able to predict the validation accuracy of a new architecture to within one percent of its true accuracy on average, for popular search spaces. This may be of independent interest beyond Bayesian neural architecture search. We test our algorithm on the NASBench (Ying et al. 2019) and DARTS ) search spaces, and we show that our algorithm outperforms other NAS methods including evolutionary search, reinforcement learning, AlphaX , ASHA, DARTS, and TPE. Our algorithm is over 100x more efficient than random search, and 3.8x more efficient than the next-best algorithm on the NASBench dataset. As there have been problems with fair and reproducible experimental evauations in the field of NAS, we adhere to the recent NAS research checklist (Lindauer and Hutter 2019) to facilitate NAS research. In particular, our implementation has been made publicly available, including all details needed to fully reproduce our results.
The paper introduces a new encoding for cell structures to improve efficiency of neural architecture search methods.
As a second contribution the paper proposes Bayesian optimization with an ensemble of neural networks as probabilistic model for the objective function.
Both contributions combined show superior performance on the Nasbench101 benchmark as well as competitive performance on the DARTS search space.
While the paper identifies an important problem - encoding of architectures - I do not think the paper is ready for acceptance.
About the encodings:
First, using different encodings to enable better architecture search has been investigated by others before.
For example, Ying et al. also provided different encodings of the adjacency matrix for Nasbench101 besides the used binary encoding and it seems that different methods work well with different encodings.
Also in the work by Kandasamy et al. they presented an encoding for architecture, such that Bayesian optimization can be applied.
Second, the encoding described in the paper lacks some intuition.
 - How does enumerating all paths and encoding them as a binary vector convey more information than just using the adjacency matrix?
 - Lead isomorphic graphs, which for example occur in Nasbench101, to the same encoding?
 - It seems somewhat counter intuitive to use a large binary vector (more than 18000 dimensional vector for the DARTS space) as encoding for Bayesian optimization which is known to struggle with high dimensional input spaces.
About the Bayesian optimization strategy:
The proposed probabilistic model for Bayesian optimization seems straight forward and simple. Also here, previous work (Snoek et al, Springenberg et al., Perrone et al)  already proposed to use neural networks and ,in order to be more convincing, the paper should include a comparison to these methods.
Furthermore, the paper should clarify how the diversity in the neural network ensemble is enforced. Are the neural networks trained with different random initialization? How does it compare to the method proposed by Lakshminarayanan et al. which showed better performance for neural network ensembles based only on different random initialization?
Minor comments:
- In the Nasbench101 paper other Bayesian optimization strategies (e.g SMAC, BOHB, TPE) showed strong performance. The results would be more convincing if these methods are included in the comparison.
- Following the empirical protocol by Ying et al. the results would be easier to parse if the Figure 3  could report the log test regret on the y-axis. I am also missing a figure that shows the robustness of the method across independent runs.
- How are invalid architectures in the Nasbench101 (e.g architectures that violate the max edge constraint) treated in the experiments?
- I think the paper is missing the following references:
Simple and scalable predictive uncertainty estimation using deep ensembles
B Lakshminarayanan, A Pritzel, C Blundell
Advances in Neural Information Processing Systems, 6393-6395
Scalable hyperparameter transfer learning
V Perrone, R Jenatton, M Seeger, C Archambeau
Advances in Neural Information Processing Systems, 6845-6855
post rebuttal
------------------
I thank the authors for answering my questions regarding the path encoding and taking the time to improve the empirical evaluation of the paper. While I think that the paper has improved, I am afraid that the contributions of the paper are still not strong enough to reach the bar of acceptance because of the following reasons: 
- The path encoding is an interesting approach and seems to improve upon just using the adjacency matrix directly, it doesn't scale and, hence, it remain somewhat unclear how valuable it is in practice. 
- More importantly, I am not convinced that the proposed neural network model represents a sufficient contribution. After some discussion with the authors, they agree that existing BO methods based on neural networks could also be applied to this setting and even say that they may perform well with the path encoding. However, they are not include them in the comparison and only promise to add them for the final evaluation.  I am concerned that if it turns out that other methods perform as well or even better, it would dramatically lower the contribution of the paper.