Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Pros:
1.	This paper gives a proof of finite-time convergence, which is the first paper working on this. Besides, the paper gives corresponding analysis of ENAS and DARTS. This is a new perspective of NAS methods.
2.	This work uses EG method to update architecture parameter, which takes the advantage of EG method and is reasonable to be applied on NAS problem.
3.	The experiment results show the efficiency and effectiveness of the proposed method.

Cons:
1.	Using EG to update architecture parameters can only accelerate convergence, which has nothing to do with improving the NAS performance. It is still confusing that why single-level optimization can resolve rank disorder and poor performance. It is not clear that the slight improvement on the performance is due to your algorithm or accident.
2.	Efficiency is claimed as an important point in this paper. However, only the results in Table 2 shows GAEA shorten the time cost. In Table 1, it cannot be detected that your method is more efficient. Is that because updating architecture parameters does not cost too much time in these experiment? If so, the contribution may be less.
3.	In Figure 2, it is not easy to detect the performance difference between your method and the baseline. You should also explain the meaning of lines with deeper colors.
4.	It is better to add discussion or conclusion at the end of your paper, which can help readers to better understand your work.

Overall Review:
This paper gives a theory about the convergence time of NAS methods, which provides new perspectives on NAS problem. The paper find that EG method is appropriate on updating architecture parameters and this method can improve the efficiency of NAS problem. There are also some questions mentioned above in this paper. With some modifications, this paper could be an excellent paper.

review_title: This paper argues for using a single level objective on weight-sharing NAS, and proposes GAEA, which uses exponentiated gradient to update architecture parameters, to accelerate the convergence. The paper gives a proof to guarantee finite-time convergence. The experiment results show this method is efficient and can slightly improve the performance.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper introduces the geometry-aware framework that can be adapted to any existing weight-sharing NAS methods optimized over gradient descent. The authors focus on the aspect of optimizing the architecture parameters to overcome the criticism of weight-sharing methods. The author's method relies on the mirror descent supporting their methods with a theoretical guarantee for the fast convergence. The author also supports their methods on various datasets such as CIFAR-10, ImageNet, NAS-Bench-201 (Dong & Yang), and NAS-Bench-1Shot (Zela et al.).

The paper supports their ideas not only supported by theoretical background, but outperforming results consistently with extensive empirical experiments such as CIFAR-10, ImageNet, NAS-Bench-1Shot1, and NAS-Bench-201. Furthermore, the GAEA can easily be applied to existing NAS methods which I believe making this work more valuable. 

Strength
1. Their methods easily apply to existing NAS methods with gradient-based methods. 
2. Theoretically supported methods with convergence guarantee. 
3. Extensive empirical experiments on CIFAR-10, ImageNet, NAS-Bench-1Shot1, and NAS-Bench-201. Moreover, detailed experiment descriptions and fair setups that are critical in NAS comparison are provided.
4. Novel perspective of view (optimization perspective) to overcoming the weight-sharing methods' criticism of recent works. 
5. Reproducible code included along with the paper. 

Overall, I recommend clear acceptance. This paper will provide new insights/perspective to NAS algorithms which adopts weight-sharing methods. 

Reference
1. Dong & Yang. NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search (ICLR 2020)
2. Zela et al. NAS-Bench-1Shot1: Benchmarking and Dissecting One-Shot Neural Architecture Search (ICLR 2020)
review_title: Well written and SOTA methods.

final_score: rating: 7: Good paper, accept
review_content: ## Summary
The submission presents a modification to the DARTS family of efficient Neural Architecture Search algorithms. The authors claim their modification (i) leads to better empirical performance, and (ii) is theoretically well-motivated. DARTS is a Neural Architecture Search algorithm which aims to find the most accurate network architecture within a human-defined search space.

The original DARTS algorithm uses gradient descent to optimize both (i) a set of shared model weights $\mathbf{w}$ which are used to rank different candidate architectures within a search space and (ii) a vector $\theta \in \mathbf{R}^n$ which corresponds to a continuous (real-valued) relaxation the network architecture. At the end of the search, $\theta$ is converted into a discrete architecture within the search space; this architecture is the output of the search process. The authors' proposed variant of DARTS -- which they call GAEA (Geometry-Aware Gradient Algorithm) -- updates the architectural parameters $\theta$ using *exponentiated* gradient descent instead of standard gradient descent. (Details are provided in Equation (8) in Section 3.3 of their paper, but the modification seems straightforward to implement.) The authors claim this modification favors sparse values of $\theta$, and helps decrease the gap between discrete architectures and their continuous relaxations.

On the applied side: The authors evaluate efficient NAS algorithms with and without their modification on three different benchmark tasks. On two of the tasks, the performance of their modified algorithm seems quite close to that of a baseline without the modification. On the third task (NASBench-201), the improvements appear to be quite substantial in one case. In most (but not all) cases, the authors directly compare the results of architecture searches obtained with and without their proposed modification. This type of control experiment is important and very helpful for a NAS paper, since it makes it possible to directly quantify the helpfulness of the proposed changes.

On the theoretical side: I had trouble understanding the significance of the authors' theoretical results. In particular: the paper claims to prove stationary-point convergence bounds for a variant of their algorithm but doesn't explain what stationary-point convergence means or why it's important. I'm very much on the applied side of machine learning, so it's possible that someone with a stronger theory background would get more out of the theoretical results. However, I also think the theoretical results could be much better-explained than they currently are. (I read through Section 3, but have not tried to check the theoretical results carefully.)

*Pros:*
* Paper provides experiments on three different benchmark tasks, and reports results for multiple NAS algorithms (mostly based on DARTS).
* Strong empirical results for some of the NASBench-201 experiments.
* Paper appears to provide solid baselines for most experiments.
* Proposed approach is not overly complex, and seems straightforward to implement.

*Cons:*
* Novelty is limited, since the authors are proposing a relatively limited change to an existing family of Efficient NAS algorithms. (This would, however, be a non-issue if the proposed changes were effective enough.)
* Unclear presentation of theoretical results.
* Quality improvements seem quite limited on 2 of the 3 benchmark tasks. (Part of the problem might -- as the authors suggest -- be due to limited headroom.)
* For the benchmark task with the largest improvement -- NASBench-201 -- the authors only provide their own baseline for 1 of the 3 NAS algorithms they evaluate, and for this variant (GDAS), the improvements over the baseline are quite small. So it's not clear to me how much of the improvements for the other two algorithms can be attributed to GAEA and how much can be attributed to NAS setups that are better tuned than the ones from the original NASBench-201 paper.

## Notes on Experimental Evaluation
The abstract makes a strong claim about the quality improvements brought about by the authors' proposed modification, so I'll evaluate the paper relative to that claim: "we exceed the best published results for both CIFAR and ImageNet on both the DARTS search space and NAS-Bench-201; on the latter we achieve near-oracle-optimal performance on CIFAR-10 and CIFAR-100."

The submission evaluates their method on three tasks: (i) the search space from the DARTS paper, (ii) the NASBench-1shot1 benchmark task, and (iii) the NASBench-201 benchmark task. On the plus side: the authors appear to provide direct comparisons between DARTS-based NAS algorithms with and without their proposed GAEA modifications (although this requires some confirmation of details which are currently missing from the paper). On the minus side: the improvements of GAEA algorithms over their non-GAEA equivalents seem quite small in most cases. (The authors attribute this to limited headroom in the search spaces, which seems plausible to me.)

On the original DARTS search space, the authors' proposed GAEA PC-DARTS algorithm produces architectures with an average test error rate of 2.50%, compared with 2.57% for standard PC-DARTS. The authors do not provide numbers for their own reproduction of the original PC-DARTS results; the writing implies that the hyper-parameters and search space are comparable. Providing numbers for the authors' reproduction of PC-DARTS would strengthen these results. Assuming the current numbers are in fact comparable: the performance improvements appear to be extremely small, and are probably within the range of statistical error.

On the NASBench-1shot1 search space, the authors claim that their proposed GAEA PC-DARTS algorithm works slightly better than an unmodified PC-DARTS, although the improvements appear to be small. While this seems reasonable given the data they provided, I think the presentation of results can be improved; the results presented in Figure 2 are difficult for me to interpret because the plots are visually noisy and contain many overlapping lines of different colors.

NASBench-201 is the most interesting (and potentially most appealing) case. The authors provide accuracy numbers for both their reproduction of the existing GDAS algorithm and their proposed GAEA-GDAS variant, and performance of the two seems quite similar (e.g., 93.55% test accuracy on CIFAR-10 for GDAS-GAEA compared with 93.52% for GDAS). The gap is larger on CIFAR-100, but primarily because the authors' reproduction of GDAS has lower accuracy than the published GDAS numbers from the NASBench-201 paper. For other DARTS variants, the accuracy improvements are quite impressive (e.g., 94.10% accuracy for GAEA-DARTS-ERM), but the authors do not provide a non-GAEA baseline for this configuration. Furthermore, the accuracies that the original NASBench-201 paper provides for baselines such as ENAS and DARTS are extremely low, so I think that providing a careful reproduction of DARTS-ERM with properly tuned hyper-parameters would help make the results more convincing.

## Notes on Clarity
While the paper seems reasonably well-organized and well-proofread, I found parts of it difficult to understand. I had trouble understanding Section 3 (which presents the paper's main theoretical results) in particular. The section is notation and terminology-heavy, and would be easier to follow if it spent more time explaining relevant terms.

I found Table 1 difficult to interpret because different rows of the table contain the results of architecture searches performed using different search spaces and/or model training hyper-parameters. For example, ProxylessNAS uses a very different search space than PC-DARTS and GAEA PC-DARTS. While the authors note this particular example in the text under the table, the table would be much easier to interpret if it was organized to show which subsets of the results were comparable to each other (i.e., used the same model training hyper-parameters and search space).

I also had trouble understanding Figure 2, which contains 8-10 overlapping red/blue lines. I also had trouble understanding the relationship between the "PC-DARTS" and "Best from Zela et al." lines (since Zela et al. evaluate PC-DARTS in their paper). It would be helpful to clarify the distinction between the two.


## Additional Notes

I had trouble understand this sentence from the end of Section 2.2: "Furthermore, for methods that adapt architecture parameters during search, it [using a first-order method] makes clear that we need not worry about rank disorder as long as we can optimize and generalize"
Why don't first-order methods need to worry about rank disorder? This needs to be better explained.

In Equation (5), what does the $\bigodot$ symbol denote? My best guess is that it refers to an elementwise product, but it would be helpful to state the meaning more clearly.

In Section 3.2: It's not clear to me what the significance of Theorem 1 is in practice. What is the significance of having a small expected value for $\Delta$ or of being close to an approximate stationary point? What does it mean, and why is it desirable? This needs to be better-explained.

review_title: Paper Review

Meta-review: This is a solid paper providing the first theoretical convergence result for NAS and showing promising empirical results.
The authors' proposed GAEA method can be combined with different types of weight-sharing algorithms (DARTS, PC-DARTS, etc) and is likely to reduce the impact of the architecture discretization step due to finding sparser solutions.
I clearly recommend acceptance and would expect this to make a nice spotlight.
Decision: Accept (Spotlight)