Stabilizing DARTS with Amended Gradient Estimation on Architectural Parameters

Introduction

Neural architecture search (NAS) has been an important topic in the research area of automated machine learning (AutoML). The idea is to replace the manual design of 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 adopted heuristic search methods such as reinforcement learning (Zoph & Le, 2017; Zoph et al., 2018) and evolutionary algorithms (Real et al., 2017; Xie & Yuille, 2017) to sample networks from a large search space, and optimizing each sampled network individually to evaluate its quality. Despite notable success by this methodology, it often requires a vast amount of computation, which obstacles its applications in the scenarios of limited resources. Inspired by reusing and sharing parameters among trained networks, DARTS (Liu et al., 2019) was designed as a ‘one-shot’ solution of NAS. The idea is to incorporate all possibilities into a super-network and then adopt a differentiable mechanism to optimize model weights (such as convolution) and architectural weights simultaneously, following which the best sub-network is sampled to be the final architecture.

Although DARTS reduced the search cost by $1$–$2$ orders of magnitudes (to a few hours on a single GPU), it suffers a critical weakness known as instability. Researchers reported that DARTS-based algorithms can sometimes generate weird architectures that produce considerably worse accuracy than those generated in other individual runs (Zela et al., 2020). Although some practical methods (Chen et al., 2019; Nayman et al., 2019) have been developed to reduce search variance, the following property of DARTS persists and has not been studied thoroughly: when DARTS gets trained for sufficiently long, e.g., extending the default number of $50$ epochs to $200$ epochs, almost all DARTS-based approaches converge to a dummy architecture in which all edges are occupied by skip-connect. These architectures, with few trainable parameters, are often far from producing high accuracy, in particular, on large datasets like ImageNet, although the validation accuracy in the search stage continues growing with more epochs.

In essence, this observation refers to that an improved validation accuracy of the super-network does not necessarily lead to high-quality sub-networks to be sampled. We name it the optimization gap between search and re-training, and investigate it from a perspective which is less studied before. We reveal that DARTS has been using an inaccurate approximation to calculate the gradients with respect to the architectural parameters ($\bm{\alpha}$ as in the literature), and we amend the error by slightly modifying the second-order term in gradient computation. Mathematically, we prove that the amended term has a bounded error, i.e., the angle between the true and estimated gradients is smaller than $90^{\circ}$, while the original DARTS did not guarantee so. With this modification, the search performance is stabilized and the dummy all-skip-connect architecture does not appear even after a very long search process. Consequently, one can freely allow the search process to arrive at convergence, and hence the sensitivity to hyper-parameters is alleviated.

Practically, our approach involves using an amended second-order gradient, so that the computational overhead is comparable to the second-order version of DARTS. Experiments are performed on two popular image classification datasets, namely, CIFAR10 and ImageNet. In all experiments, the search process, after arriving at convergence, produces competitive architectures and classification accuracy comparable to the state-of-the-arts.

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 a complicated feature space. Recent years have witnessed the trend of using deeper (He et al., 2016) and denser (Huang et al., 2017) networks to boost recognition performance, while there is no justification that whether these manually designed architectures are best for each specific task, e.g., image classification. Recently, researchers started considering the possibility of learning network architectures automatically from data, which led to the appearance of neural architecture search (NAS) (Zoph & Le, 2017), which is now popular and known as a sub research field in automated machine learning (AutoML).

The common pipeline of NAS starts with a pre-defined space of network operators. Since the search space is often large (e.g., containing $10^{10}$ or even more possible architectures), it is unlikely that exhaustive search is tractable, and thus heuristic search methods are widely applied for speedup. Typical examples include reinforcement learning (Zoph & Le, 2017; Zoph et al., 2018; Liu et al., 2018a) 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 distribution, evaluates them and learns from rewards by updating the distribution. In an early age, each sampled architecture undergoes 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 the sampled architectures, with the key lying in reusing network weights trained previously (Cai et al., 2018) or starting from a well-trained super-network (Pham et al., 2018). These efforts shed light on the ‘one-shot’ architecture search methods, which require training the super-network only once and thus run more efficiently, e.g., $2$–$3$ 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 to apply end-to-end optimization for training network and architectural parameters simultaneously. This methodology is known today as differentiable NAS, and a typical example is DARTS (Liu et al., 2019), which constructed a super-network 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 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 (Li & Talwalkar, 2019; Sciuto et al., 2019), 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., 2019), or using other kinds of techniques such as decoupling modules (Cai et al., 2019; Guo et al., 2019), adjusting search space during optimization (Noy et al., 2019; Chen et al., 2019; Nayman et al., 2019), regularization (Xu et al., 2020), early termination (Liang et al., 2019), etc., however, these approaches seem to develop heuristic remedies rather than analyze it from the essence, e.g., how instability happens in mathematics, which this paper delves deep into this problem and presents a preliminary solution.

Stabilizing DARTS with Amended Architectural Gradient Estimation

Differentiable NAS approaches start with defining a super-network, which is constrained in a search space with a pre-defined number of layers and a 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), so that optimization can be done in an end-to-end manner. Mathematically, the super-network is a function $\mathbf{f}\!\left(\mathbf{x};\bm{\omega},\bm{\alpha}\right)$, with $\mathbf{x}$ being input, and parameterized by network parameters $\bm{\omega}$ (e.g., convolutional kernels) and architectural parameters $\bm{\alpha}$ (e.g., indicating the importance of each operator between each pair of layers). $\mathbf{f}\!\left(\mathbf{x};\bm{\omega},\bm{\alpha}\right)$ is differentiable to both $\bm{\omega}$ and $\bm{\alpha}$, so that gradient-based approaches (e.g., SGD) can be applied for optimization.

In the example of DARTS, $\mathbf{f}\!\left(\mathbf{x};\bm{\omega},\bm{\alpha}\right)$ is composed of a few cells, each of which contains $N$ nodes, and there is a pre-defined set, $\mathcal{E}$, denoting which pairs of nodes are connected. For each connected node pair $\left(i,j\right)$, $i<j$, node $j$ takes $\mathbf{x}_{i}$ as input and propagates it through a pre-defined operator set, $\mathcal{O}$, and sums up all outputs:

Here, normalization is performed by computing softmax on the architectural weights. Within each unit of the search process, $\bm{\omega}$ and $\bm{\alpha}$ get optimized alternately. After that, the operator $o$ with the maximal value of $\alpha_{o}^{\left(i,j\right)}$ is preserved for each edge $\left(i,j\right)$. All network parameters $\bm{\omega}$ are discarded and the obtained architecture is re-trained from scratch.

2 The Optimization Gap of DARTS

Our research is motivated by an observation that DARTS, at the end of a regular training process with, say, $50$ epochs (Liu et al., 2019), has not yet arrived at convergence. To verify this, we increase the length of each training stage from $50$ to $200$ epochs, and observe two weird facts shown in Figure 1. First, the weight of the none operator monotonically goes up – at $200$ epochs, the weight has achieved $0.95$ on most edges of the normal cells, however, the none operator is not considered in the final architecture. Second, almost all preserved operators are the skip-connect (a.k.a., identity) operator, a parameter-free operator that contributes little to feature learning – and surprisingly, it occupies $30\%$ to $70\%$ of the weight remained by the none operator. Such a network has very few trainable parameters, and thus usually reports unsatisfying performance at the re-training stage, in particular, lower than a randomly sampled network (please refer to the experiments in Section 4.1.2).

Despite dramatically bad sub-networks are produced, the validation accuracy of the super-network keeps growing as the search process continues. In a typical run of the first-order DARTS on CIFAR10, from $50$ to $200$ search epochs, the validation accuracy of the super-network is boosted from $88.82\%$ to $91.06\%$, while the re-training accuracy of the final architecture reduced from $97.00\%$ to $93.82\%$. This implies an optimization gap between the super-network and its sub-networks. Specifically, the search process aims to improve the validation accuracy of the super-network, but this does not necessarily result in high accuracy of the optimal sub-network determined by the architectural parametersThis opinion is different from that of (Zela et al., 2020), which believed a super-network with higher validation accuracy must be better, and owed unsatisfying sub-network performance to the final discretization step of DARTS. Please refer to Appendix A.1 for the detailed elaboration., $\bm{\alpha}$. A practical solution is to terminate the search process early (Liang et al., 2019), however, despite its effectiveness, early termination makes the search result sensitive to the initialization ($\bm{\alpha}$ and $\bm{\omega}$), the hyper-parameters of search (e.g., learning rate), and the time of termination. Consequently, the stability of DARTS is inevitably weakened.

3 Amending the Architectural Gradients

Again, applying the chain rule to the left-hand side gives:

Note that no approximation has been made till now.

To compute $\mathbf{g}_{2}$, the main difficulty lies in $\mathbf{H}^{-1}$ which, due to the high dimensionality of $\mathbf{H}$ (over one million in DARTS), is computationally intractable. We directly replace $\mathbf{H}^{-1}$ with $\mathbf{H}$, which leads to an approximated term:

where ${\eta}>{0}$ is named the amending coefficient, the only hyper-parameter of our approach, and its effect will be discussed in the experimental section. A nice property of $\mathbf{g}_{2}^{\prime}$ is that the angle between $\mathbf{g}_{2}$ and $\mathbf{g}_{2}^{\prime}$ does not exceed $90^{\circ}$(i.e., ${\left\langle\mathbf{g}_{2}^{\prime},\mathbf{g}_{2}\right\rangle}\geqslant{0}$, as proved in Appendix A.3).

As the final step, we compute $\mathbf{g}_{1}$ and $\mathbf{g}_{2}^{\prime}$ following the second-order DARTS (see Appendix A.4). Overall, the computation of Eqn (6) requires similar computational costs of the second-order DARTS. On an NVIDIA Tesla-V100 GPU, each search epoch requires around $0.02$ GPU-days on the standard $8$-cell search space on CIFAR10.

4 Why Is Our Approach Better Than DARTS?

On the contrary, with an amended approximation, $\mathbf{g}_{2}^{\prime}$, our approach can survive after a sufficiently long search process. The longest search process in our experiments has $500$ epochs, after which the architecture remains mostly the same as that after $100$ epochs. In addition, the final architecture seems converged, i.e., will not change even with more search epochs, as (i) the none operator does not dominate any edge; and (ii) the weight of the dominating operator in each edge is still gradually increasing.

5 Hyper-Parameter Consistency

Our goal is to bridge the optimization gap between the search and re-training phases. Besides amending the architectural gradients to avoid ‘over-fitting’ the super-network, another important factor is to make the hyper-parameters used in search and re-training consistent. In the contexts of DARTS, examples include using different depths (e.g., DARTS used $8$ cells in search and $20$ cells in re-training) and widths (e.g., DARTS used a basic channel number of $16$ in search and $36$ in re-training), as well as using different training strategies (e.g., during re-training, a few regularization techniques including Cutout (DeVries & Taylor, 2017), Dropout (Srivastava et al., 2014) and auxiliary loss (Szegedy et al., 2015) were used, but none of them appeared in search). More importantly, the final step of search (removing $6$ out of $14$ edges from the structure) can cause another significant gap. In Section 4.1.2, we will discuss some practical ways to bridge these gaps towards higher stability. For more analysis on this point, please refer to Appendix B.1.

6 Discussions and Relationship to Prior Work

A few prior differentiable search approaches noticed the issue of instability, but they chose to solve it in different manners. For example, P-DARTS (Chen et al., 2019) fixed the number of preserved skip-connect operators, PC-DARTS (Xu et al., 2020) used edge normalization to eliminate the none operator, while XNAS (Nayman et al., 2019) and DARTS+ (Liang et al., 2019) introduced a few human expertise to stabilize search. However, we point out that (i) either P-DARTS or PC-DARTS, with carefully designed methods or tricks, can also fail in a long enough search process (more than $200$ epochs); and that (ii) XNAS and DARTS+, by adding human expertise, somewhat violated the design principle 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, e.g., validation accuracy. In the viewpoint of optimization, this pipeline mainly differs from the differentiable one in that optimizing $\bm{\alpha}$ is decoupled from optimizing $\bm{\omega}$, so that it does not require $\bm{\omega}$ to arrive at $\bm{\omega}^{\ast}$, but only need a reasonable approximation of $\bm{\omega}^{\ast}$ to predict model performance – this is an important reason that such algorithms often produce stable results. Our approach sheds light on introducing a similar property, i.e., robustness to approximated $\bm{\omega}^{\star}$, which helps in stabilizing differentiable search approaches.

Experiments

The CIFAR10 dataset (Krizhevsky & Hinton, 2009) has $50\rm{,}000$ training and $10\rm{,}000$ testing images, equally distributed over $10$ classes. We mainly use this dataset to evaluate the stability of our approach, as well as analyze the impacts of different search options and parameters.

We search and re-train similarly as DARTS. During the search, all operators are assigned equal weights on each edge. The batch size is set to be $96$. An Adam optimizer is used to update architectural parameters, with a learning rate of $0.0003$, a weight decay of $0.001$ and a momentum of $\left(0.5,0.999\right)$. 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 starting from $0.025$, decaying with cosine annealing, and arriving at after $600$ epochs. The weight decay is set to be $0.0003$, and the momentum is $0.9$.

We first investigate how the amending coefficient, $\eta$, defined in Eqn (6), impacts architecture search. To arrive at convergence, we run the search stage for $500$ epochs. We evaluate different $\eta$ values from to $1$, and the architectures corresponding to small, medium and large amending coefficients are summarized in Figure 2.

We can see that after $500$ epochs, ${\eta}={0.1}$ produces a reasonable architecture that achieves an error rate of $3.08\%$ on CIFAR10. Actually, even with more search epochs, this architecture is not likely to change, as the preserved operator on each edge has a weight not smaller than $0.5$, and most of these weights are still growing gradually.

When $\eta$ is very small, e.g., ${\eta}={0.001}$ or ${\eta}={0.01}$, the change brought by this amending term to architecture search is negligible, and our approach shows almost the same behavior as the first-order version of DARTS, i.e., ${\eta}={0}$. In addition, in such scenarios, although the search process eventually runs into an architecture with all skip-connect operators, the number of epochs needed increases significantly, which verifies that the amending term indeed pulls architecture search away from degeneration.

On the other hand, if we use a sufficiently large $\eta$ value, e.g., ${\eta}={1}$, the amending term, $\mathbf{g}_{2}^{\prime}$, can dominate optimization, so that the first term, i.e., the gradient of architectural parameters, has limited effects in updating $\bm{\alpha}$. Note that the amending term is closely related to network regularization, therefore, in the scenarios of a large $\eta$, the network significantly prefers avg-pool-3x3 to other operators, as average pooling can smooth feature maps and avoid over-fitting. However, pooling is also a parameter-free operator, so the performance of such architectures is also below satisfaction.

Following these analyses, we simply use ${\eta}={0.1}$ for all later experiments. We do not tune $\eta$ very carefully, though it is possible to determine $\eta$ automatically using a held-out validation set. Besides, we find that the best architecture barely changes after $100$ search epochs, so we fix the search length to be $100$ epochs to reduce computational costs.

1.2 Towards Stabilized Search Performance

Next, we investigate the stability of our approach by comparing it (with ${\eta}={0.1}$) to DARTS (Liu et al., 2019), P-DARTS (Chen et al., 2019), and PC-DARTS (Xu et al., 2020). We run all the competitors for $200$ search epochsFor P-DARTS, we run each of its three search stages for $100$ epochs, and do not use the heuristic rule that preserves exactly two skip-connect operators. to guarantee convergence in the final architecture. Results are summarized in Table 1. One can see that all others, except PC-DARTS, produce lower accuracy than that of random search (some of them, DARTS and P-DARTS, even degenerate to all-skip-connect architectures), but our approach survives, indicating the amended approximation effectively boosts search robustness. Moreover, we verify the search stability by claiming a $0.58\%$ advantage over random search.

Table 1 also provides an ablation study by switching off the amending term or the consistency of training hyper-parameters (i.e., adding Cutout, Dropout, and the auxiliary loss tower to the search stage with the same parameters, e.g., the Dropout ratio, as they are used in re-training). Without any one of them, the error rate significantly increases to more than $3\%$, still better than random search but the advantage becomes much weaker. These results verify our motivation, i.e., shrinking the optimization gap from any aspects can lead to better search performance. The architectures with and without unified hyper-parameters are shown in Figure 3 (top) and Figure 2 (middle), respectively.

We also perform experiments in the simplified search space defined by (Zela et al., 2020). Without bells and whistles, we obtain an error rate of $2.55\%$ which is significantly better than random search ($3.05\%$) reported in the paper. Please refer to Appendix C.1 for more results under this setting.

1.3 Exploring More Complex Search Spaces

Driven by the benefit of shrinking the optimization gap, we further apply two modifications. First, to avoid edge removal, we partition the search stage into two sub-stages: the former chooses $8$ active edges from the $14$ candidates, and the latter, restarting from scratch, determines the operators on each preserved edge. Technical details are provided in Appendix B.2. Another option that can save computational costs is to fix the edges in each cell, e.g., each node $i$ is connected to node $i-1$ and the least indexed node (denoted by $c_{k-2}$ in most conventions). 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 use the same width (i.e., the number of basic channels, $36$) and depth (i.e., the number of cells, $20$) in both search and re-training. The modification on depth reminds us of the depth gap (Chen et al., 2019) between search and re-training (the network has $8$ cells in search, but $20$ cells in re-training). Instead of using a progressive search method, we directly search in an augmented space (see the next paragraph), thanks to the improved stability of our approach.

We denote the original search space used in DARTS as $\mathcal{S}_{1}$, which has six normal cells and two reduction cells, and all cells of the same type share the architectural parameters. This standard space contains $1.1\times 10^{18}$ distinct architectures. We also explore a more complex search space, denoted by $\mathcal{S}_{2}$, in which we relax the constraint of sharing architectural parameters, meanwhile the number of cells increases from $8$ to $20$, i.e., the same as in the re-training stage. Here, since the GPU memory is limited, we cannot search with all seven operators, so we only choose two, namely skip-connect and sep-conv-3x3, which have very different properties. This setting allows a total of $1.9\times 10^{93}$ architectures to appear which significantly surpasses the capacity of most existing cell-based search spaces.

The searched results in $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ with fixed or searched edges are shown in Figure 3, and their performance summarized in Table 2. By directly searching in the target space, $\mathcal{S}_{2}$, the error is further reduced from $2.71\%$ to $2.60\%$ and $2.63\%$ with fixed and searched edges, respectively. The improvement seems small on CIFAR10, but when we transfer these architectures to ImageNet, the corresponding advantages become more significant ($0.4\%$, see Table 3).

We also execute DARTS (with early termination, otherwise it fails dramatically) and random search on $\mathcal{S}_{2}$ with the fixed-edge setting, and they report $0.25\%$ and $0.29\%$ deficits compared to our approach (DARTS is slightly better than random search). When we transfer these architectures to ImageNet, the deficits become more significant ($1.7\%$ and $0.8\%$, respectively, and DARTS performs even worse). This provides a side evidence to randomly-wired search (Xie et al., 2019), advocating for the importance of designing stabilized approach on large search spaces.

1.4 Comparison to the State-of-the-Arts

Finally, we compare our approach with recent approaches, in particular, differentiable ones. Result are shown in Table 2. Our approach produces competitive results among state-of-the-arts, although it does not seem 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 be terminated in an early stage, which makes them less convincing as search has not arrived at convergence. These tricks somewhat violate the ideology of neural architecture search; in comparison, our approach, though not producing the best performance, promises a more theoretically convinced direction.

2 Results on ImageNet

The comparison of our approach to existing work is shown in Table 3. In the augmented search space, $\mathcal{S}_{2}$, our approach reports a top-$1$ error rate of $24.3\%$ without either AutoAugment (Cubuk et al., 2019) or Squeeze-and-Excitation (Hu et al., 2018). This result, obtained after search convergence, is competitive among state-of-the-arts. In comparison, without the amending term, DARTS converges to a weird architecture in which some cells are mostly occupied by skip-connect and some others by sep-conv-3x3. This architecture reports a top-$1$ error of $26.0\%$, which is even inferior to random search ($25.1\%$). Last but not least, the deficit of $\mathcal{S}_{1}$, compared to $\mathcal{S}_{2}$, becomes more significant on ImageNet. This again verifies the usefulness of shrinking the optimization gap, in particular for challenging tasks.

3 Results on Penn Treebank

We also evaluate our approach on the Penn Treebank dataset, a popular language modeling task on which the recurrent cell connecting LSTM units are being searched (Zoph & Le, 2017; Pham et al., 2018; Liu et al., 2019). We follow the implementation of DARTS to build the search pipeline and make two modifications, namely, (i) amending the second-order term according to Eqn (6), (ii) unify the weight decay and variational Dropout ratio between search and evaluation. The search process continues till the architecture does not change for sufficiently long, and the evaluation stage is executed for $8\rm{,}000$ epochs (i.e., until convergence, following the released code of DARTS), on which the best snapshot on the validation set is transferred to the test set.

Results are shown in Table 4, and the searched recurrent cell shown in Figure 4. Note that the DARTS paper reported $58.1$/$55.7$ validation/test perplexity (ppl), but our reproduction obtains $58.5$/$56.3$, slightly lower than the original implementation. Our approach with amended gradients reports $57.1$/$54.8$, showing a significant gain over the baseline. As far as we know, this is the best results ever reported in the DARTS space. Prior DARTS-based approaches mostly reported worse results than the original DARTS (see Table 4), or restricted to image-level operations (e.g., PC-DARTS (Xu et al., 2020)), but our approach is a fundamental improvement over DARTS that boosts both computer vision and language modeling tasks. More importantly, we emphasize that after gradient fixation, the search process becomes more robust: we have achieved similar performance, in terms of ppl, using a few different random seeds, while the original DARTS seems quite sensitive to the random seed.

Conclusions

In this paper, we present an effective approach for stabilizing DARTS, the state-of-the-art differentiable search method. Our motivation comes from that DARTS-based approaches mostly converge to all-skip-connect architectures when they are executed for a sufficient number of epochs. We analyze this weird phenomenon mathematically and find the reason to be in the dramatic inaccuracy in gradient computation of the architectural parameters. With an alternative approximation based on the optimality of the network parameters, for the first time we can prove that the error of estimation is bounded, while previous work cannot. In standard image classification tasks, our approach shows improved stability, with which we are able to explore much larger search spaces and obtain better performance.

Our research sheds light on NAS research in several aspects. First, we reveal the importance of proper approximation in differentiable architecture search. Second, by fixing the error, we provide a platform for fairly comparing the ability of NAS itself rather than designing tricks. Third, thanks to improved stability, our algorithm can explore larger search spaces, which we believe is the future trend of NAS.

References

Appendix A Mathematical Proofs and Analyses

In this section, we provide some details to complement the theoretical part of the main article.

This part corresponds to Section 3.2 in the main article.

In (Zela et al., 2020), the authors believed that a super-network with a higher validation accuracy always has a higher probability of generating strong sub-networks, and they owed the weird behavior of DARTS to the discretization step (preserving the operator with the highest weight on each edge and discarding others) after the differentiable search phase. Here, we provide a different opinion, detailed as follows:

A high validation accuracy does not necessarily indicate a better super-network. In training a weight-sharing super-network, e.g., in DARTS, the improvement of validation accuracy can be brought by two factors, namely, the super-network configuration (corresponding to $\bm{\alpha}$) becomes better or the network weights (corresponding to $\bm{\omega}$) are better optimized. We perform an intuitive experiment in which we fix the initialized $\bm{\alpha}$ and only optimize $\bm{\omega}$. After $50$ epochs, the validation accuracy of the super-network is boosted from $10\%$ (random guess) to $88.28\%$. While the performance seems competitive among a regular training process, the sampled sub-network is totally random.

The advantage of our approach persists even without discretization-and-pruning. From another perspective, we try to skip the discretization-and-pruning step at the end of the search stage and re-train the super-network (with $\bm{\alpha}$ fixed) directly. To reduce computational costs, we use a shallower super-network, and perform both search and re-training for $600$ epochs on CIFAR10 to guarantee convergence. Without the amending term, the validation error in the search stage and the testing error in the re-training stage are $12.8\%$ and $7.4\%$, respectively, and these numbers become $10.5\%$ and $5.4\%$ after the amending term is added. This indicates that amending the gradient estimation indeed improves the super-network, and the advantage persists even when discretization-and-pruning is not used.

Therefore, our opinion is that the ‘optimization gap’ is brought by the inconsistency between search and re-training – edge pruning after search is one aspect, and the inaccuracy of gradient estimation is another one which seems more important. We alleviate the pruning issue by first selecting (or fixing) a few edges and then determining the operator on each preserved edge. However, such a two-stage search process can be very unstable if the gradient estimation remains inaccurate. In other words, amending errors in gradient computation lays the foundation of hyper-parameter consistency.

This part corresponds to Section 3.3 in the main article.

DARTS (Liu et al., 2019) owed the inaccuracy in computing $\mathbf{g}_{2}$ to that $\bm{\omega}^{\star}\!\left(\bm{\alpha}\right)$ is difficult to arrive at (e.g., requiring a lot of computation), and believed that $\mathbf{g}_{2}$ goes to $\mathbf{0}$ when the optimum is achieved. We point out that this is not correct even in a very simple example of convex optimization, detailed as follows.

In summary, $\mathbf{g}_{2}$ will not be zero even when $\bm{\omega}^{\star}$ is achieved, which implies that ignoring $\mathbf{g}_{2}$ may lead to a wrong direction of optimization – in the toy example above, the loss will increase monotonically towards infinity if $\mathbf{g}_{2}$ is ignored. We believe that this inaccuracy also contributed to the weird phenomena in real-world data (i.e., when DARTS was run on CIFAR10, the optimization process collapses to a dummy network architecture which produces poor classification results).

This part corresponds to Section 3.3 in the main article.

Substituting $\mathbf{g}_{2}$ and $\mathbf{g}_{2}^{\prime}$ into ${\left\langle\mathbf{g}_{2}^{\prime},\mathbf{g}_{2}\right\rangle}$ gives:

Let $\left\{\bm{\psi}_{k}\right\}$ be an orthogonal set of eigenvectors with respect to $\mathbf{A}$ (i.e., ${\bm{\psi}_{k}^{\top}\cdot\bm{\psi}_{k}}={1})$, and $\left\{\lambda_{k}\right\}$ be the corresponding eigenvalues satisfying ${\lambda_{k}}\geqslant{\mathbf{0}}$. Let $\bm{\phi}_{l}$ be an eigenvector of $\mathbf{H}\cdot\mathbf{A}\cdot\mathbf{H}^{-1}+\mathbf{H}^{-1}\cdot\mathbf{A}\cdot\mathbf{H}$, and expanding $\mathbf{H}\cdot\bm{\phi}_{l}$ and $\mathbf{H}^{-1}\cdot\bm{\phi}_{l}$ based on $\left\{\bm{\psi}_{k}\right\}$ derives the following equation for any $l$:

where $\left\{a_{k}\right\}$ and $\left\{b_{k}\right\}$ are the corresponding expansion coefficients. According to the definition of eigenvalues, we have:

where $\mu_{l}$ is the corresponding eigenvalue of $\bm{\phi}_{l}$. Substituting Eqn (11) into Eqn (12), we obtain:

Left-multiplying Eqn (13) by $\left[\sum_{k=1}^{K}b_{k}\cdot\left(\lambda_{k}-\mu_{l}\right)\cdot\left(\mathbf{H}^{-1}\cdot\bm{\psi}_{k}\right)\right]^{\top}$ obtains:

$\mathbf{A}$ is a real symmetric matrix sized $M_{1}\times M_{1}$, and it is obtained by multiplying a $M_{1}\times M_{2}$ matrix to a $M_{2}\times M_{1}$. Here, $M_{1}$ and $M_{2}$ are the dimensionality of $\bm{\omega}$ and $\bm{\alpha}$, respectively, and $M_{1}$ is often much larger than $M_{2}$ (e.g., millions vs. hundreds in DARTS). Hence, $\mathbf{A}$ has much fewer different eigenvalues compared to its dimensionality, and so we can choose many sets of $\left\{\bm{\alpha}_{k}\right\}$ which are orthogonal to each other, and generate many sets of $\left\{a_{k}\right\}$ and $\left\{b_{k}\right\}$ satisfying ${\sum_{k=1}^{K}\mathbf{a}_{k}\mathbf{b}_{k}}={\bm{\beta}^{\top}\cdot\bm{\beta}}\geqslant{0}$. That being said, in most of time, we can choose one set of eigenvectors from the subspace, $\left\{\bm{\alpha}_{k}\right\}$, and the elements within are orthogonal to each other, which makes ${\mathbf{a}_{k}\mathbf{b}_{k}}\geqslant{0}$ in most cases, and hence ${\mu_{l}}\geqslant{0}$ for any $l$.

Since all of the eigenvalues with respect to the real symmetric matrix $\mathbf{H}\cdot\mathbf{A}\cdot\mathbf{H}^{-1}+\mathbf{H}^{-1}\cdot\mathbf{A}\cdot\mathbf{H}$ is not smaller than zero, so it is semi-positive-definite. This derives that $\mathbf{H}^{-1}\cdot\mathbf{A}\cdot\mathbf{H}$ is semi-positive-definite, and thus ${\left\langle\mathbf{g}_{2}^{\prime},\mathbf{g}_{2}\right\rangle}\geqslant{0}$.

This part corresponds to Section 3.3 in the main article.

Appendix B Technical Details and Search Costs

An important contribution of this paper is to reveal the need of hyper-parameter consistency, i.e., using the same set of hyper-parameters, including the depth and width of the super-network, the Dropout ratio, whether to use the auxiliary loss term, not to prune edges at the end of search, etc. This is a natural idea in both theory and practice, but most existing work ignored it, possibly because its importance was hidden behind the large optimization gap brought by the inaccurate gradient estimation in the bi-level optimization problem.

We point out that even when bi-level optimization works accurately, we may miss the optimal architecture(s) without hyper-parameter consistency. This is because each hyper-parameter will more or less change the value of the loss function and therefore impact the optimal architecture. We provide a few examples here.

The most sensitive change may lie in the edge pruning process, i.e., preserving $8$ out of $14$ edges in each cell and eliminating others. This may incur significant accuracy drop even when only one edge gets pruned. For example, in the normal cell searched on the $\mathcal{S}_{1}$-A space (see Figure 9), removing the skip-connect operator will cause the re-training error to increase from $2.71\%\pm 0.09$ to $3.36\%\pm 0.08$. The dramatic performance drop is possibly due to the important role played by the pruned edge, e.g., the pruned skip-connect may contribute to rapid information propagation in network training.

Some hyper-parameters will potentially change the optimal architecture. The basic channel width and network depth are two typical examples. When the channel number is small, the network may expect large convolutional kernels to guarantee a reasonable amount of trainable parameters; also, a deep architecture may lean towards small convolutional kernels since the receptive field is not a major bottleneck. However, the original DARTS did not unify these quantities in search and re-training, which often results in sub-optimality as noticed in (Chen et al., 2019).

Other hyper-parameters, in particular those related to the training configuration, are also important. For example, if we expect Dropout to be used during the re-training stage, the optimal architecture may contain a larger number of trainable parameters; if the auxiliary loss tower is used, the optimal architecture may be deeper. Without hyper-parameter consistency, these factors cannot be taken into consideration.

B.2 Details of the Two-Stage Search Process

To avoid the optimization gap brought by edge pruning, we adopt a two-stage search process in which we perform edge search followed by operator search. In the DARTS setting, the first stage involves preserving $8$ out of $14$ edges to be preserved. For each node, indexed $j$, we use $\mathcal{E}_{j}$ to denote the set of all combinations of edges (in the DARTS setting, each node preserves two input edges, so $\mathcal{E}_{j}$ contains all $\left(i_{1},i_{2}\right)$ pairs with ${0}\leqslant{i_{1}}<{i_{2}}<{j}$). The output of node $j$ is therefore computed as:

where $\beta^{\left(i_{1},i_{2}\right)}$ denotes the edge-selection parameter of the node combination of $\left(i_{1},i_{2}\right)$. This mechanism is similar to the edge normalization introduced in (Xu et al., 2020) but we take the number of preserved inputs into consideration.

After edge selection is finished, a regular operator search process, starting from scratch, follows on the preserved edges to determine the final architecture.

B.3 Search Cost Analysis

Note that the first (edge selection) stage requires around $2\times$ computational costs compared to the second (operator selection) stage. This is because edge selection works on $14$ edges while operator selection on $8$ edges. Fortunately, the former stage can be skipped (at no costs) if we choose to search operators on a fixed edge configuration, which also reports competitive search performance.

Appendix C Additional Experimental Results

Our approach works smoothly in this space, without the need of tuning hyper-parameters, and in either pruned or searched edges (see Figure 6). Thanks to the reduced search space, the best architecture often surpasses the numbers we have reported in Table 2.

C.2 200200200 Search Epochs for DARTS, P-DARTS, PC-DARTS, and Our Approach

We execute all algorithms for $200$ search epochs on CIFAR10. The searched architectures by DARTS, P-DARTS, and PC-DARTS are shown in Figure 7, and that of our approach shown in Figure 3.

We find that both DARTS and P-DARTS failed completely into dummy architectures with all preserved operators to be skip-connect. PC-DARTS managed to survive after $200$ epochs mainly due to two reasons: (i) the edge normalization technique is useful in avoiding skip-connect to dominate; and (ii) PC-DARTS sampled $1/4$ channels of each operator, so that the algorithm converged slower – $200$ epochs may not be enough for a complete collapse.

We also visualize our approach throughout $200$ epochs in $\mathcal{S}_{1}$ (under the edge-pruning setting) to investigate its behavior. In Figure 8, the visualized factors include the average weight of none, the ratio of preserved skip-connect operators, the super-network validation accuracy, and the re-training accuracy of some checkpoints during the search process.

C.3 Searching with Different Seeds

On CIFAR10, we perform edge search (the first search stage) in $\mathcal{S}_{2}$ with different seeds (i.e., random initialization), yielding three sub-architectures named $\mathcal{S}_{2}$-A, $\mathcal{S}_{2}$-B, and $\mathcal{S}_{2}$-C. Then, we execute the operator search process with different seeds for $3$ times in $\mathcal{S}_{1}$ (with edge pruning), $\mathcal{S}_{2}$-A, $\mathcal{S}_{2}$-B, $\mathcal{S}_{2}$-C, and $\mathcal{S}_{2}$-F (fixed edges), and re-train each discovered architecture for $3$ times. The results are summarized in Table 6. We also transfer some of the found architectures to ImageNet, and the corresponding results are listed in Table 7. The edge-searched architectures in $\mathcal{S}_{2}$ report inferior performance compared to the edge-fixed ones, arguably due to the inconsistency of hyper-parameters.

All the searched architectures are shown in Figures 9–12.