MSR-DARTS: Minimum Stable Rank of Differentiable Architecture Search

There has been growing interest in NAS since Zoph and Quoc [41] proposed its algorithm. In the early years, EAs and RL were used to optimize network architectures. The algorithm using RL trains a recurrent neural network meta-controller to guide the search process and gradually sample a better architecture. Zoph et al. and Pham et al. [42, 27] first optimized the structure of a small component in an entire network, namely a cell, instead of the entire network structure, then constructed the entire network by stacking the optimized cells. This two-step process reduces search cost. Liu et al., Tang et al. and Real et al. [22, 35, 28] used EAs, which mutate the architecture topologies and evolve towards better performances. DARTS introduces a differentiable NAS pipeline, which relaxes the search space to be continuous and directly uses gradient-based optimization. Many studies [37, 7, 38, 19] followed this approach and achieved remarkable performance with improved efficiency.

In this study, similar to previous ones [37, 7, 38], we used DARTS as a baseline framework. DARTS stacks $L$ cells, each of which is represented as a DAG of an ordered sequence of $N$ nodes, $\{x_{0},x_{1},\dots,x_{N-1}\}$, where each node $x_{i}$ is a feature map and each edge $(i,j)\ (i<j)$ denotes an information flow from node $i$ to node $j$. A set of $K$ candidate operators is denoted as $\mathcal{O}=\{o_{0},o_{1},\dots,o_{K-1}\}$, in which an element $o_{v}$ that includes a learnable parameter $w^{(i,j)}_{v}$ is the $v$-th candidate operator defined in advance (e.g., separable convolution and dilated convolution). Figure 1 left illustrates an example of a DAG with $4$ nodes. An information flow between nodes is a mixed edge, which includes all candidate operators. An architecture parameter $\alpha^{(i,j)}_{v}$, which indicates how suitable $o_{v}$ is for mixed edge $(i,j)$, is introduced as a weight for $o_{v}$. The goal is to optimize $\alpha^{(i,j)}_{v}\ (v=0,\dots,K-1)$. For each $i<j$, the information flow from node $i$ to node $j$, illustrated in the upper middle of Figure 1, is computed as

where $o_{v}(x_{i})$ is the result of applying the input $x_{i}$ to $o_{v}$. An output of node $j$ is a sum over all information flows from its predecessors, that is, $x_{j}=\sum_{i<j}f_{i,j}(x_{i})$. The first two nodes, $x_{0}$ and $x_{1}$, are input nodes to a cell. The output of all the cells equals that of the final node $x_{N-1}$, which is defined as the concatenation of all the intermediate cells, i.e., ${\rm concat}(x_{2},x_{3},\dots,x_{N-2})$.

There are two types of cells introduced in DARTS. One is a normal cell, which maintains spatial resolution, and the other is a reduction cell, which reduces the spatial resolution of feature maps. Note that while DARTS shares the architecture topology among all normal cells, the same is true for reduction cells because it optimizes architecture parameters $\alpha_{{\rm normal}}$ and $\alpha_{{\rm reduce}}$, where $\alpha_{{\rm normal}}$ is shared by all the normal cells and $\alpha_{{\rm reduce}}$ is shared by all the reduction cells.

DARTS has two stages. The first is the search stage, which trains the over-parameterized network consisting of mixed edges in each of which all possible operators are included, and derives a promising discrete architecture in accordance with the architecture parameter $\alpha_{v}^{(i,j)}$ (see Subsec. 3.4 for more details). The second stage is an evaluation stage in which the derived architecture from full-scratch is trained.

A deep network generalizes well even when it has a larger amount of parameters than the sample size. Generalization bounds represent the upper bound of the generalization error. We can guarantee that a model with small training error can have a high generalization performance if the generalization error (difference between training error and expected error) can be evaluated properly and has a small upper bound. There are several metrics to represent generalization error bounds such as VC-dimension [36, 14], PAC-Bayes theory [25, 11], norm based analysis [3, 26, 12], and the compression based approach [2, 4, 32]. The compression based approach has recently attracted much attention because it gives tighter generalization error bounds for deep neural networks. For example, Arora et al. [2] used the low rank property of weight matrices to compress neural networks based on the fact that a matrix with a lower stable rank is more robust to noise thus generalizes well. Suzuki et al. [32] experimentally confirmed that most networks have near low rank weight matrices after training, where a near low rank matrix is defined as a matrix in which a small number of singular values are significantly large while the other singular values are close to zero. This near low rank property is used to derive generalization bounds.

While DARTS and many related methods [37, 7, 38] search for architectures by jointly training the architecture parameters $\alpha$ and weights of neural networks $w$ (e.g., the parameters of the convolutional operator) in an alternating manner ($\alpha^{(i,j)}_{v}$ is denoted as $\alpha$ and $w^{(i,j)}_{v}$ is denoted as $w$ for simplicity), Shu et al. [31] reported that these methods tend to lead to a fast converged architecture during the search stage rather than well generalized models. This is because $\alpha$ is updated on the basis of $w$, which is not fully converged rather than well trained $w$, which is harmful especially in the early epochs. This means that there is room to search for a model with lower error rate in the search space. MSR-DARTS addresses this issue. It fixes $\alpha$ to $1$, hence optimizes only $w$. In the search stage, instead of Eq. (1), the information flow from node $i$ to node $j$ with MSR-DARTS illustrated in Figure 1 middle bottom, is defined as

The other process is the same as those defined in Subsec. 2.2.

With MSR-DARTS, we assume that each candidate operator $o_{v}\in\mathcal{O}$ consists of several convolutional layers. Let $c^{v}_{p}$ and $c^{v}_{{\rm fin}}$ be the $p$-th and last convolutional layers in $o_{v}$, respectively. Note that the notation of node $(i,j)$ is omitted for simplicity in $c^{v}_{p}$ and $c^{v}_{{\rm fin}}$. Regarding convolutional computation as matrix calculation [30], the stable rank of convolution $c$ is then denoted as $R(c)=\frac{\|c\|^{2}_{F}}{\|c\|^{2}_{2}}$, where $\|\cdot\|_{F}$ denotes the Frobenius norm and $\|\cdot\|_{2}$ denotes the spectral norm. A stable rank is often used as a surrogate for a rank [2].

Then we select the best operator from $\mathcal{O}$ for each edge after training of an over-parameterized network in the search stage. We use the relation between network generalization ability and singular values proposed by Arora et al. [2]. They reported that a well-generalized network consists of noise-robust convolutions that have low stable ranks. Noise sensitivity $\psi_{\mathcal{N}}(c,x)$ is defined as

where $c$ is a mapping from real-valued vectors to real-valued vectors (e.g., convolutional computation represented by a matrix), $x$ is a vector to be multiplied (i.e., input for a convolutional layer), $\mathcal{N}$ is a noise distribution, $\mathbb{E}$ is an expectation value, and $\|\cdot\|$ is the Euclidean norm. Low noise sensitivity indicates that the convolution matrix has a near low rank property (i.e., a low stable rank) because the signal $x$ is correctly carried whereas noise $\eta$ is attenuated. Note that $\psi_{\mathcal{N}}(c,x)$ is at least its stable rank when noise is generated from standard normal distribution, i.e., $\eta\sim\mathcal{N}(0,I)$. For more details, refer to the paper by Arora et al. [2].

We assume that an operator that generalizes better has lower noise sensitivity, i.e., a lower stable rank (experimentally shown in Appendix B). We further assume that the last convolution $c^{v}_{{\rm fin}}$ is the most relevant to the output of $o_{v}$, thus use the stable rank of $c^{v}_{{\rm fin}}$ (i.e., $R(c^{v}_{{\rm fin}}))$ only. The operator that has the lowest $R(c^{v}_{{\rm fin}})$ is selected to yield the discrete architecture.

DARTS defines an operator set with eight operators. That is, 3$\times$3 and 5$\times$5 separable convolutions, 3$\times$3 and 5$\times$5 dilated separable convolutions, 3$\times$3 max pooling, 3$\times$3 average pooling, identity, and zero. Our operator set is the subset of the search space of DARTS, i.e., 3$\times$3 and 5$\times$5 separable convolutions and 3$\times$3 and 5$\times$5 dilated separable convolutions. As described in Subsec. 3.1, we assume that all candidate operators $o_{v}\in\mathcal{O}$ consist of limited convolutional layers, where 3$\times$3 max pooling, 3$\times$3 average pooling, identity, and zero, which are not convolutional calculations, are excluded. As with DARTS, we use the ReLU-Conv-BN order for convolutional operators, in which each separable convolution is always applied twice.

We assume that with MSR-DARTS, all operators in a search space are trained correctly in the search stage. However, previous studies [32, 13, 17] reported that deep learning tends to produce a simpler model than its full expression ability when we use regularization such as $L_{1}$ regularization. More precisely, it has been experimentally shown that a trained network tends to have near low rank weight matrices, in which only a few singular values are large and others are close to zero. Therefore, in each mixed edge of an over-parameterized network with MSR-DARTS, some operators can be redundant because their singular values can be all close to zero. To train each operator stably, we apply the spectral norm adjustment technique introduced by Behrmann et al. [5] to all convolutional operators in candidate operators, that is,

where $C$ is a constant value to be set (Figure 1 right). We estimate the spectral norm of $c^{v}_{p}$ by carrying out power-iteration (see Appendix A for more details), which yields an under-estimate $\tilde{\sigma}_{1}(c^{v}_{p})\leq\|c^{v}_{p}\|_{2}$, where $\sigma_{q}(c^{v}_{p})$ denotes the $q$-th largest singular value of $c^{v}_{p}$. Similar to the above study, using this estimate, each convolution in candidate operator $c^{v}_{p}$ is normalized as

Note that spectral norm adjustment of each convolution is conducted before forward propagation. We used $C=1$ in our experiments.

After training of the over-parameterized network, a discrete architecture is derived by selecting the topology and operator for each intermediate node. With DARTS and its derivations, the topology is selected by retaining two of the strongest precedent edges for each intermediate node, where the strength of an edge from node $i$ to node $j$, denoted as $S_{i,j}$, is defined as

In each edge, the operator with the largest $\alpha_{v}$ is selected. However, as described in Subsec. 3.1, MSR-DARTS uses a fixed value for $\alpha_{v}$. We use the stable rank of the last convolution $R(c^{v}_{\rm fin})$ in each $o_{v}$ to determine the topology. First, for normal and reduction cells, the mixed edge between node $i$ and node $j$ is replaced with the best operator $(o^{\ast}_{\mathcal{T}})_{i,j}$, defined by

We explicitly notate the edge indices $i,j$ in convolution $c$, $\mathcal{T}=\{{\rm normal},{\rm reduce}\}$ denotes the type of cells and $\overline{R}_{\mathcal{T}}(\cdot)$ denotes the average $R(\cdot)$ of all the cells belonging to cell type $\mathcal{T}$. Similar to Eq. (7), the strength of an edge from node $i$ to node $j$ of cell type $\mathcal{T}$ with MSR-DARTS is defined by

We use Eq. (8) instead of Eq. (6) to derive topology. Note that the operator $o_{v}\in\mathcal{O}$, which has lower $R(c^{v}_{\rm fin})$ is considered a better operator in terms of generalization ability (see Subsec. 3.1).

As with DARTS, each intermediate node retains the connections from the two strongest precedent nodes, denoted as $i^{\ast}_{1}$ and $i^{\ast}_{2}$, with Eq. (8), that is,

Note that the cell-type notation $\mathcal{T}$ is omitted from Eq. (3.4) for simplicity.

In summary, a discrete architecture is derived from the over-parameterized network after training, where each mixed edge is replaced with the best operator $(o^{\ast}_{\mathcal{T}})_{i,j}$ in accordance with Eq. (7). The two strongest precedent connections from node $i^{\ast}_{1}$ and $i^{\ast}_{2}$ are then preserved in each node in accordance with Eq. (8).

Similar to several previous studies [23, 7, 38], we conducted experiments on the well-known image classification datasets CIFAR-10 [18] and ImageNet [9]. CIFAR-10 consists of 50K training images and 10K testing images. All images have a fixed size of 32$\times$32 and equally distributed over ten classes. ImageNet was obtained from the Imagenet Large Scale Visual Recognition Challenge 2012 [29] and contains 1K object classes, 1.28M training images, and 50K validation images. We follow the general setting in which the input image size is $224\times 224$.

First, we confirmed the effectiveness of the proposed method using MSR through a simple toy experiment using CIFAR-10. In this experiment, MSR-DARTS and DARTS [23] were compared, both under the same experimental conditions. The results indicate that MSR-DARTS is superior to DARTS.

In the search stage, following DARTS, the architecture was conducted on a network with $L=8$ cells. Each convolutional cell consists of $N=7$ nodes. The input nodes $x_{0}$ and $x_{1}$ were equal to the output of the last two preceding cells, respectively. The output node was $x_{6}$, which is the concatenation of all the intermediate nodes. Reduction cells were inserted at 1/3 and 2/3 the total depth of the network to reduce the spatial resolution of feature maps. All other cells were normal cells that maintain spatial resolution. Note that while DARTS and related methods [37, 38] share the architecture topology among all normal cells, the same is true for reduction cells, because they optimize architecture parameters $(\alpha_{{\rm normal}},\alpha_{{\rm reduce}})$, where $\alpha_{{\rm normal}}$ is shared by all the normal cells and $\alpha_{{\rm reduce}}$ is shared by all the reduction cells (see Subsec. 2.2). MSR-DARTS also optimizes two types of cell structures, i.e., normal and reduction cell, but each cell is optimized using MSR (see Subsec. 3.1) because learnable architecture parameters are not optimized with MSR-DARTS.

We evaluated the MSR-DARTS with $20$ cells (18 normal cells and 2 reduction cells) in the evaluation stage to compare other state-of-the-art methods. We used the same cell structure optimized in the toy experiment. The rest of the experimental settings were exactly the same as with DARTS. Table 2 compares the image-classification performance of MSR-DARTS with those of the other methods. MSR-DARTS achieved $2.54\%$ test error, which is better than 2nd order DARTS. It outperformed PC-DARTS [38] and was competitive with Fair DARTS [8] in terms of test-error rate. Our architecture search finished in $0.3$ GPU-days, which is faster than 2nd order DARTS ($1.0$ GPU-day) and Fair DARTS ($0.4$ GPU-days). Note that MSR-DARTS generated the optimal model with $4.0$M parameters, which is a slightly larger number of parameters compared with the models of the other methods. This is because of search space $\mathcal{O}_{\rm MSR}$, which includes the convolutional operator only. This means that the operator with few parameters, such as pooling or identity (skip connection), is not selected.

Following DARTS and its derivations, we evaluated the architecture with $L=14$ cells in the architecture evaluation stage. We used the normal and reduction cells, which were optimized with CIFAR-10 (see Subsec. 4.2). The experimental settings mostly followed those of DARTS. The network was trained $250$ epochs with a batch size $128$. The initial number of channels was set to be $48$. We used momentum SGD to optimize the weights, with an initial learning rate $0.1$ (annealed down following a cosine schedule), momentum of $0.9$, and weight decay of $3\times 10^{-4}$. For additional enhancements, label smoothing and an auxiliary loss tower were used during the training. We used $32$ TITAN V100 GPUs, applied learning warm-up for the first $10$ epochs (increase linearly with each batch), and used Horovod for distributed training.

The results are summarized in Table 3. The architecture found with MSR-DARTS using CIFAR-10 reported a top-1 error rate of $23.9\%$ and top-5 error rate of $7.3\%$, which outperforms the top-1 error rate of $26.7\%$ and top-5 error rate of $8.7\%$ reported with DARTS. In the comparison with other DARTS-based methods using CIFAR-10 for architecture search, MSR-DARTS had $0.5\%$ higher top-1 accuracy than P-DARTS, $1.2\%$ higher than PC-DARTS, $1.0\%$ higher than Fair DARTS, and $0.2\%$ higher than PR-DARTS. It was also competitive with $23.9\%$ of DARTS+, which searches for an optimal architecture with CIFAR-100. Regarding search cost, MSR-DARTS required only $0.3$ GPU-days, which is 3 times faster than the 2nd order DARTS and slightly faster or competitive with Fair DARTS and P-DARTS. Due to the fact that the search space includes only limited types of convolutional operators (see Subsec. 3.2), MSR-DARTS had a relatively large number of parameters and multiply-add operations.

In this subsection, we compare the optimized architectures between DARTS and MSR-DARTS qualitatively. Figure 4 illustrates the cell structures found with DARTS((a) normal cell, (b) reduction cell) and with MSR-DARTS ((c) normal cell, (d) reduction cell).

As described in a previous paper [31], the depth of a cell structure is defined as the number of connections along the longest path from input node to output node. The width of a cell structure is defined as the total width of intermediate nodes that are connected to the input nodes. In particular, the normal cell found with DARTS (Figure 4 (a)) had a depth of $3$ and width of $3.5$.

The normal cell found by MSR-DARTS, however, had a depth of $4$ and width of $2.5$, a deeper and narrower structure. As discussed in the above paper [31], DARTS tends to select shallow and wide cells because is optimizes two parameter sets (weight $w$ and architecture parameter $\alpha$) in an alternating manner. Each candidate architecture is not evaluated based on the generalization performance at convergence during architecture search; thus architectures with faster convergence rates tend to be selected. In contrast, the architecture parameters are fixed and only $w$ are optimized with MSR-DARTS. Thus, MSR-DARTS can evaluate each architecture more correctly at convergence and yield deeper and narrower cells, which is a well generalized architecture. Note that the scheme that penalizes shallower cells is used with PR-DARTS [40]. However, PR-DARTS has many more hyper-parameters than the original DARTS, which are difficult to adjust. On the other hand, MSR-DARTS does not require any hyper-parameters to deepen a cell structure, making it easy to optimize. All the intermediate nodes, except the first intermediate node (illustrated as $0$ in Figure 4) in the normal cell found with MSR-DARTS had both a connection from an input node and a connection from another intermediate node. Each intermediate node can handle both the input features of the cell and well-processed features inside the cell. This structure may improve of the accuracy.

The reduction cell found with MSR-DARTS had a shallow and wide cell structure in contrast to the normal cell. The reason MSR-DARTS finds these structures may be that the reduction cell should summarize the information to reduce the spatial dimension, thus requiring more information from the input features than the normal cell. In addition, it seems that the reduction cell found with MSR-DARTS has small receptive fields (e.g., “3x3 separable convolution” and “5x5 separable convolution”) for the output of the before last cell and relatively large receptive fields (e.g., “5x5 separable convolution” and “3x3 dilated convolution”) for the output of the before cell. This enables the efficient aggregation of information by applying a large receptive field to the latest information.

This work was supported by JST CREST JPMJCR1687 and NEDO JPNP18002. TS was partially supported by MEXT Kakenhi (15H05707, 18K19793 and 18H03201), and Japan Digital Design.