Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: *UPDATE* I have read the other reviews, author's comments and the revised pdf. I maintain my weak accept rating, the paper is borderline but above the bar. The inclusion of experiments that Reviewer1 suggested definitely make the contributions stronger. I believe the paper will be substantially stronger with a careful study of where the empirical improvement is coming from. The theory (that the approximate gradient has an acute angle with the desired gradient) is potentially vulnerable -- this property is certainly desirable when stochastic-optimizing convex functions (with appropriate step sizes) but it's not trivial that it gives good behavior for optimizing non-convex functions like NAS. Without this careful study, it is not obvious that the proposed method doesn't suffer from it's own "gradient traps". That said, pointing out gradient approximation issues with differentiable NAS may be a valuable enough contribution.

The paper studies differentiable approaches to neural architecture search and convincingly points out that existing approximations to the gradient w.r.t. architecture parameters are problematic. A new approximation is proposed, and evaluated to show that degenerate architectures are not getting selected once search has converged (empirically) on standard image classification datasets.
The problem with existing approximations (e.g. first-order or second-order DARTS) is explained clearly. It is however unclear whether the proposed solution provides a complete solution, or if there are avenues for further improvement. The key question marks are: is the proposal a tractable approximation? is the empirical improvement indeed arising because of better gradients? Studying these two questions carefully via experiment will make the paper's contributions stronger.

Minor questions (related to writing/exposition):
How is Eqn2 different from Eq3? If they are the same, please remove the redundant equation (you already repeat it in the Introduction).
Why is Eqn7 a tractable approximation when H is very high-dimensional? I agree that it is more efficient that H^-1, but don't see how it can be tractable to compute in general.
Section 4.1.2: What is "auxiliary loss tower"?

Abstract: "obstacles it" (obstacles is an awkward verb, perhaps use "hinders it" instead)
Introduction: "was very few covered in previous works" is an awkward phrase. "has not been studied carefully in previous works"
Related work: "exhausted search" -> "exhaustive search"

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper offers through analysis on instability of NAS training that the system degenerates and reaches to trivial solutions, e.g., more skip-connect operators, as training goes longer. Motivated by this issue, this paper proposes an approach to stabilize NAS training.

Strength:
[1] Theoretical analysis
[2] The paper is well written
[3] This paper is trying to solve a very interesting and important problem

Weakness:
[1] Lack of ablation study. It would be better to show learning curve like Fig.1 to illustrate how the proposed approach helps to stabilize training and how about >500 epoch, any unstable?
[2]The proposed approach offers comparable results with SOTA (early stopping). I agree that it opens a direction of stable NAS training, but the contribution so far is limited. I expect to see quality gains due to improved training technology

review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: --- response after the author's rebuttal ---

Thank the authors to provide their response and let me clearly understand their contribution.

However, after considering those, I will not change my rating. The paper identifies the inaccurate gradient computation in the original DARTS and propose a new estimation and achieves constant improvement. While interesting, the experiments show this approach is just as good as some simple human tricks like early stopping. In their response, they also didn't intend to generalize their approach to other baselines, and it will significantly limit the impact of this work. 

Authors insist that involving human prior is not the primary goal of AutoML. This is a subjective opinion, and my subjective opinion is it is wrong. If you take a closer look at all search spaces currently used in the NAS field, human priors are why NAS works up to now. For example, to use a convolutional operation, people use Conv-Bn-ReLU instead let NAS also search the activation functions. To search a cell rather than entire network is also designed by a human. If applied correctly, it is not wrong to include human priors. 

As stated in guideline, we should apply a higher standard to a 10-page paper, and unfortunately, in my opinion, this paper does not meet such standard with the current version, and heavily revision will be necessary. I encourage the authors to shorten their paper by putting some of the derivations to the appendix and to better show their contribution. If not planning to generalize their method, show more ablation and toy example of gradient trap and how the approach solves that. 

--- original review---


Summary

The paper presents a novel way to refactor second-order gradient term in Differentiable Architecture Search (DARTS) into the inverse of Hessian matrix (H^{-1}) corresponding to the optimal weight w^*, by leveraging a mathematical based on a property that gradient of loss w.r.t. w^* is 0. It provides an estimate relying on H instead of H^{-1} and showing mathematically that the proposed estimate has an angle (w.r.t ground-truth gradient vector) < 90 degrees, while the original estimate in DARTS is not bounded. The paper claims phenomenon (namely, gradient trap in DARTS) is the reason why DARTS and its successors constantly converge into a poor architecture while the proposed amendment will not.
It shows the experiments in both original DARTS search space with changes in the search phase, as well as a larger space with fewer operations. 

The observation that DARTS converging to a fixed point is interesting and the motivation to find the reason and solution is well justified. The technical novelty to compute the actual and estimate term for second-order DARTS is okay, and the identified "gradient trap" seems reasonable. However, I have some doubts regarding both theoretical and empirical aspects of this paper. The evidences in the current version is not sufficient to support all the claims. Especially considering the 10-page length, I hope the author could clarify these concerns during the rebuttal period.

Major concerns

About the derivation

- Based on the derivation in Section 3.3, the proposed gradient amendment relies on Hessian Matrix regarding the optimum w^*(\alpha), while in reality, it is rarely satisfied. Will this brings another gradient trap? Could you comment on the theoretical bound between the proposed amendment and the original DARTS estimation? In addition, as stated in DARTS paper (Liu et al.) section 2.3, if w is already a local optimum, the \nabla L_train (w, \alpha) = 0, where this will also make g2 or g2' to 0.  However, to obtain a good estimate of the Hessian matrix, one will need to have a good estimate of w^*. Does this contradict the proposed approach? 

- Computation of the Hessian matrix is missing, and the motivation to use g2'. 
The proposed estimate depends on the Hessian matrix, however, it is not mentioned in the paper how to compute such matrix, especially "... is computationally intractable due to the large dimensionality of H, ... usually exceeds one million ..." as in Section 3.3. Also, authors proposed to use g2' on top of the Hessian matrix instead its inverse, could author add experiments to show the difference between g2 and g2'? 

I came across to a concurrent paper submission [1], the derivation of second-order gradient estimate is the same as yours, i.e., one could use negative Hessian to improve the DARTS (see Appendix A.2 in [1]). However, the numerical computation of this Hessian is hard is also mentioned in [1]. Could the author also comment on that?

- Why the paper introduces \nabla_{\alpha} w^*(\alpha) with regarding L_train while the equation 2,3 is about validation loss? In DARTS, both training and validation dataset is used in training for better generalization. 

About experiments

- Could the author provide an additional experiment, to show in reality, even for a toy example, this gradient trap make DARTS converge to an architecture full of skip-connection, i.e., showing the gradient estimate (i.e., g1+g2) w.r.t. \alpha, obtained by original DARTS, proposed approach, if possible, ground-truth estimate, after a certain epoch number (e.g. 50 or any number that DARTS start turning to skip-connection)? I think this will empirically reveals if the gradient trap is causing the DARTS problem and better demonstrate the paper's method effectiveness. 

- Additional experiments for a fair comparison with baseline DARTS.
Experiment settings for both S1 and S2 seem to make the comparison to DARTS unfair. As shown in some previous work [2], different search space has different characteristic and is usually non-trivial in NAS domain. In addition, [3,4] shows that, weight sharing NAS is usually sensitive to random initialization, and results across runs can be quite different. To have a fair comparison, the paper should include additional experiments, running original DARTS and proposed one on the search space, S1 and S2, **with the same hyper-parameter setting**, for 3 runs with different random initialization. If the new results are still statistically significant, it will be strong evidence that the proposed algorithm indeed improves original DARTS.

Minor comments.

- Would the author kindly clarify the following points I found confusing during the reading? 

1. Introduction third last paragraph: "Our final solution involves using the amended second term of [eq] brings \alpha meanwhile keeping the first term unchanged". What's does "brings \alpha?" means? 
2. Section 3.3 line 7, is "fundamentals in mathematics" referring math foundations?

3. Equation 2, 3 are repetitive for no good reason?

4. In table 1,2 Random search results for S2 are missing. Could the author also listed for better comparison?

5. The second line after equation (3), "estimating \nabla ... ^2" why is this a square while in equation (3) it's not?


- generalization comparison with DARTS+, XNAS, etc. 
Since the proposed gradient amendment is a general approach, adding this on top of other approaches seems natural. Could the author extend their method to other modified DARTS algorithms. It should obtain even better results with extra human-expertise after fixing the gradient trap. Adding this will further strengthen the paper.

- The writing is somehow informal and could be polished, e.g. "This is to say" in paragraph 1 of page 2, misuse of bold style, and some typos:
1. Introduction page 2, "In all experiments", 'I' should not be in bold. 
2. line after equation 5, "throughout the remainder of this paper" remainder -> remaining.


--- Reference ---
[1] Anonymous, UNDERSTANDING AND ROBUSTIFYING DIFFERENTIABLE ARCHITECTURE SEARCH, link: https://openreview.net/forum?id=H1gDNyrKDS.
[2] Radosavovic et al., On Network Design Spaces for Visual Recognition, ICCV'19.
[3] Li and Talwalker, Random Search and Reproducibility for Neural Architecture Search, UAI'19.
[4] Scuito et al., Evaluating the search phase of neural architecture search, arxiv'19.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: The paper proposed to amend the 2nd order formulation of DARTS for improved stability. The main idea is to leverage the stationarity condition at a local optimum w* (that the derivative of the training loss equals zero). This is an interesting method, though the technique itself is not new outside the sub-field of architecture search. For instance, the same trick has been used in [1] for gradient-based hyperparameter optimization. Note the continuous architecture \alpha is mathematically equivalent to a high-dimensional hyperparameter.

Some major concerns:
* The authors correctly pointed out that the original 2nd-order approximation in DARTS is insufficient to make an accurate gradient direction. On the other hand, the proposed approximation in equation (8) seems aggressive enough to lead to outrageous approximation error. Specifically, the only guarantee is that the gradients before and after approximation form a non-negative angle (that their inner product is non-negative), whereas the angle alone can be insufficient to ensure the quality of individual elements, especially for high-dimension vectors.
* According to the authors, an advantage of the proposed approach is that one does not have to rely on early-stopping rules which require human expertise and “violates the fundamental ideology of AutoML” (Section 3.2). However, I am not fully convinced that the proposed method has an edge on this in practice, given the additional hyperparameter \eta (one may argue that those handcrafted early stopping rules are robust enough, just like the empirical statement in the paper that \eta = 0.1 worked well across the experiments) and potential approximation errors due to the Hessian.
* I'm also a bit concerned about the similar empirical performance but longer search time when comparing with other DARTS variants in Table 1 (using search space S1).

Minor issue:

In the introduction, the authors argue “convergence in search often leads to bad performance in re-training”, saying that a high validation accuracy during search is not a good indicator for the final performance. On the other hand, the goal of the proposed method is exactly to maximize the former rather than the latter. I believe this reasoning needs to be revised.

Question:
* Since each architecture gradient step is of comparable to the cost of 2nd order DARTS (which took 4 GPU days with 4 search repeats), it is not immediately clear why the proposed Amended-DARTS took only 1.1 GPU days (Table 1 & 2). Can you explain where did the speedup come from?
* Is there a particular reason to fix the edges in S1 and make it smaller than the original DARTS space? The question is relevant here because ideally we want an apple-to-apple comparison of those methods in the same space.

[1] Pedregosa, Fabian. "Hyperparameter optimization with approximate gradient.", ICML 2016

==== post-rebuttal comments ====
I would like to thank the authors for addressing some of my questions in the rebuttal. I decide to keep my score unchanged (weak reject). The reasons are as follows:
(1) Trying to improve DARTS from the optimization perspective is certainly interesting. However, the proposed approximation technique is rather a heuristic and only addresses the issue at a superficial level.
(2) Evaluating the proposed algorithm in the original DARTS space (in addition to the restricted space in the current manuscript) will substantially strengthen the paper.
review_title: Official Blind Review #4

Meta-review: This paper studies Differentiable Neural Architecture Search, focusing on a problem identified with the approximated gradient with respect to architectural parameters, and proposing an improved gradient estimation procedure. The authors claim that this alleviates the tendency of DARTS to collapse on degenerate architectures consisting of e.g. all skip connections, presently dealt with via early stopping.

Reviewers generally liked the theoretical contribution, but found the evidence insufficient to support the claims. Requests for experiments by R1 with matched hyperparameters were granted (and several reviewers felt this strengthened the submission), though relegated to an appendix, but after a lengthy discussion reviewers still felt the evidence was insufficient.

R1 also contended that the authors were overly dogmatic regarding "AutoML" -- that the early stopping heuristic was undesirable because of the additional human knowledge involved. I appreciate the sentiment but find this argument unconvincing -- while it is true that a great deal of human knowledge is still necessary to make architecture search work, the aim is certainly to develop fool-proof automatic methods. 

As reviewers were still unsatisfied with the empirical investigation after revisions and found that the weight of the contribution was insufficient for a 10 page paper, I recommend rejection at this time, while encouraging the authors to take seriously the reviewers' requests for a systematic study of the source of the empirical gains in order to strengthen their paper for future submission.
Decision: Reject