Operation-level Progressive Differentiable Architecture Search

Cell-based NAS methods [9, 14, 15] have been proposed to learn cells instead of architectures to reduce computation overhead in the process of architecture search. The networks consist of many same cell structures. A cell is similar to a directed acyclic graph (DAG), and it contains $N$ nodes, i.e., two input nodes, some intermediate nodes, and a single output node. Each node is a latent representation symbolized as $x^{(i)}$, and each directed edge denoted as $(i,j)$ represents an information flow that an operation $o^{(i,j)}$ in the directed edge $(i,j)$ transfers information from node $x^{(i)}$ to node $x^{(j)}$. Differentiable Architecture Search (DARTS) [16] relaxes the selection problem of operations as a continuous optimization problem. There is a candidate operations space $\mathcal{O}$, where $o\in\mathcal{O}$ represents a candidate operation, e.g., $skip\_connect,3\times 3\_sep\_conv$, and so on. In DARTS [16], each edge consists of a set of operations from $\mathcal{O}$, and these operations are weighted by architecture parameters $\alpha^{i,j}$, and it can be formulated as:

where $0\leq i<j\leq N-1$. The input nodes of the cell take the output from the previous two cells as input, and the output node contacts all intermediate nodes as the output of the cell. Each intermediate node is be obtained by its predecessors, i.e. $x^{(j)}=\sum_{i<j}o^{(i,j)}\left(x^{(i)}\right)$. Finally, the architecture search of DARTS becomes a bi-level optimization problem:

where $\mathcal{L}_{val}$ and $\mathcal{L}_{\text{train }}$ are validation and training loss, $w$ is the network weights, and $\alpha$ is the architecture weights. According to DARTS[16], the bi-level optimization problem is solved by a first/second-order approximation. When the search process is nearly finished, an optimal substructure is obtained based on the architecture weights $\alpha$, i.e., $o^{(i,j)}=\operatorname{argmax}_{o\in\mathcal{O}}\alpha_{o}^{(i,j)}$.

To eliminate unfairness between operations, we propose operation-level progressive differentiable architecture search, briefly called ”OPP-DARTS”. In other words, we increase operations progressively to expand the search space during the search phase of DARTS, as illustrated in Figure 1, and the OPP-DARTS is detailed in Alg. 1. Firstly, the search phase of DARTS is divided into several stages denoted as $stage\ 1...K$, each stage consists of $T$ epochs, and one operation will be increased into the search space of DARTS every stage.

Then, we will begin increasing operations to enlarge search space. Because the supernet must own an operation with parameters to make itself trainable, we must select an operation with parameters at $stage\ 0$. We first define candidate operations with parameters set as $\mathcal{O}_{pm}$. Furthermore, we select an operation $o$ from candidate operations set $\mathcal{O}_{pm}$. Then, we increase it into the supernet and begin to train the supernet until the next stage.

Afterwards, we will define the candidate operations set as $\mathcal{O}$, and the candidate operations set $\mathcal{O}$ includes all candidate operations except the operation selected in $stage\ 0$ and $skip\_connect$. At the beginning of each stage, we select an operation from candidate operations set $\mathcal{O}$, and increase it into the supernet to train, i.e.,

where $o$ is the operation selected at the stage and $\Omega$ is the search space of the supernet. In this way, these operations increased into the supernet early have the advantage compared to those increased into the supernet lately because these operations that are increased into the supernet early can learn more valuable knowledge than those operations. We can alleviate the unfair natural advantages between operations to make operations compete fairly. When we pick operations at random from the candidate operations set $\mathcal{O}$, it may cause a negative effect if we select operations with natural advantages compared with the others to increase it into the supernet earlier than other operations. Thus, we need to design a criterion to guide us to select operations, and Section III-C shows a criterion to alleviate the problem.

In $stage\ K-1$, we increase $skip\_connect$ into the supernet because skip connection has the most significant natural advantages than other operations. By increasing it into the supernet, at last, we can make other operations offset the natural advantages of skip connection to make operations compete fairly.

By increasing operations progressively, we can make operations compete fairly during the search phase. However, the problem still needs to be solved, i.e., when we select operations from the candidate operations set $\mathcal{O}$ at each stage, we need to decide to select which operation to increase in the supernet. The problem is very critical because if we select operations with natural advantages compared with the others to increase it into the supernet earlier than other operations, it will negatively impact it. Thus, we need to design an applicable criterion to guide us to make operation selection.

[17] indicates that edges share the same optimal feature map in a cell, and it means the edge feature graphs will be closer and closer as the network converges. The feature map of an edge can be represented as Eq. 1. At initialization, if the feature map on an operation is close to the optimal feature map, the architecture parameter $\alpha$ of the operation will become larger at the beginning of the architecture search. It will result in unfairness in initialization. To keep operations competing fairly, we select the operation which can make the supernet gain the largest training loss after the operation is increased into the supernet at the beginning of each stage, called ”operation loss”, i.e.,

where $o$ is the operation that is selected at the stage. When we use ”operation loss” as a criterion to guide us to select an operation at the beginning of each stage, we can make feature maps of operations relatively close to the optimal feature map before they begin to compete with each other. We increase the operation that owns the largest ”operation loss” to train at each stage so that the operation can be more closed to the optimal feature map. Thus, it can alleviate unfairness in initialization. Furthermore, the search process of DARTS can be formalized as follows:

where $\Omega$ is the search space of the supernet. In addition, the feature map of operation is saved in the parameters of operation. Training loss is used to optimize network parameters, i.e., training loss has a maximum correlation with the feature map of operation, so we select training loss instead of validation loss.

We know that skip connection owns a natural advantage because it can make the network coverage faster, and it means that skip connection owns a more significant advantage than other operations, so we increased it into the supernet at the final stage to keep operations compete fairly.

In the paper, our method is proposed to deal with performance collapse in DARTS arising from skip connections aggregation. Our method owns two contributions mainly, i.e., operation-level increasing operations progressively and operation loss. The first contribution is a very significant innovation to alleviate skip connections aggregation. Compared with other works to alleviate performance collapse in DARTS by indicator-based methods (e.g., R-DARTS [10], SDARTS [11]), we alleviate performance collapse by optimizing the search space of DARTS to keep operations compete with each other fairly. Thus the view of our research is very novel. The second contribution is proposed to solve the operation selection problem at the beginning of each stage. If we select operations from candidate operations set at random, operations will suffer from unfairness in initiation, making DARTS work worse. By operation loss, we can alleviate unfairness in the initiation and make DARTS work well. We obtain a good performance (a test error of $2.63\%$) on CIFAR-10 by combining two contributions, and the result indicates that our method makes a remarkable improvement in accuracy on standard DARTS. At the same time, the transferability and robustness of our method are also demonstrated to be better than standard DARTS.

CIFAR-10 is an images dataset that contains $50K$ training images and $10K$ test images. In the next moment, we will introduce our search space. Our search space consists of eight operation, i.e., $max\_pool\_3\times 3,avg\_pool\_3\times 3,zero,sep\_conv\_3\times 3,sep\_conv\_5\times 5,dil\_conv\_3\times 3,dil\_conv\_5\times 5$, it is the same with DARTS. Our training settings are also the same with DARTS, we stack $6$ normal cells and $2$ reduction cells to build a network, and the reduction cells are inserted in a network of $1/3$ and $2/3$, respectively. A cell includes $7$ nodes with $4$ intermediate nodes, every node represents a feature map, and the number of edges in a cell is $14$.

We perform an architecture search for $50$ epochs with a batch size of $64$, and the architecture search is divided into $8$ stages. Each stage includes $2$ epochs. We increase one candidate operation in the search space at the beginning of each stage and train the supernet until the next stage. After the final stage, we train the supernet until the final epoch. During the training, we leverage SGD [19] as an optimizer to optimize model weights $W$, and its initial learning rate is $3\times 10^{-4}$, momentum is $(0.5,0.999)$, weight decay is $10^{-3}$. At the same time, we leverage Adam [20] to optimize architecture weights, and its initial learning rate is $3\times 10^{-4}$, momentum is $(0.5,0.999)$, weight decay is $10^{-3}$. The search phase spends 0.4 GPU day on a single NVIDIA GTX 2080Ti. We ran $5$ times independent search experiments with 5 different seeds, and the best cells were found are illustrated in Figure 2.

The cells found by OPP-DARTS have shown in Figure 2, and then we will stack these cells to evaluate their performance on CIFAR-10. We build a large network with $20$ cells and $36$ initial channels. After building the network, we train the stacked network until $600$ epochs with a batch size of $96$. Furthermore, other training settings are the same with DARTS, such as cutout with length $16$, auxiliary towers with weight $0.4$, and path dropout with a probability of $0.3$.

We compare our result on CIFAR-10 with other methods in Table I, such as Darts- [13], SGAS [27]. Table I shows that our method (OPP-DARTS) improves standard DARTS’ test error from $3.00\%$ to $2.63\%$, with identical search cost ($0.4$ GPU days) on a single NVIDIA GTX 2080Ti. Our method surpasses them a lot compared to other indicator-based variants, such as SDARTS-RS and R-DARTS (L2). The result further demonstrates that the indicator-based method can alleviate skip connections aggregation but prevent DARTS from exploring better architectures.

To verify the transferability of our method, we evaluate architecture on ImageNet by using the best cells searched on CIFAR-10. ILSVRC 2012 [28] is a famous ImageNet dataset, and we leverage it to test our architecture searched on CIFAR-10.

The network configuration is also the same as DARTS, i.e., the network used to evaluate is stacked by $14$ cells, and the number of its initial channels is $48$. The stacked network is trained from scratch for 250 epochs, and its batch size is $256$ during the training phase of the network. An SGD optimizer optimizes the network’s parameters; the optimizer’s initial learning rate is $0.2$, weight decay is $3\times 10^{-5}$, momentum is $0.9$.

Table II shows our evaluation result, and we compare our result with SOTA manual architectures and models obtained through other search methods. The architecture found by OPP-DARTS on CIFAR-10 is superior to the architecture found by standard DARTS in the image classification task, and it means that the transferability of our method is better than standard DARTS.

Because of skip connections aggregation, DARTS will face a performance crash when DARTS searches architectures on three simple search space [10], i.e., S2, S3, S4. S2 is consist of two operations per edge: $(skip\_connect,3\times 3\_sep\_conv)$. S3 is consist of three operations per edge: $(skip\_connect,3\times 3\_sep\_conv,zero)$. S4 is consist of two operations per edge: $(noise,3\times 3\_sep\_conv)$. [10] discovers that when DARTS is used to search architectures on S2, S3, it finds suboptimal architectures, and the performance of architectures is inferior. Even though on S4, DARTS selects excessive harmful $noise$ operations.

To verify the robustness of our methods, we search architectures on these search spaces by OPP-DARTS. Table III shows the results of the OPP-DARTS search in the S2-S4. When searching on S2, the performance of OPP-DARTS (a test error of $2.84\%$) is far further than DARTS. At the same time, we use OPP-DARTS to search architectures on S3 and S4. Table III also shows that the performance of OPP-DARTS on S3 and S4 is better than DARTS. Based on these above experiments, OPP-DARTS is more robust than DARTS.