Stabilizing DARTS with Amended Gradient Estimation on Architectural Parameters
Authors: Kaifeng Bi
Changping Hu
Lingxi Xie
Xin Chen
Longhui Wei
Qi Tian
Venue:  (2020)
Keywords: Neural Architecture Search
DARTS
Stability

Abstract: 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 obstacles 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.

Under review as a conference paper at ICLR 2020
STABILIZING DARTS WITH AMENDED GRADIENT Es- TIMATION ON ARCHITECTURAL PARAMETERS
Anonymous authors
Paper under double-blind review
ABSTRACT
Differentiable neural architecture search has been popular methodology of ex- ploring architectures for deep learning. Despite the great advantage of search efficiency, it often suffers weak stability, which hinders from being applied a large search space 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- re-training process. Based on this analysis, we propose an amending term for computing architectural gradients by making mality of network parameter optimization. Our approach mathematically guaran- tees 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 DARTS based approaches efficiently. Exper- iments 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.
of direct property of the opti-
INTRODUCTION
Neural architecture search (NAS) has been an important topic in the research area of automated machine learning (AutoML). The idea is replace the manual way of designing neural network architectures with an automatic algorithm, by which deep learning methods become more flexible in fitting complex data distributions, e.g., large-scale image datasets. Early efforts of NAS involved using heuristic search methods such as reinforcement learning (ooph & Le [017] Zoph et al., 2018) and evolutionary algorithms (Real et al.) 2017] Xie Yuille 2017) to sample networks from large search space, and optimizing each sampled network individually to evaluate its quality. Despite no- table successes obtained by this methodology, it often requires a vast amount of computation, which obstacles its applications in the scenarios of limited resources. Inspired by the idea of reusing and sharing parameters among trained networks, DARTS (Liu et al. (201bb) was designed as a 'one-shot' solution of NAS. The major difference from the aforementioned methods is differentiable formu- lation of architecture search and an end-to-end mechanism which optimizes model weights (such as convolution) and architectural weights simultaneously. Recently, improvements upon DARTS were made in various aspects (Chen et al.) 2019 Xu et al. 2019 Liang et al. 2019), making it reasonable tradeoff between search cost and performance.
Despite its broad applications, the current pipeline of DARTS (or, generally speaking, differentiable NAS approaches) suffers critical weakness known as instability. Researchers reported (Liang et al. 2019) that DARTS- algorithms can sometimes generate weird architectures that produce considerably worse accuracy than those generated in other individual runs, or even significantly worse than randomly generated architectures. There indeed exist tricks designed by human exper- tise (Chen et al. 2019 Nayman et al., 2019 Liang et al. 2019) to alleviate this issue, but we point out that these approaches violated the idcology of NAS, which is to maximally prevent human interventions. Moreover, even with such add-ons, a dramatic property of DARTS persists and has not been studied carefully in prior work. When DARTS, well as its variants, gets trained for longer time, e.g., from the default number of 50 epochs to 200 epochs, we surprisingly observe that all these approaches converge very similar architectures, in which almost all edges are occupied

---

Under review as a conference paper at ICLR 2020
by skip-connect (a.k.a,, identity). These architectures, with fewer trainable parameters, are often far from producing high accuracy in particular on large datasets like ImageNet, but they somehow produce sufficiently high validation accuracy in the search stage. In other words, convergence in search often leads to bad performance in re-training. This is why some previous DARTS-based approaches advocated for early termination (Liang al.) 2019), practical but non-essential solu- tion. Also, we conjecture that early termination also contributes to the lack of stability and, more importantly, trustfulness, of DARTS-bbacd approaches.
This paper delves deep into the inconsistency between convergence and performance. We show that the devil lies in optimizing the loss function of the super-network, (wal (a). , Q) (w and a denote network and architectural parameters, respectively, and (a(a) is the global optimum of w given a), in which w and a get updated alternately. Following the chain rule, Vafral (wo (w*((ww))))) (a), ; a)) equals to Valval ax) (a)))a)))a== + Vaw"(a) a= (we ax) ( in which the first term is easy to compute while the second term is not, mainly because w" (ax is difficult to estimate, and so is the term of Vaw*(a))a==s
DART'S approaches performed inaccurate approximation for this purpose, in which the first-order version of DARTS directly dis- carded the second term but this term is often numerically significant, and the second-order ver- sion of DARTS applied an approximation to this term which is not mathematically guaranteed (see Section 3.4p. Consequently, the accuracy of VaLval (w> (a). laza cannot be guaranteed, and hence the update of a can be problematic. To the best of our knowledge, this issue is not studied by existing DARTS-based approaches.
To deal with this problem, we propose an alternative way of computing V Vaw"(a))a=s We make holds for any al, which directly comes from the optimality of (a)). Differentiating both sides with respect to at, we ob- tain a new equality which enables computing derives V Vaw" (a))a=(alaa (a))a=a, with the inverse of the Hesse matrix, V& Ctrain (w) w==+(()) This idea enables us to achieve more accurate approxi- mation on VaLrall"*()) ()) a=)a when (a(a) not available. Mathematically, we prove that when we have w x (as,) the inner angle between the second term and our approximate term is smaller than 90 degrees. Note that this property does not hold in existing DARTS- -bsed algo- rithms. Our final solution involves using the amended second term of Va (w" (ax) a))a= meanwhile keeping the first term unchanged, which goes one step further in optimizing the super- network, which reflects in a higher validation accuracy in the search stage.
use of an important property, i.e., Vu ax) (w= )
Our approach is very easily implemented. The overall computational overhead is comparable the second-order version of DARTS. Experiments are performed on image classification, with popular datasets including CIFAR and ImageNet being used. In all experiments, we allow the search stage to come to a complete convergence and report competitive accuracy among current state-of-the- arts. The stability of our approach also enables us close the gap between hyper-parameters of search and evaluation, as well as explore more complex search spaces, which are believed to be correct directions of NAS but existing DARTS-based approaches would mostly fail. Therefore, we helieve our algorithm can expand the application scenario of differentiable NAS methods in particular DARTS- hased approaches.
The remainder of this paper is organized as follows. We briefly review related work in Section 2 and illustrate our approach of amending architectural gradients in Section 3 After experiments are shown in Section 4 we conclude this work in Section 5
2 RELATED WORK
With the era of big data and powerful computational resources, deep learning (LeCun et al. 2015). in particular, deep neural networks (Krizhevsky et al., 2012). have rapidly grown up to be the standard tool for learning representations in complicated feature space. Recent years have witnessed the trend of using deeper (He et al. (016)) and denser (Huang et al. 2017) networks to boost recognition performance, while there is justification that whether these manually designed architectures are best for each specific task, e.g., image classification. To advance, researchers started considering the possibility of learning network architectures automatically from data, which led to the appearance
2

---

Under review as a conference paper at ICLR 2020
of neural architecture search (NAS) Zooh & Le 2017), which is now popular and known sub research field in automated machine learning (AutoML).
The common pipeline of NAS starts with pre-defined space of network operators. Since the search space is often large (e.g., containing 10 or even more possible architectures), it is unlikely that exhaustive search is tractable, and thus heuristic search methods
widely applied for speedup.
Typical examples include reinforcement learning (Zoph & Lej 2017: Zoph et al. 2018 Liu et al.) 80) and evolutionary algorithms (Real et al.) 2017: Xie & Yuille 2017 Real et al. 2019). These approaches followed a general pipeline that samples a set of architectures from a learnable distri- bution, evaluates them and learns from rewards by updating the distribution. an early age, each sampled architecture underwent an individual training process from scratch and thus the overall computational overhead is large, e.g. hundreds of even thousands of GPU-days. To alleviate the burden, researchers started to share computation among training sampled architectures, with the key lying in reusing network weights trained previously (Cai et al., 2018) or starting from well-trained super-network (Pham al. 2018). These efforts shed light on the so-called one-shot architecture search methods, which required training the super-network only once and thus ran more efficiently, e.g., two three orders of magnitude faster than conventional approaches.
Within the scope of one-shot architecture search, an elegant solution lies in jointly formulating architecture search and approximation, so that it is possible apply end-to-end optimization for training network and architectural parameters simultaneously. This methodology is known today differentiable NAS, and typical example is DARTS (Liu al.] 2019b), which constructed super-networt with all possible operators contained and decoupled, and the goal is to determine the weights of these architectural parameters, followed by pruning and re-training stages. This kind of approach allowed more flexible search space to be constructed, unlike conventional approaches with either reinforcement or evolutionary learning, which suffer from the computational burden and thus must constrain search within a relatively small search space (Tan & Le 2019).
Despite the inspirations brought by differentiable NAS, these approaches still suffer a few critical issues that narrow down their applications in practice. One significant drawback lies in the lack of stability, which reflects in the way that results of differentiable search can be impacted by very small perturbations, e.g., initialization of architectural weights, training hyper-parameters, and even randomness in the training process. Existing solutions include running search for several individual times and choosing the best one in validation (Liu et al., 2019b), or using other kinds of techniques such as decoupling modules (Cai et al., 2019] Guo et al. 2019). adjusting search space during optimization (Noy al., Chen et al. [2099] Nayman al. 2019), regularization (Xu al., 2019). early termination (Liang et al.] 2019). etc., however, these approaches seemed to develop heuristic remedies rather than analyze it from the mathematical fundamentals, egg., how instability happens in mathematics.
In this paper, we investigate the stability issue in mathematics and show that the results produced by the current approaches are much less reliable than people used to think. Then, we fix this issue by amending optimization of the architectural parameters, so that each step of the update gets closer to the correct direction. We show great improvement on stability in a fundamental task, image classification, while we believe our approach can be applied to a wide range of tasks including object detection (Gihissi et al.] (019)), semantic segmentation (L.iu et al., 2019a), hyper-parameter learning (Cubuk et al. 2019), etc.
3 STABILIZING DARTS WITH AMENDED GRADIENTS
In this section, we first show that DARTS can fail dramatically when it gets trained till convergence, and then we mathematically analyze how this problem is related to inaccurate approximation in optimization, following which we present our solution to amend this error and thus stabilize DARTS.
3.1 PRELIMINARIES: DIFFERENTIABLE NEURAL ARCHITECTURE SEARCH
Differentiable NAS approaches start with defining a neterr, which is constrained in a search space with pre-defined number of layers and limited set of neural operators. The core idea is to introduce a 'soft' way operator selection (i.e., using a weighted sum over the outputs of a few operators instead of taking the output of only one), that optimization can be done in end-to-
3

---

Under review as a conference paper at ICLR 2020
1.00
97.5
sci__coneec
None/skip Ratio
0.75
(K-1)
skip connect
97.0
Accuracy
seip copnect
0.50
Acc
96.5
skip copncce
0.25
None Ratio
sip_coneed
C.
0.00
skip Ratio
96.0
c_(k-2)
Skip connect
skip_ connect
100
200
con_coneett
Epoch
Figure 1: Left: a typical search process of the first-order DARTS, which 200 search epochs are used. Red, green and blue lines indicate the average weight of none, the ratio of dominant skip- connect operators (over 14 normal edges) and the re-training accuracy, with respect to the number of search epochs, respectively. Right: the normal cell obtained after 200 search epochs, in which all preserved operators are skip-connect. We executed both first-order and second-order DARTS for several times, and such failure consistently happens in each individual run.
end manner. Mathematically, the super-network function f(x; w ar), with x being input, and parameterized by network parameters w (e.g., convolutional kernels) and architectural parameters a (e.g.. indicating the importance of each operator between each pair of layers). f(x: w. a) is differentiable to both w and a. so that gradient-based approaches can be applied for optimization.
In the example of DARTS, f(x; w, a)) is composed of few cells, each of which contains N nodes, and there is a pre-defined set, E, denoting which pairs of nodes are connected. For each connected node pair (i. < j. node takes the output of node i, x,, as a part of its input, and propagate through a pre-defined operator set, O, with all outputs summed up:
exp(ao (1-5)
(ll (xx)
Σ OEO Eo'eo exp(a!..) (1))) o(x;).
Here, a softmax term is computed by architectural weights to normalize outputs. Within each unit of the search process, and a get optimized alternately. After search, the operator with the maximal value of ao (fJ) is preserved for each edge (i, 1). All network parameters w are discarded and the obtained architecture is re-trained from scratch
3.2 DARTS FAILS: THE CONTRADICTORY BETWEEN CONVERGENCE AND PERFORMANCE
Our research is motivated by an observation that DARTS, the end of regular training process with, say, 50 epochs (Liu et al. 22199)), has not yet arrived at or even got close to convergence, yet the weight of the none (a.k.a., zero) operator is consistenlly the largest on each edge of the normal cell. To verify this, we increase the length of each training stage by 4 times, i.e., from 50 to 200 epochs. Two weird phenomena are observed, both of which are shown in the left part of Figure First, the weight of the none operator monotonically goes up at 200 epochs, the weight has achieved 0.97 on each edge of the normal cells, however, this operator not considered in the final architecture. Second, almost all preserved operators are skip-connect (a.k.a,, identity), parameter-free operator that contributes little to feature learning and surprisingly, it occupies 30% to 70% of the weight remained by none. Such network has much fewer parameters than well-designed one, and thus it usually reports unsatisfying performance at the re-training stage. This indicates that, in the context of DARTS, there exists contradictory between search convergence and re-training accuracy.
We point out that this is a critical issue, which suggests that when using DARTS- based approaches, one does not hope the search process achieve convergence as it implies bad performance. In other words, each 'successful' architecture comes from an carly-terminated search process. Consequently, the initialization of parameters (or and w), the parer--aramettrs of search (e.g., learning rate) and the time of terminating search become important and thus need to be determined by experience (Liang al. 2019). This weakens the stability as well as explainability of search and, more importantly,
For simplicity, we ignore lot of technical details, which we simply follow the original implementation.
4

---

Under review as a conference paper at ICLR 2020
violates the fundamental ideology of AutoML, i.e., maximally reducing human interference and determining the best architecture by training data.
3.3 DELVING DEEP INTO MATIEMATTCCS: PROBLEM AND SOLUTION
We point out that the reason lies in inaccurate estimation of the gradient with respect to a, namely,
V Va (w= (ax), a=)a Following the chain rule of gradients, this quantity equals to
(a a) (aww(a)) Vaw" Taw"(a)a==a, VwLvalww, a (a)
(2)
in which the first term is relatively easy to compute (as is done by the first-order version of DARTS), while the second term, in particular Vaw (a)="(a)a==aa)) is not. The first-order version of DARTS directly discarded this term, but it often has significant numerical values which are not negligible. The second-order version of DARTS indeed proposed an approximation to this term, but, as we shall see in the next subsection, can incur large approximation error (the inner- inner-product between the correct and estimated directions can be smaller than 0). Consequently, there can be a significant gap between the estimated and true values of V Vo (w= aa) a= Such inaccuracy accumulates with every update on a, and gradually causes a to converge to weird solutions that are far from optimum, e-g., the entire super-network is dominated by none and skip-connect operators. We name this phenomenon as the gradient trap during optimization.
To estimate V,w" (a))a=a, (a))(a)) values. Then, we make use of important property, i..,, Vu (w, ar) [==
we first make reasonable assumption that Vaw" (a))aaa) has finite
holds for any at, This is property directly comes from the optimality of w" (a), but it has never been used by existing approaches. Applying differentiation with respect to any a both sides of this equality, we have Val Vw (w, a w=w
O. When a aze it becomes:
Val
(uuftrain (w, a aw)_=waa')
)
a===a = =0.
(3)
Again, applying the chain rule the left-hand side gives:
? V2 firain a:) waw"(a)) + Vaw" Vaw"(a)lazas V2 Pirarai (w, a)) (aww))))) (4)
where we use the notation ()) V (+)(+) throughout the remaining part of this paper. Here, Crriii at)
a wax) aa==a, H is the Hesse matrix corresponding to the optimum w (ar), which is symmetric and positive-definite, and thus invertible. This gives us estimation that Vaw" (a))aaa)aaa V2 Va. Ctrain (w, a:) (=w -H- Substituting it into Equation
gives:
VaLualw" aa))aaa = VaLral ))ه w=w
22 Cirain (w, ar) u= HH. VuLma ai) w=
(5)
Note that Equation 5 does not involve any approximation. The only issue comes from the term of H-1 which is computationally intractable due to the large dimensionality of H (it is related to the number of network parameters, which often exceeds one million in typical super-network).
3.4 APPROXIMATIONS COMPUTING THE INVERSE HESSE MATRIX
Let us denote Equation 5 in an abbreviated form of g = g1 + g2, in which gı, the first-order term of DARTS, is easily computed, while g2 is due to the computation of H Here, we propose an alternative solution which constructs an approximation term g2:
g
v2 Curain (w, x (==w)a)) .H (v a) (aw"(av)
(6)
where 7 > 0 is named the amending coefficient. In what follows, we show that g is indeed a reasonable approximation of g2. Since
(g (2) n7. Ver a))
H V Ctrainn (w, a) w-w(aaamma
V2 Crraiii a) w=w'(a))
H. V Lva a a)lw=ww()))
5

---

Under review as a conference paper at ICLR 2020
the product of the two terms between H and H is a sami-positive-defiite matrix, and so is the matrix after similarity transformation, which directly gives (g2, g2) > O.
In summary, we decompose the gradient of architectural parameters into two terms, gi and g2, compute g1 directly and use an approximation to 82 so that the angle between the accurate and approximated terms is smaller than 90 degrees. In comparison, existing DARTS-based ap- proaches either discarded g2 entirely or used a mathematically non-explainable approximation g -1 V Ctrain (w, ax) (== II- Vu (w, (0)
None of them are reasonable because g2 can be large, yet there is no guarantee that (g2 g2) > 0, iee, the second- order DARTS can lead the algorithm to a wrong direction.
The rationality of our approach is also verified by the validation process, i..., in updating architec- tural parameters. The first-orler DARTS, by directly discarding g2, reported an average validation accuracy of 90.5% in search space S₁ (see Section 4.1.3) on the CIFARIO dataset. The second-order DARTS added gy. which has no guarantee that (g g2) > 0, and thus resulted in a reduced val- idation accuracy. Our approach, by adding 82. achieves validation accuracy of 91.5%, implying that our optimization works better than DARTS. This eventually results in the advantage of searched architectures, which will be verified in Section 4.1.2
The remainder part of computing &2 simply follows conventions, which we replace w" with the current west the most accurate approximation we can ge Computing 82 with Equation 6 requires both Ttrainn (w, ax) w==+(a)).==a, and Wafral (W,, xx) [a==)))))) while DARTS
needs the former one with w (oxz) estimated in two steps. Therefore, computing Equation requires
similar computational overhead compared to the second-order version of DARTS. In experiments,
each search epoch requires around 0.02 GPU-days on the standard 8-cell space on CIFARIO.
3.5 DISCUSSIONS AND RELATIONSHIP TO PRIOR WORK
The core benefit brought by our approach is the consistency between search and evaluation. This is indeed fundamental idea of NAS, but it was ignored by existing approaches since they have been perplexed by a more significant error caused by inaccurate optimization. After the error, we point out few prior conventions that need to be adjusted accordingly, including using different depths (e.g.. DARTS used 8 cells in search and 20 cells in evaluation) and widths (e.g., DARTS used a basic channel number of 16 in search and 36 in evaluation) during search and evaluation, as well as using different training strategies (e.g., during re-training, a few regularization techniques including Cutout (Devsses & Taylor 2017), Dropout (Srivastava al.) (014)) and auxiliary loss were used, but none of them appeared in search). More importantly, the search process was followed by edge removal (8 out of 14 connections were preserved) which caused significant difference between the network architectures of search and evaluation. Our approach provides the opportunity to bridge the gap between search and evaluation, which we will show in Section 4.1.2 that unifying these hyper-parameters leads to better performance.
A few prior differentiable search approaches noticed the issue instability, but they chose to solve it in different manners. For example. P- P-DARTS (Chen et al., (019) fixed the number of preserved skip-comnect operators, PC-DARTS (Xu et al. 2019) used edge normalization to climinate the none operator, while XNAS (Nayman et al. 2019) and DARTS+ (Liang al. 2019) introduced few human expertise to stabilize search. However, we point out that (i) either P- P-DARTS or PC-DARTS, with carefully designed methods or tricks, can also fail in sufficiently long search process (more than 200 epochs); and that (ii) XNAS and DARTS+, by adding human expertise, somewhat violated the design nature of AutoML, in which one is expected to avoid introducing too many hand-designed rules.
Another line of NAS, besides differentiable methods, is to use either reinforcement learning or an evolutionary algorithm as a controller of heuristic search and train each sampled network to get some kind of rewards, egg., validation accuracy. In the viewpoint of optimization, this pipeline mainly differs from the differentiable one in that optimizing a is decoupled from optimizing w, so
This raises another benefit of using gá to approximate g2. Note that ga (Equation 5) requires computing H while gá (Equation 6) only requires H. The existence of H is only guaranteed at = wa)). and thus the estimation can he quite inaccurate even if wst gets sufficiently close to w (a)). Therefore, using H itself is more friendly in this scenario.

---

Under review as a conference paper at ICLR 2020
that it does not require arrive at w", but only need reasonable approximation of w" to predict model performance this is an important reason that such algorithms often produce stable results. Our approach sheds light introducing a similar property, Le., robustness approximated w', which helps in stabilizing differentiable search approaches.
EXPERIMENTS
4.1 RESULTS ON CIFARIO
The CIFARIO dataset (Krizhevsky & Hinton, 2009) has 50,000 training and 10,000 testing images, sized 32 32, and equally distributed over 10 classes. We mainly use this dataset evaluate the stability of our approach, as well as analyze the impacts of different search options and parameters.
4.1.1 IMPACT OF THE AMENDING COEFFICIENT
We first investigate how the amending coefficient, 7) defined in Equation 6 impacts architecture search. We search and re-train similarly DARTS. During the search, all operators are assigned equal weights on each edge. We use a base channel number of 16, and batch size of 96. An Adam optimizer used to update architectural parameters, with learning rate of 0.0003, a weight decay of 0.001 and momentum of (0.5, 0.999). The number of epochs is to be discussed later. During re-training, the base channel number is increased to 36. An SGD optimizer is used with an initial learning rate of 0.025, decaying following the cosine annealing rule and arriving at 0 after 600 epochs. The weight decay set to be 0.0003, and the momentum 0.9.
To arrive at convergence, from to 1, and the architectures corresponding to 7) 0 (equivalent to DARTS), 7j = 0.1 and are summarized in Figure 2 We can see that 0.1 converges, after 500, into a reasonable architecture that achieves an eтror rate of 3.08% on CIFAR10. We emphasize that, even with more search epochs, this architecture is not likely change, the preserved operator each edge has weight not smaller than 0.5, and most of these weights are still growing gradually.
run the search stage for 500 epochs. We evaluate different values
When 17 is very small, e-g., 1) 0.001 or 1) 0.01, the change brought by this amending term to architecture search ignorable, and our approach shows almost the same behavior as the first-order version of DARTS, i.e., 17 the search process eventually runs into an architecture with all skip-connect operators, the number of epochs needed for a complete failure is significantly postponed, which verifies that the amending term indeed pulls architecture search away from the gradient trap.
In addition. when 1) grows up, e.g., from 0.001 0.01, although
(1:13
Mki oo val
0-22
That pood
mes pood 3s3
ang poet 3cl
Miu Meeeaa sol
ingLsoo
Mi nol
mesn_pool_b
din mo
0-11
eeg peod
wkat coumedd
POLARCE 30
mg poot h21
00
200 p00 26, 20..29000
sib connec
CD
<og mineet
Figure 2: Normal (left) and reduction (right) cells (the standard DARTS space) obtained by different amending coefficients, namely, 7 = 0 (top), 7 0.1 (middle) and n) (bottom).
7

---

Under review as a conference paper at ICLR 2020
On the other hand, if we use sufficiently large y value, e.g., 1) 1, the amending term, g2. can dominate optimization, so that the first term, i.e., the gradient of architectural parameters, has lim- ited effects in updating therefore, in the scenarios of a large the network significantly prefers avg-pooling to other opera- tors, as avg-pooling can smooth feature maps and avoid over-fitring. However, avg-pooling is also parameter-free operator, so the performance of such architectures is also below satisfaction.
Note that the amending term is closely related to network regularization,
Following these analyses, we simply use 1/ 0.1 for all later experiments. We do not tune 1) very carefully, though it is possible to determine automatically using a held-out validation set. Besides, we find that the best architecture barely changes after 100 search epochs, which we fix the total length to be 100 epochs in all remaining experiments.
4.1.2 CONSISTENCY BETWEEN SEARCH AND EVALUATION
As discussed in Section 3.5 it is important to alleviate the difference between search and evaluation. We make the following modifications, listed from most to least important. First, to avoid edge removal, we fix the edges in each cell, that each node is connected to node i and the least indexed node (denoted by Cs-2 in most conventions), resulting in 8 edges in each cell. Note that our approach also works well with all 14 edges preserved, but we have used 8 edges to be computationally fair to DARTS. Second, we unify the width (the number of basic channels) as 36 for both search and evaluation. Third, we add normalization techniques, including Cutout (De & "Taylor 2017), Dropout (Srivastava et al. 2014) and an auxiliary loss tower, into the search stage.
We use the amending coefficient 7) = 0.1 learned from previous experiments, i.e., without modifica- tion. the searched architecture, denoted by Aorig. is shown in the middle column of Figure After modification, the obtained architecture, denoted by Anew, is shown in Figure 3 We re-train both networks on CIFARI0 10, with or without the option that stacking duplicate cells to make the network deeper (with 20 cells). With a standard re-training process, Aorig reports a 3.67% error with 8 cells, and a 3.08% error with 20 cells; and the corresponding numbers are 3. 3.20% and 2.81% for Anew- We find that Anew is consistently better than Aorig. which suggests that alleviating the gap indeed helps. This also reminds us of the significant depth gap (Chen al. 2019) between search and re-training (the network has 8 cells in search, but 20 cells in re-training), and this gap also obstructs our approach from achieving better performance. We will investigate this issue in the following part.
4.1.3 EXPLORING MORE COMPLEX SEARCH SPACES
We note tremendous efforts made by existing approaches to alleviate the depth gap, while our so- lution is a direct one, thanks to the stability of our approach which enables us to directly explore larger search spaces. Here, we denote the original search space used in DARTS as SJ, which has six normal cells and two reduction cells, and all normal cells share the same set of architectural param- eters and so do the reduction cells. Note that we have fixed the edges in this space, resulting in the total number of possible architectures reduce from 1.1 10 to 3.3 x 10 We also explore more complex search space, denoted by S2, in which we relax the constraint that either normal cells or reduction cells should be the same, and also the number of cells increases from 8 to 20, to be applied in re-training. Here, limited by GPU memory, we cannot support all seven operators to be searched, so we only choose two, namely skip-connect and sep-conv-3x3, which have very different properties. This setting allows a total of 1.5 x 10 architectures to appear, much larger than S..
Results are listed in Table I In S1, our approach achieves a moderate error rate of 2.81 %, mainly because the assumption of consistency between search and re-training does not hold. In Sy, with directly searching in deep architectures, our result is significantly boosted (an error rate of 2.60%, the architecture is shown in the middle row of Figure 3). Again, we emphasize that we report re- training results based on an converged architecture, which stands out from existing DARTS- based approaches which required early termination.
In Sz, we compare our approach against both DARTS (no amending term) and random search. We observe that DARTS produces weird architectures (the bottom row of Figure 3. that high-layer cells are mostly occupied by skip-counect, which is not likely to fully utilize the ability of the super- network. Regarding random search, we follow DARTS by randomly sampling 20 valid architectures from each of S, and S2. and using a small validation dataset to choose the best two architectures for re-training. Given fixed number of probes, it becomes more and more difficult to sufficiently
8

---

Under review as a conference paper at ICLR 2020
SURRCOO
Figure 3: Top: normal and reduction cells found Sj. Middle & Bottom: the overall architecture found in S2 by DARTS, with and without the amended term, in which red and blue edges indicate skip-connect and sep-comv-3x3 operators, respectively.
explore a large space. The deficits of DARTS and random search on CIFARIO are 0.25% and 0.29%, respectively, which do not seem to be very large arguably because CIFARIO is relatively easy and our edge-fixed fixed search space guarantees sufficient depth. However, when we transfer these architectures to ImageNet, the deficits become much larger, i.e. with 1.7% and 0.8% top-1 accuracy drops, respectively (DARTS produces inferior performance to random search). These results remind us prior work (Xie et al. 2019) which claimed that random search works sufficiently well in large search spaces. Here, leave comment on this debate, demonstrating that large space indeed raises challenges to architecture search, but a stabilized search algorithm still has the ability to find more powerful architectures.
4.1.4 COMPARISON TO THE STATE-OF-THE-ARTS
Finally, we compare approach with recent approaches, in particular, differentiable Result are shown Table Our approach produces competitive results among state-of-the-arts, although it does not to beat others. We note that existing approaches often used additional tricks, e.g., P- DARTS assumed a fixed number of skip-connect operators, which shrinks the search space (so as to guarantee stability). More importantly, all these differentiable search approaches must terminated in an early stage, which makes them less convincing as search has not arrived at convergence. These
Test Err.
Params
Search Cost
Architecture
Search Method
(%)
(M)
(GPU-days)
DenseNet-BC: (Huang al. 2017]
3.46
25.6
manual
ENAS (Pham 2018) Cutout
2.89
4.6
0.5
RL
NASNeI-A Zoph al. 2018
w/ Cutout
2.65
3.3
1800
RL
NAONet WS (Liio et al.
2018
3.53
3.1
0.4
NAO
Hireachical Evolutron (Lu
2018b
3.
15.7
300
evolution
AmoebaNet-B B (Real et
w/ Culout
2.55=10.05
2.8
3150
evolution
PNAS Liu et 2018a
3.41-10.09
3.2
225
SMBO
DARTS (brst-odde)) (L.ud
2019b
Cutout
3.00+F0.14
0.4
gradient-hased
DARTS (second-order) (1 al. 2019h Cutout
2.76+-0.09
3.3
gradient-based
SNAS (moderate) (Xie al. 2018 Cutout
2.85::0.02
gradient-basee
ProxylessNAS (Cai et al. 2019 w/ Cutout
2.08
gradient- based
P-DARTS (Chen et al. 2019 w/ Cutout
gradient- based
BayesNAS (Zhou et al. 2019 w/ Cutout
2.81-10.04
gradient- based
PC-DARTS' (Xu al. 2019 w/ Cutout
2.57+0.07
gradient-ber
Amended- DARieE, Si, w/ Cutout
2.81=0.21
3.5
1.0
gradient- based
Amended- DARTS, S2, w/ Cutout
2.60=10.15
3.6
1.1
gradient based
Table 1: Comparison with state-of-the-ar network architectures CIFAR10.

---

Under review as a conference paper at ICLR 2020
Architecture
Test Err. (%)
Params
X+
Search Cost
Search Method
top-1
top-5
(M)
(M)
(GPU-days)
Inception-vl (Szegedy ct al.
2015
30.2
10.1
6.6
1448
manual
MobileNet Howard et at. 2017)
29.4
10.5
4.2
569
manual
ShuffleNet 2x (V1) (Zhang
2018
26.4
10.2
~
524
manual
ShuffleNet 2x (v2) (Ma
2018)
25.1
~
591
manual
NASNet-A 77oph et al. 2018
26.0
8.4
5.3
564
1800
RT.
MnasNNct-22 Lun ul. 2019
25.2
8.0
4.4
388
RL
PNAS (Liu et al. 20188
25.8
8.1
5.1
588
225
SMBO
AmoebuNet-C (Real al.
2019
24.3
7.6
6.4
570
3150
evolution
DARTS (sccond-nrder)
(L.u
2019b
26.7
8.7
4.7
574
4.0
gradient-
SNAS (mild) (Xe et al.
2018
27.3
9.2
4.3
522
1.5
gradient-based
BayesNAS Zhou
2019
26.5
8.9
3.9
0.2
gradient-busee
P-DARTS (CIFAKIU)
hen ct al.
2019
24.4
7.4
4.9
557
0.3
gradient-busee
ProxylessNAS (GPU)*
(Cai
2019
24.9
7.5
7.1
465
8.3
gradient-bused
PC-DARTS (Xu et al.
2019
24.2
7.3
5.3
597
gradient-har
DARTS+ (Liang et al.
2019
23.9
7.4
5.1
582
6.8
gradicnt- -basentt--acdddd
Aimended-DARIS. S2
24.3
7.4
5.5
590
1.1
gradient- gradient-based
Table Comparison with state-of-the-art architectures on ILSVRC2012. All searched architectures are fit into the mobile setting. indicates architectures searched on ImageNet.
tricks somewhat violate the ideology of neural architecture search; in comparison, our research, though not producing the best performance, seems going along a correct and promising direction.
4.2 RESULTS ON ILSVRC2012
ILSVRC2012 (Russakovsky et al., 2015) is the most commonly used subset of ImageNet (Deng) ct al. 2009). It contains 1.3M training images and 50K testing images, which are almost evenly distributed over all 1,000 categories. We directly use the Sn architecture obtained from CIFARIO experiments and enlarge with a basic number of channels of 42, so that the FLOPs of our model is 590M, i.e., fitting the mobile setting. During re-training, there SGD optimizer with an initial learning rate of 0.5 (decaying linearly after each epoch), a momentum of 0.9 and weight decay of 3 10-5 On NVIDIA Tesla V100 GPUs, the entire re-training process takes around 24 GPU-days.
total of 250 epochs. We
The comparison of approach existing approaches is shown in Table Our approach achieves a top-1 error rate of 24.3% without any common optimization tricks such as Auto.Augment (Cubuk al. 2019) and Squeeze-and-Exciteee Excitation modules (Hu al. 2018). This result is competitive among state-of-the-arts, and it is obtained after convergence is achieved in the search stage. On the other hand, without the amending term, DARTS converges to solution that skip-connected and sep-conv- 3x3 are largely separated, on which the re-training performance is even inferior to random search.
5 CONCLUSIONS
In this paper, we present an effective approach for stabilizing differentiable neural architecture search. Our motivation comes from that DARTS-based approaches mostly generate all-skip-connect architectures when they are executed for a sufficient number of epochs. We analyze this weird phe- nomenon mathematically and find the reason lie in the dramatic inaccuracy estimating gradients of architectural parameters. With an alternative approximation based on the optimality of network parameters, we guarantee the update of architectural parameters to be in a correct direction. In DARTS-based search spaces CIFARI0 and ImageNet, our approach shows improved stability, in particular in large search spaces, as well as improved performance in the re-training stage.
Our research sheds light on future research NAS in several aspects. First, we reveal that previous differentiable approaches were mostly built upon a dangerous pipeline, and mostly introduced heavy human expertise avoid failure. By fixing the 'system error' of this pipeline, we provide platform that NAS approaches can compete in the ability of NAS. Second, our approach enables researchers explore even bigger search spaces that have not been studied before (due search instability).
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
H. Cai, T. Chen, W. Zhang, Y. Yu, and J. Wang. Efficient architecture search by network transfor- mation. In AAAI Conference on Artificial Intelligence, 2018.
H. Cai, L. Zhu, and S. Han. Proxylessnas: Direct neural architecture search on target task and hardware. 2019.
X. Chen, L. Xie, J. Wu, and Q. Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In International Conference on Computer Vision, 2019.
E. D. Cubuk, B. Zoph, D. Mane, V. Vasudevan, and Q. V. Le. Autoaugment: Learning augmentation policies from data. In Computer Vision and Pattrn Recognition, 2019.
J. Deng, W. Dong, R. Socher, L. J. Li, K. Li, and L. Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, 2009.
T. Veieies and G. W. Taylor. Improved regularization of convolutional neural networks with cutout. arXiv preprint 1708. 04552, 2017.
G. Ghiasi, T. Y. Lin, and Q. V. Le. Nas-fpn: Learning scalable feature pyramid architecture for object detection. In Computer Vision and Pattern Recognition, 2019.
Z. Guo, X. Zhang, H. Mu, W. Heng, Z. Liu, Y. Wei, and J. Sun. Single path one-shot neural architecture search with uniform sampling. arXiv preprint arXiv: 190.:0040040040 2019.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Computer Vision and Puttern Recognition, 2016.
A. G. Howard, M. Zhu, B. Chen, D. Kalenichenko, W. Wang, T. Weyand, M. Andreetto, and
H. Adam. Mobilenets: Efficient convolutional neural networks for mobile vision applications. arXiv preprint arXiv: 1004:::7700446611 2017.
J. Hu, L. Shen, and G. Sun. Squeere-and-excitation networks. In Computer Vision and Pattern Recognition, 2018.
G. Huang, Z. Liu, L. Van Der Maaten, and K. Q. Weinberger. Densely connected convolutional networks. In Computer Vision and Pattern Recognition, 2017.
A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, 2012.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical report, 2009.
Y. LeCun, Y. Bengio, and G. E. Hinton. Deep learning. Nature, 521((553):436, 2015.
H. Liang, S. Zhang, J. Sun, X. He, W. Huang. K. Zhuang, and Z. Li. Darts+: Improved differentiable architecture search with early stopping. arXiv preprint /90v:0999.00033: 2019.
C. Liu, B. Zoph, M. Neumann, J. Shlens, W. Hua, L. J. Li, L. Fei-Fei, A. L. Yuille, J. Huang, and K. Murphy. Progressive neural architecture search. In European Conference Computer Vision, 2018a.
C. Liu, C. Chen, F. Schroff, H. Adam, W. Hua, A. L. Yuille, and L. Fei-Fei. Auto-deeplab: Hierarchical neural architecture search for semantic image segmentation. In Computer Vision and Pattern Recognition, 2019a. 9a.
H. Liu, K. Simonyan, O. Vinyals, C. Fernando, and K. Kavukcuoglu. Hierarchical representations for efficient architecture search. In International Conference on Learning Representations, 2018b.
H. Liu, K. Simonyan, and Y. Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations, 2019b.
R. Luo, Tian, T. Qin, E. Chen, and Y. Liu. Neural architecture optimization. In Advances in Neural Information Processing Systems, 2018.
11

---

Under review as a conference paper at ICLR 2020
N. Ma, X. Zhang, H. T. Zheng, and J. Sun. Shufflenet v2: Practical guidelines for efficient emn architecture design. In European Conference on Computer Vision, 2018.
N. Nayman, A. Noy, T. Ridnik, I. Friedman, R. Jin, and L. Zelnik-Manok Xnas: Neural architecture search with expert advice. arXiv preprint arXiv: 1906. 08031, 2019.
A. Noy, N. Nayman, Ridnik, N. Zamir, S. Doveh, I. Friedman, R. Giryes, and L. Zelnik-Man -anno.. Asap: Architecture search, anneal and prune. arXiv preprint arXiv:1904.044 2019.
H. Pham, M. Guan, B. Zoph, Q. Le, and J. Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning. 2018.
E. Real, S. Moore, A. Selle, S. Saxena, Y. L. Suematsu, J. Tan, Q. V. Le, and A. Kurakin. Large-scale evolution of image classifiers. In International Conference on Machine Learning, 2017.
E. Real, A. Aggarwal, Y. Huang, and Q. Le. Regularized evolution for image classifier architec- ture search. In AAAI Conference on Artificial Intelligence, 2019.
O. Russakovsky, Deng, H. Su, J. Krause, Satheesh, S. Ma, Huang, A. Karpathy, A. Khosla, M. Bernstein, al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 115(3):211225 2015.
N. Srivastava, G. E. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1): 1959-1958, 2014.
C. Szegedy, W. Liu, Y. Jia, Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Ra- binovich. Going deeper with convolutions. In Computer Vision and Pattern Recognition, 2015.
M. Tan and Q Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning. 2019.
M. Tan, B. Chen, R. Pang, V. Vasudevan, M. Sandler, A. Howard, and Q. V. Le. Mnasnet: Platform- aware neural architecture search for mobile. In Computer Vision and Pattern Recognition, 2019.
L. Xie and A. L. Yuille. Genetic CNN. In International Conference on Computer Vision, 2017.
Xie, H. Zheng, C. Liu, and L. Lin. SNAS: Stochastic neural architecture search. arXiv preprint arXiv: 1oXiv:18/2,00 089260992, 2018.
Xie, A. Kirillov, Girshick, and K. He. Exploring randomly wired neural networks for image recognition. In International Conference on Computer Vision, 2019.
Y. Xu, L. Xie, X. Zhang, X. Chen, G. Qi, Q. Tian, and H. Xiong. Pe-darts: Partial channel connec- tions for memory- differentiable architecture search. arXiv preprint arXiv: arXiv:1907.05737, 2019.
X. Zhang, X. Zhou, M. Lin, and Sun. Shufflenet: An extremely efficient convolutional neural network for mobile devices. In Computer Vision and Pattern Recognition, 2018.
H. Zhou, M. Yang, J. Wang, and W. Pan. Bayesnas: A bayesian approach for neural architecture search. arXiv preprint arXiv: httl::/905.0999 999999499, 2019.
B. Zoph and Q V. Le. Neural architecture search with reinforcement learning. In International Conference on Learning Representations, 2017.
B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In Computer Vision and Pattern Recognition, 2018
12

---

Under review as a conference paper at ICLR 2020
A APPENDIX
A.1 A TOY EXAMPLE TO SHOW THE IMPORTANCE OF 82
(wx a)² Then, the only difference between Ltaain (w, L (w, a;; Dirain) and Lvalid (w, a) = L (w, a Evalid) lies in the input, a. As- sume the input of training data is Etrain
Let the loss function be (w,
and the input validation data is Evalid 2. It is easy to derive that the local optimum of Lirain (w,a) a) is w (a) a. Substituting Evalid = 2 into Lvalid (w, ax) yields Lvlldd (w, a) (2w a)² When
az,, arrives w" (a.), so
gi = 2a 20x,)= = 2a, and g2 = 4a,- When w arrives at w (ax), Liaatd (w" (ax) a)) = a², g (a.) 20; = gi + g2. In summary, both gi and g2 are important, but DARTS chose to ignore 82 which can cause a dramatic error in approximation.
A.2 THE COMPLEXITY OF 82 CAN BE SUBSTANTIALLY REDUCED USING THE FINITE DIFFERENCE APPROXIMATION
We use the finite difference approximation just like DARTS. Let 6. be a small scalar, WI + Lval VaLisainlli.c
W2
wW ar). Then: H. (w,
-V VVw.irssnlw2aa))
w + VuLuaillr VWW-eniiiuzaa W1 = w
26 (1) (uniniiaw
Then: g2 n Fufralws, () - -VVuualaaa))
W3
2c
A.3 A TOY EXAMPLE TO SHOW THE IMPORTANCE OF THE "GRADIENT TRAP"
We have small toy to show the influence of the "gradient trap". We searched for small super-network in the DARTS's ' search space, which only has two cells we searched for 600 epochs).
When train the super-network in the "training sets in search phase" and validate in the "validation sets in search phase", the test error using g2 is 10.5% while the test error without g2 is 12.8%.
When we train the super-netword in the training sets and validate in the validation sets, the test error using 82 is 5.4% while the test error without g2 is 7.4%.
When generalize and train the network in the training sets and validate in the validation sets, the test error using 82 is 6.2% while the test error without 82 is 7.4%.
In this case the "gradient trap" will cause a dramatic accuracy drop of the super-network.
A.4 SEARCH WITH DIFFERENT SEEDS
We ran our search algorithms with different seeds for times Sy and evaluated each discovered architecture for 3 times. The lowest test error is 2.57 and the highest is 0..1%. We did the same thing on S₁ and the lowest and the highest test errors are 2.71 0.15% and 2.92 + 0.09%, respectively.
As we expected, the results in S are less robust than those in Sz. The main reason is the difference between search and evaluation, including the different depths of search and evaluation networks and the the discretization stage of the standard DARTS method.
More importantly, our approach survives after 500 (and even more) epochs, while DARTS degener- ates to an all-skip-connect architecture in all (10+) individual runs.
A.5 THEORETICAL ANALYSIS OF SEMI- MATRIX AFTER SIMILARITY TRANSFORMATION
A CT C, A is cumi--psitive-defiiii matrix. In this case, the number of different eigenvalues far less than the dimension of A (hundreds compared to millions). H is a real symmetric positive- definite matrix.
13

---

Under review as a conference paper at ICLR 2020
Let {a;} be set of cigenvectors w.n. A(a a; 1), then (H a:) is set of eigenvectors w.rt
H A T. (H ( .a.) a set of eigenvectors w.r. H A H. and {A,} a set of eigenvectors
shared by them.
Let B be an eigenvector of - A.H E a; X a: = E 6 x a.
- + H B AB,
E a x x a: + Ei b H a =
E a: H a; = b x H-l.ca.
EL (A - (A: - b) H (4
a: 0
A a real symmetric matrix, so we have many sets of {ax that is orthogonal to each other. 3 3 E b; 2 0, For every eigenvalue, the dimension of the subspace will be very high in the case of neural architecture search, so we assume that we can choose a set of {a; orthogonal to each other from the subspace satisfying Lj=n; - bjbj 2 0 in most cases(nj is the id of the first eigenvector w.r.t A
E (A; - a; = E (A
anb; I 0, so À cannot be smaller than zero
All of the eigenvalues w.r.t real symmetric matrix H A H + H A H is not smaller than zero, so is semi-positive-defiiit. Then we get that --1 A H semi-positive-defniie
14


Reviews:
[{"review_id": "rJgeM3MhtB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nSome major concerns:\n* 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.\n* 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.\n* 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).\n\nMinor issue:\n\nIn 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.\n\nQuestion:\n* 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?\n* 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.\n\n[1] Pedregosa, Fabian. \"Hyperparameter optimization with approximate gradient.\", ICML 2016\n\n==== post-rebuttal comments ====\nI 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:\n(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.\n(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.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SkgXDcgdqB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*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.\n\nThe 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.\nThe 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.\n\nMinor questions (related to writing/exposition):\nHow is Eqn2 different from Eq3? If they are the same, please remove the redundant equation (you already repeat it in the Introduction).\nWhy 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.\nSection 4.1.2: What is \"auxiliary loss tower\"?\n\nAbstract: \"obstacles it\" (obstacles is an awkward verb, perhaps use \"hinders it\" instead)\nIntroduction: \"was very few covered in previous works\" is an awkward phrase. \"has not been studied carefully in previous works\"\nRelated work: \"exhausted search\" -> \"exhaustive search\"\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SJeCAhFpFH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "--- response after the author's rebuttal ---\n\nThank the authors to provide their response and let me clearly understand their contribution.\n\nHowever, 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. \n\nAuthors 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. \n\nAs 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. \n\n--- original review---\n\n\nSummary\n\nThe 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.\nIt shows the experiments in both original DARTS search space with changes in the search phase, as well as a larger space with fewer operations. \n\nThe 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.\n\nMajor concerns\n\nAbout the derivation\n\n- 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? \n\n- Computation of the Hessian matrix is missing, and the motivation to use g2'. \nThe 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'? \n\nI 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?\n\n- 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. \n\nAbout experiments\n\n- 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. \n\n- Additional experiments for a fair comparison with baseline DARTS.\nExperiment 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.\n\nMinor comments.\n\n- Would the author kindly clarify the following points I found confusing during the reading? \n\n1. 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? \n2. Section 3.3 line 7, is \"fundamentals in mathematics\" referring math foundations?\n\n3. Equation 2, 3 are repetitive for no good reason?\n\n4. In table 1,2 Random search results for S2 are missing. Could the author also listed for better comparison?\n\n5. The second line after equation (3), \"estimating \\nabla ... ^2\" why is this a square while in equation (3) it's not?\n\n\n- generalization comparison with DARTS+, XNAS, etc. \nSince 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.\n\n- 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:\n1. Introduction page 2, \"In all experiments\", 'I' should not be in bold. \n2. line after equation 5, \"throughout the remainder of this paper\" remainder -> remaining.\n\n\n--- Reference ---\n[1] Anonymous, UNDERSTANDING AND ROBUSTIFYING DIFFERENTIABLE ARCHITECTURE SEARCH, link: https://openreview.net/forum?id=H1gDNyrKDS.\n[2] Radosavovic et al., On Network Design Spaces for Visual Recognition, ICCV'19.\n[3] Li and Talwalker, Random Search and Reproducibility for Neural Architecture Search, UAI'19.\n[4] Scuito et al., Evaluating the search phase of neural architecture search, arxiv'19.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gPFMEBcr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nStrength:\n[1] Theoretical analysis\n[2] The paper is well written\n[3] This paper is trying to solve a very interesting and important problem\n\nWeakness:\n[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?\n[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\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

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