Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: I have not worked in the optimization filed and I am only gently followed the NAS field. I might under-valued the theoretical contribution.

This work provides  theoretical analysis for the NAS using weight sharing in two aspects: 
1) The authors give non-asymptotic stationary-point convergence guarantees (based on stochastic block mirror descent (SBMD) from Dang and Lan (2015)) for the empirical risk minimization (ERM) objective associated with weight-sharing. Based on this analysis, the authors proposed to use  exponentiated gradient to update architecture parameter, which enjoys faster convergence rate than the original results in Dang and Lan (2015). The author also provided an alternative to SBMD that uses alternating successive convex approximation (ASCA) which has similar convergence rate. 
2) The author provide generalization guarantees for this objective over structured hypothesis spaces associated with a finite set of architectures.

My biggest concern is the validity of the proposed exponentiated gradient update, at least empirically. We indeed observed slightly improvement in test error over DARTS on the CIFAR10 benchmark but how reproducible the results are? Can you compare at least on the other benchmark (PENN TREEBANK) used in Liu et al 2019? Also, comparing to first order DARTS, search cost is the same and this is hard to justify the better convergence rate for EDARTS. In addition, the results on feature map selection is not very encouraging as the gap to the successive halving is significant.

The author proposed ASCA, as an alternative method to SBMD. Why we need such alternative? What is the advantage of ASCA comparing to SBMD? When should I use ASCA and when SBMD? How do they empirically different? 

Then I feel some wording can be improved. For example, "while requiring computation training …”,  “…which may be of independent interest”.


review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This work proposes an algorithm for handling the weight-sharing neural architecture search problem. It also derives generalization bound for this problem.

The reviewer has several concerns:

1) the SBMD and ASCA algorithms are existing generic algorithms. The analysis in this work also looks very generic. There is a sense of disconnection with the considered training problems. The reviewer would like to see more discussions on how to connect the algorithms with specific NAS problems. For example, what is the beta parameter when training a NAS problem?

2) The convergence rate improvement brought by using mirror descent has been long known. It is not easy to see what is the contribution of this work.

3) The generalization part seems to be meaningful. But it may be much stronger if the NAS problem can also have a theoretical bound. It is less appealing to only discuss cases with strongly convex objectives.
review_title: Official Blind Review #1

Meta-review: Since there were only two official reviews submitted, I reviewed the paper to form a third viewpoint.  I agree with reviewer 2 on the following points, which support rejection of the paper:
1) Only CIFAR is evaluated without Penn Treebank;
2) The "faster convergence" is not empirically justified by better final accuracy with same amount of search cost; and
3) The advantage of the proposed ACSA over SBMD is not clearly demonstrated in the paper.

The scores of the two official reviews are insufficient for acceptance, and an additional review did not overturn this view.
Decision: Reject