This paper introduces NSGA-Net, an evolutionary approach for neural architecture search (NAS). NSGA-Net is designed with three goals in mind: (1) a NAS procedure for multiple, possibly conflicting, objectives, (2) efficient exploration and exploitation of the space of potential neural network architectures, and (3) output of a diverse set of network architectures spanning a trade-off frontier of the objectives in a single run. NSGA-Net is a population-based search algorithm that explores a space of potential neural network architectures in three steps, namely, a population initialization step that is based on prior-knowledge from hand-crafted architectures, an exploration step comprising crossover and mutation of architectures and finally an exploitation step that applies the entire history of evaluated neural architectures in the form of a Bayesian Network prior. Experimental results suggest that combining the objectives of minimizing both an error metric and computational complexity, as measured by FLOPS, allows NSGA-Net to find competitive neural architectures near the Pareto front of both objectives on two different tasks, object classification and object alignment. NSGA-Net obtains networks that achieve 3.72% (at 4.5 million FLOP) error on CIFAR-10 classification and 8.64% (at 26.6 million FLOP) error on the CMU-Car alignment task.
After rebuttal, I adapted the score. See below for original review.
--------------------------------------------
The authors implement a two-stage multi-objective optimization scheme to optimize neural network architectures with several conflicting goals.
I can not accept the paper in its current form.
In short, I have the following main criticisms:
1. use of crowding distance(CD) instead of hypervolume-contribution.
CD is not consistent with the HV estimator, especially CD might remove solutions that have a large HV-contribution and thus HV will not increase monotonically. The effect is even visible in Figure 8c) as in iteration 22, HV is decreasing as crowding distance removes a good offspring. In short: Crowding distance should not be used as long as the number of objectives does not prohibit computing the HV-contribution.
2. No good justification of BN. It is unclear to me why BN should be used instead of more iterations at stage 1. In 4.4 BN is only compared to the uniform initialization, but this comparison has no meaning given that we already have an optimized front that improved on the uniformly sampled distribution. To be honest, the samples shown from BN do not look very convincing as a lot of very poor architectures are created.
A proper comparison would be comparing the 2-step approach with only the first step and the same budget. Then we could compare samples from both distributions (either sampling from the front using mutation/crossover or sampling from BN). Also we would have a fair comparison of the obtained fronts and HV-values.
3. Ablation study cross-over
I am not convinced by the results presented. The paper says this is a "small scale" study but does not give the number of iterations/samples. It is clear that in the setup of the mutation operator cross-over might help, simply because it can change many more connections in a single iteration than mutation alone, which is limited to max 1 change. Allowing up to two mutations and no crossover could already proof to be better (orsmaller size of offspring population, see below)
Smaller concerns:
1. The results suggest that the uniform distribution might not be tuned well, as it only covers the "expensive" networks but not the "cheap" networks. A better initialization scheme that covers the x-axis better might already show vastly different results. As the Flop-objective is cheap to compute and does not require simulation, one could expect to tune this offline before initialization.
2. No handling of Noise.
During optimization, the chosen starting point and SGD algorithm will introduce noise into the process. Thus, the final test accuracy will be noisy. As an elitist dominance scheme is used, one might easily end up with an architecture that has a large variance when trained, i.e. when performing a final training pass on the full dataset, the performance might be very different. Moreover, the algorithm might stop convergence towards the true pareto front as it is held back by noisy "good" results. This should be discussed in the paper
3. A single-offspring approach might be better than sampling a full population (or offspring size in the order of parallel instances one can expend to run). 40 sounds excessive given that the sampling distribution is only improved through selection and given that the pareto front approximation appears to include less than 40 elements. This might also affect the results in the ablation study for cross-over: more iterations with reduced offspring size allows for more mutations of successful offspring.
4. Some unclear or wrong wordings:
page 4: "As a consequence[...] the best solution encountered [...] will always be present in the final population. " What do you consider "best" in a 2-objective problem? Do you mean: the best in each objective?
page 6, footnote1: this is not true. even without crossover the selection operator ties the solutions together, an offspring has to beat any point in the population, not necessarily its direct parent.
5. Figure 8a) does not include the state of the art result for CIFAR10, see for example 
http://rodrigob.github.io/are_we_there_yet/build/classification_datasets_results.html#43494641522d3130