Differentiable neural architecture search has been a popular methodology of exploring architectures for deep learning. Despite the great advantage of search efficiency, it often suffers weak stability, which hinders it from being applied to a large search space or being flexibly adjusted to different scenarios. This paper investigates DARTS, the currently most popular differentiable search algorithm, and points out an important factor of instability, which lies in its approximation on the gradients of architectural parameters. In the current status, the optimization algorithm can converge to another point which results in dramatic inaccuracy in the re-training process. Based on this analysis, we propose an amending term for computing architectural gradients by making use of a direct property of the optimality of network parameter optimization. Our approach mathematically guarantees that gradient estimation follows a roughly correct direction, which leads the search stage to converge on reasonable architectures. In practice, our algorithm is easily implemented and added to DARTS-based approaches efficiently. Experiments on CIFAR and ImageNet demonstrate that our approach enjoys accuracy gain and, more importantly, enables DARTS-based approaches to explore much larger search spaces that have not been studied before.
--- 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.