FTSO: Effective NAS via First Topology Second Operator
Authors: Likang Wang
Lei Chen
Venue:  (2021)
Keywords: Neural Architecture Search
DARTS

Abstract: Existing one-shot neural architecture search (NAS) methods generally contain a giant supernet, which leads to heavy computational cost. Our method, named FTSO, separates the whole architecture search into two sub-steps. In the first step, we only search for the topology, and in the second step, we only search for the operators. FTSO not only reduces NAS’s search time from days to 0.68 seconds, but also significantly improves the accuracy. Specifically, our experiments on ImageNet show that within merely 18 seconds, FTSO can achieve 76.4% testing accuracy, 1.5% higher than the baseline, PC-DARTS. In addition, FTSO can reach 97.77% testing accuracy, 0.27% higher than the baseline, with 99.8% of search time saved on CIFAR10.

Under review as a conference paper at ICLR 2021
FTSO: EFFECTIVE NAS VIA FIRST TOPOLOGY SECOND OPERATOR
Anonymous authors Paper under double-blind review
ABSTRACT
Existing one-shot neural architecture search (NAS) methods generally contain a giant super-net, which leads heavy computational cost. Our method, named FTSO, separates the whole architecture search into two sub-steps. In the first step. we only search for the topology, and in the second step, we only search for the operators. FTSO not only reduces NAS's search time from days to 0.68 seconds, but also significantly improves the aceuracy. Specifically, our experiments on ImageNet show that within merely 18 seconds, FTSO can achieve 76.4% testing accuracy, 1.5% higher than the baseline, PC-DARTS. In addition, FTSO can reach 97.77% testing accuracy, 0.27% higher than the baseline, with 99.8% of search time saved on CIFAR1O.
INTRODUCTION
Since the great success of AlexNet (Krizhevsky et al., 2012) in image classification, most modern machine learning models have been developed based on deep neural networks. For neural networks, their performance is greatly determined by the architectures. Thus, in the past decade, a tremendous amount of work (Simonyan & Zisserman 2013) Szegedy et al., 2015 5, He et al., 2016) has been done to investigate proper network architecture design. However, as the network size has grown larger and larger, it has gradually become unaffordable to manually search for better network architectures via trial and error due to the expensive time and resource overhead. To ease this problem, a new technique called neural architecture search (NAS) was introduced, which allows computers to search for better network architectures automatically instead of relying on human experts..
Early-prop proposed reinforcement learning- bbssdd based NAS methods (Zoph & Le. 2017 Baker et al. 2017 Zoph et 20188) typically have an from the search space. Although these algorithms can provide promising accuracy, their computation cost is usually unaffordable, e.g., 1800 GPU-days are required for NASNet.
controller to sample candidate network architectures
To ease the search efficiency problem, one-shot approaches (Pham et al.) 2018 Cai et al., 2019 Liu et al., (019) with parameter sharing were proposed. These methods first create a huge di- rected acyclic graph (DAG) super-net, containing the whole search space. Then, the kernel weights are shared among all the sampled architectures via the super-net. This strategy makes it possible to measure the candidate architecture's performance without repeatedly retraining from scratch. However, these algorithms suffer from the super-nets' computational overheads. This problem is particularly severe for differentiable models (Liu et al. 2019 Xu el. 2020).
Limited by current NAS algorithms' inefficiency, it is rather challenging to find satisfying network architectures on large-scale datasets and high-level tasks. For instance, current speed- ppeed-oreented NAS approaches generally require days to accomplish one search trial on ImageNet, e.g., 8.3 GPU-days for ProxylessNAS (Cai et al.] (219)) and 3.8 GPU-days for PC-DARTS (Xu al.) 2020). There- fore.we argue that it is essential to propose new well-defined search space, which is only expressive enough to cover the most powerful architectures, but also compact enough to filter out the poor architectures.
Motivated by Shu et al. (220)). who demonstrated that randomly replacing operators in a found architecture does not harm the accuracy much, believe that it could not only bring reduction to the testing accuracy but also significantly benefit the search efficiency if we omit the influence of operators and cluster architectures according to the topology. Thus, in this paper, we propose

---

Under review as a conference paper at ICLR 2021
separately search for the network topology and the operators. We name this new method Effective NAS via First Topology Second Operator (FTSO).
In this paper, we mathematically prove that FTSO reduces the required parameters by 5.3 10? and decreases the FLOPs per iteration by x 10 Besides, FTSO significantly promotes the accuracy compared to the baseline by greatly shrinking the search space, reducing the operators complexity in magnitude and lowering the required searching period from 50 epochs to one iteration. What's more, the Matthew effect eased.
Furthermore, we empirically show that FTSO is superior in both efficiency and effectiveness, ac- complishing the whole architecture search in 0.68 seconds. On ImageNet, FTSO achieve 76.4% testing accuracy. 1.5% higher than the baseline, within merely 18 seconds. More importantly, when we only search for one iteration, FTSO can reach 75.64% testing accuracy, 0. 0.74% higher than the baseline in just 0.68 seconds. Besides, if we allow FTSO to search for 19 minutes, 76.42% Top1 and 93. 13.2% Top5 testing accuracy can be obtained. In addition, FTSO can reach 97. 77.77% testing accuracy, 0.27% higher than the baseline, with 99.8% of search time saved CIFARIO. Although in this paper we have only implemented FTSO within continuous search space, we illustrate in Section 5 that FTSO can be seamlessly transferred to other NAS algorithms.
2 RELATED WORK
In general, existing NAS algorithms can be divided into three categories, namely, reinforcement learning-based revolution- based and differentiable. Early-proposed reinforcement learning-base methods (Zoph & Le 2017, Zoph et al., 2018) generally suffer from high computational cost and low-efficiency sampling. Instead of sampling a discrete architecture and then evaluating it, DARTS (Liu et al.] 2019) treats the whole search space as continuous super-net. It assigns every operator a real number weight and treats every node as the linear combination of all its transformed predecessors. To be specific, DARTS's s search space is directed acyclic graph (DAG) containing two input nodes inherited from previous cells, four intermediate nodes and one output node. Each node denotes one latent representation and each edge denotes an operator. Every intermediate node exp Xj is calculated from all its predecessors x,, i.e., X; -iiej Enco Ev' expo?y o(x:), where O
denotes the collection of all candidate operators, af,j denotes the weight for operator from node i to j. This strategy allows DARTS to directly use gradients to optimize the whole super-net. After the super-net converges, DARTS only retains the operators with the largest weights. In this way, the final discrete architecture is derived. The main defect of DARTS is that needs maintain and do all calculations giant super-net, which inevitably leads to heavy computational overheads and over-fithe over-fitting.
Proposed to relieve the computational overhead of DARTS, DARTS-ES (Zela et al. 2020 reduces the number of searching epochs via early stopping, according to the Hessian matrix's 's max eigen- value. PC-DARTS (Xu et al. 2020) decreases the FLOPs per iteration by only calculating propor- tion of the input channels and retaining the remainder unchanged, and normalizes the edge weights to stabilize the search. To be specific, in PC-DARTS, every intermediate node X; is computed from exp
all its predecessors x,, i.e., Xj = Eies Exerpp rx,,,, f (x;)),,, where Bi., describes the input node i's importance the node j. and fij is the weighted sum of all the candidate operators' outputs ei
between node and j. Specifically, fr., (x;, St.s) = E.Eo
Eveo " (S x.) + (1 - -St,) * x
where Sr denotes binary vector, in which only 1/K elements are 1.
3 FTSO: EFFECTIVE NAS VIA FIRST TOPOLOGY SECOND OPERATOR
Existing NAS approaches generally suffer from the heavy computational overhead and the unsat- isfying testing accuracy leaded by the huge search space. Such problems especially stern in one-shot and differentiable methods because, these algorithms need to maintain and even do all the calculations directly on the search space.
To ease such problems, it is of great demand to investigate the correlations among different archi- tectures and shrink the search space according these prior knowledge. We notice that there
2

---

Under review as a conference paper at ICLR 2021
an important observation in Shu et al. (2020) that randomly substituting the operators does not observably influence the testing accuracy in a found architecture. Therefore, it would be a great inspiration that we could cluster the architectures according to their connection topologies. To be specific, suppose we have found an architecture only containing the simplest operators achieves high accuracy the testing set, if we replace all the skip connections in this architecture with powerful operators, the converted architecture can also perform well on the testing set with high confidence.
Form DAG only containigg the lighteel operato: namely, sklpcconnccoon
Turn edgees weights vis gradiente. For every node, only rotain the inpul edge with highest weight
The pruned graph
ShUp
Q4
Smaleer
Conv
Poot
The archtlccturo
edgeo wwights every the highest
wigeu graph operators
Figure I: The main structure of FTSO.
Thus, in this paper, we first propose to find the effective network topology with simple operators and then we fix the topology, and search for the most suitable operators for the given topology. In this way, the testing accuracy can still be guaranteed, while the search space is shrunk in magnitude. We name this new NAS algorithm Effective NAS via First Topology Second Operator (FTSO).
As shown in Figure D we inherit the differentiable framework of PC-DARTS, and divide the archi- tecture search into two phases. We name these two phases topology search and operator search, and respectively. In the first phase, we form a super-
illustrate how they work in Algorithm T and 2 net only containing the simplest operator, skip connection. Because the skip connection operator contains no kernel weights, we only need to optimize the architecture parameters $r.j. denoting the node i's importance to the node j. In fact, as shown 3able the max pooling operator also brings satisfying results for the topology search. There are two reasons why we use skip connection. The first reason is that the skip connection operator not only requires zero parameter, but also produces the minimum computational cost. The second reason is that max pooling may lead to the loss of useful information if the network deep. Furthermore, as the the only difference between our topol- ogy search and the vanilla DARTS is the number of candidate operators, the pruned architecture's connectivity can be guaranteed.
After the topology search, for every intermediate node j. we only retain its connections to its pre- decessors i" with the highest two fi,, similar to DARTS and PC-DARTS. In the second phase, we search for the operators suitable for the pruned topology with two strategies. One replaces each operator in the pruned topology with a mix-operator fi.j. where ft, is the linear combination of all the candidate operators with weight of,,, denoting the importance of the operator o between the node and j. After that, we optimize the architecture parameters, of Br, and the kernel weights wi, alternatively. After the super-net converges, we only retain one operator o* with the highest af for every two connected nodes i and j. The other is to directly replace all the operators in the pruned topology with one single operator owning the highest model capacity, e-g., a convolution operator. In this paper, we take the second strategy as the default configuration because it is much more ef- ficient and avoid over-fitting. The final architecture outputted by the first strategy is only a small part of the super-net. If the sub-graph can generalize perfectly on the testing set, the super-net must over-fit. Thus, under this circumstance, the optimum super-net on training set is not the optimum one testing set, and is the sub-graph. PC-DARTS has mentioned this issue and reduced the size of the super-ner net via only computing partial input channels. While in the second strategy, since super-net is adopted and all the simple operators in the sub-graph are replaced with powerful
3

---

Under review as a conference paper at ICLR 2021
operators, the final architecture's 's model capacity gets promoted. Additional empirical comparisons between these two strategies can be found in Section 4.4
Algorithm 1:
topology search
Input:
set of nodes: 7
Output: the pruned architecture: Ap
Create an directed edge ei. with weight B.g between each pair of nodes n, and nj (1 f): Assign each edge Gi,j a skip connection operator Oz,j with kernel weights Wi.s while still in the first epoch do
Norward-propageet following nj =Eics Bkjs
Update architecture 33 by descending VeLaa B);
Update weights w by descending V forrrann (w, 3);
foreach node n; E Ap do Tý <- the second largest Bidj foreach node n, do if Big < T then Prune edge Cijj
11
12 Derive the pruned architecture Ap.
Algorithm 2: operator search
Input:
the pruned architecture produced by the topology search: Ap
Output: the found architecture: A
replace with convolutions then
Replace all the retained operators o, in Ap with convolutions;
else
Assign each node ny + Eies Eoco Eveoo expay o o (n.:):
exp
while not converged do
Update architecture by descending Va Lraa (w, a)); Update weights w by descending V Ctrain (w, O);
foreach edge ei E Ap do Assign edge et, the operator o' E O with the highest of
10 Derive the found architecture A + Ap.
In DARTS, the network topology and operators are jointly searched, which makes both the size and the computational cost of the super-net extremely high. We use n to denote the number of nodes, p denote the number of candidate operators. Since we have two input nodes, one output node and n - 3 intermediate nodes, the super-net contains totally [n² - 3n) edges. At the same time, every edge keeps p operators, thus, the total number of operators in DARTS is [n² 3n)p. By comparison, there are only (n(nn33 operations in topology search, and 2(n 3)p operations in our operator search. This is because in the topology search, every edge contains only one operator; and in the topology search, every intermediate node only connects to two predecessors. Since is usually close to FTSO reduces the number of operations from O to O
In addition the reduction on the number of operations, FTSO also dramatically decreases the internal cost of the operations because, during the topology search, all the powerful operators are replaced with the simple operators. To be specific, a vanilla convolutional operator needs k²,,,, Wont Cout FLOPs and (k2 + 1)Cout parameters, where k is the kernel size, Oin the input tensor's channel number and Hout, Wout- and Cout are the output tensor's height, width and channel number respectively. By comparison, skip connection operator needs 0 parameters and FLOPs. For simplicity, assume all the candidate operators are convolutions. Since DARTS has p - 3) edges, it needs to compute ?pn(( - 3) convolutions and fpm(n- - 3) tensor summations. Because each tensor summation consumes Hi, W Ci. FLOPS, DARTS requires totally 2opk2nnn- Ho C),,, Hourh Wout Cowe (pn(nn (3)-3 W Cout Hu) W Wowe Cow (k2C,n +1) FLOPs
Co
4

---

Under review as a conference paper at ICLR 2021
and In(n C)p(k2Cin + oou parameters. While in FTSO, if we first search for the topology and then directly substituting the operators, only in(n 3) tensor summation need to be calcu- lated. Thus, the total number of FLOPs and parameters of FTSO are 2n(n 3) Wi in and in(n - 3) respectively. As a typical configuration, let k = 5, Can = Cott = 512, n = 7,
p 8. Then, our algorithm requires only +1J = 1.9 x 10 times the parameters and
p( +1) = 9.8 10 times the forward-propagation FLOPs per iteration compared to those of DARTS.
FTSO's huge reduction on the parameter numbers provides large amount of benefits. As men- tioned above, it allows the algorithm to converge in only a few iterations and prevent over-fitting. This is because when extracting the discrete sub-graph from the super-net, many architecture param- eters are set to be O. The introduced disturbance impacts more on the over- ever-fitting super-nets nets since they prefer sharper local minimums. Furthermore, it avoids the Matthew's 's effect. Each architecture has only one iteration to tune its kemee weights in DARTS. However, within one iteration, only the operators with few parameters can converge and thus, the simpler operators outperform the power- ful ones in the super-net, then obtain larger gradients to enlarge their advantages, In this way, the found architectures tend to only contain the simplest operators and perform poorly on both training and testing set. Since FTSO only contains one operator with 0 parameter, the Matthew's effect is eliminated.
TAS
DRD QROLANTE_
cres
2ep 000 ALL
(a)
(b)
(d)
(I)
(h)
Figure 2: FTSO's found architectures. (a) and (b); Normal and reduction cells found on CIFARIO
after one epoch's search: (c) and (d) Normal and reduction cells found on the entire ImageNet after
one epoch's 's search: (e) and ff) Normal and reduction cells found on CIFAR10, where we adopt the
operator search, and use the 3 x 3 separable convolution to search for the topology; [g] FTSO's
cell found on NATS-Bench; h DARTS's cell found on NATS-
4 EXPERIMENTS
Our search algorithm is evaluated on the three most widely-used datasets NAS papers, namely,
CIFAR 10 et al. 2009) and maageNe((Russaoossk et al., 2015) and NATS- AXTS-Bench(Dong
ctt al. 2020). Following DARTS, our search space contains total eight candidate operators: 3 x and 5 x 5 separable convolutions, 3 3 and 5 x 5 dilated separable convolutions. 3 x 3 max and average pooling, skip connection (i.e., output = imput) and zero (i.e., output = O). When search- ing for the topology, we pick only one operator from the candidate set. As mentioned in Section B we have two strategies to determine the operators. including the one based on gradients and the one we focus more the second configuration. In Section
is directly replacing. In Section 4.1 and 4.2
5

---

Under review as a conference paper at ICLR 2021
have comprehensive comparison these two strategies. All detailed configurations shown in Table 4 in Appendix A.I In addition, most of our experiments only search for one epoch iteration because of the benefits of FTSO's huge reduction on the parameter numbers. For more experimental supports, please refer to Section [4.4 Note that it is almost impossible for the iteration because their super-nets contain a large amount of parameters, which require a long period to tune.
existing models obtain satisfying results via only searching for epoch
4.1 RESULTS ON CIFARIO
We compare FTSO to existing state-of-the-art NAS methods in Table [ In the experiment, we 3 separable
only search for the topology with skip-connections and then replace them all with convolutions. The reason that we do not adopt 5 x separable convolutions is that the pre-processed input images do not have enough resolutions, and the network is rather deep. After a few layers, convolution's 's receptive field has been larger than the whole image. At that time, larger convolutional kernels may not bring benefits. Instead, the extra parameters brought by the larger kernel size may lead to over-fitting. On the other hand, suppose both the image's 's resolution and the dataset's scale are big enough and the evaluation period is adequate, the x 5 separable convolution might be better choice. The found architecture after one epoch's 's search is shown in Figure 2 Because FTSO contains only a few trainable parameters, it can even achieve comparable accuracy to PC- DARTS with only an one-time gradient update. Under this configuration, merely 0.68 seconds are required and 99. 99.993% of the search time is saved. In addition, as shown in Table 3 when the topology is searched with powerful operators for a long period, additional operator search usually helps. However, when we search for the topology with simple operators for short period, omitting the operator search may lead to better results. This is because with simple operators and very few updates, the found topology can already generalize quite well.
Table Comparison with existing state cate-of-the of-the-art art image classification architectures
CIFAR
ImageNet Err ())
Search Cost
Architecture
Err( %
(GPU-days)
600
1200
Top1
Top5
CIFAR
LN.
NASNet-A Zoph et al. 2018
2.65
26.0
8.4
1800
AmoebaNet Real al. 2019
2.55
24.3
7.6
3150
PNAS et al. 2018
3.41
25.8
8.1
225
ENAS Pham et al. 2018
2.89
0.5
DARTS (2nd) (Liu al.
2019)
2.76
26.7
8.7
1
4.0
SNAS (Xie et al.
2019
2.85
27.3
9.2
1.5
NrS
Cai et al.
2019
2.08
24.9
7.5
4.0
8.3
P-DARTS Chen et al.
2019
2.50
24.4
7.4
0.3
BayesNAS (Zhou et 2019
2.81
26.5
8.9
0.2
PC-DARTS(CIF.) Xu et al. PC-DARTS(LNN.)
2020
2.57
2.50
25.1
7.8
0.1
Xu et al.
2020
24.2
7.3
3.8
FTSO (CIFARIO epoch)
2.48
2.23
23.60
7.01
2 10
FTSO (CIFARIO iteration)*
2.68
2.54
24.36
7.27
7.87 x 10
FTSO (Full ImageNet + lepoch)
2.35
2.26
23.58
6.80
0.01
When testing CIFARIO, these models adopt cut-out. These models are directly searched on ImageNet.
4.2 RESULTS ON IMAGENET
On ImageNet, we use similar configurations to those on CIFARIO, When searching, we have two configurations. The detailed configurations shown in Appendix A.I Our experiments in Table show that FTSO is significantly superior to existing methods in both efficiency and effectiveness. The found architectures after epoch's search CIFARIO and the entire ImageNet are shown

---

Under review as a conference paper at ICLR 2021
in Figure 2 It is surprising that the best architecture found on ImageNet is the shallowest and widest onc. Compared to the much more "reasonable" architectures shown in Figure 2 and 2 which was found with the topology search only containing 3 x 3 separable convolutions and an additional operator search on CIFARIO, 10, the "abnormal" architecture, containing the same amount of FLOPs and parameters, whole model is stacked with many cells. If the depth of each cell is too high, it leads to a very deep neural network. At that time, because all the operators in our found architecture are convolutions, we cannot use skip connections to facilitate gradients' propagation in ResNet's 'ss manner. In this way, both the vanishing and explosion of gradients may prevent the deeper models from higher performance.
achieve 0.78% higher testing accuracy. We think this is because the
4.3 RESULTS ON NATS-BENCH
In the search space of HATS-Bench, there are one input node, three intermediate nodes and one output node, and each intermediate node connects to all its predecessors. Here we implement FTSO based on DARTS instead of PC-DARTS, and we compare FTSO's performance to other NAS algo- rithms in Table It is shown that FTSO dominates DARTS our analysis in Section 3 the architectures found by DARTS tend to only contain simple operators, thus cannot achieve satisfying accuracy. For example, when searching on CIFAR1O, R10, the architecture found by DARTS is full of skip connections as shown in Figure ((h) By comparison, as shown in the architecture found by FTSO much more powerful.
all configurations. Coinciding with
Figure 2gg
Table Comparison with existing state-of-the-ard image classification architectures
Search on CIFAR10
Search CIFAR100
Search ImageNet
Architecture
CF10
CF100
L.N.
CF10
CF100
L.N.
CF10
CF100
L.N.
DARTS (Ist)
54.30
15.61
16.32
86.57
58.13
28.50
89.58
63.89
33.77
DARTS (2nd)
86.88
58.61
28.91
91.96
67.27
39.47
84.64
55.15
26.06
FTSO
93.98
70.22
45.57
93.98
70.22
45.57
93.98
70.22
45.57
1 This means that within NATS-Bench's search space, when we use the st order DARTS to search for architectures CIFARIO 10 dataset, the found architecture can achieve 16.32% testing accuracy on ImageNet.
CF10 means testing accuracy (%) on CIFARIO; CF100 means testing accuracy (%) on CI- FAR100; INN. means testing accuracy (%) on ImageNet.
4.4 ABLATION STUDY
In terms of topology-only search, one epoch is just enough, thanks to the many fewer kernel weights contained in FTSO, and more search epochs bring obvious disadvantages because of over-fitting. Since one epoch performs better than more epochs, it raises the question whether one iteration is also superior to more iterations. In Figure (Ce) we show that although one iteration cannot surpass one epoch, it is better than few iterations. This is because when we only search for one iteration, the model does over-fit the data, thus the model generalizes well. When we only searched for few iterations, the number of different images seen by the model is not big enough. However, since the super-net only contains skip connections, such number of gradient updates has been enough for the architecture parameters to get over-fitted. This is the reason that few iterations perform worse than one iteration. After we have searched for one whole epoch, the super-net has seen enormous different images, this helps it generalize better on the testing This is the reason that one epoch performs the best. In terms whether we should search for one iteration or two, in Figure 3(d) we show that both choices work well.
When we do not search for the operators after the topology search, we assign all the remaining edges fixed operator. Thus, which operator we should choose becomes critical question. Figure 3(e) show that 3 x 3 separable convolution can indeed outperform all other operators in terms of accuracy.
7

---

Under review as a conference paper at ICLR 2021
c2ee wripedd (1ie)d
(a)
(b)
(c)
913
ecp
2411
spp
frand
(c)
g
(h)
254
1677
9032 1332 1742 1933. PIAL 9132
(k)
(l)
Figure 3: Ablation study. [a) CIFARIO: Accuracy Search epochs (in the same rb) CIFARIO:
Accuracy Search epochs (multiple runs); [c] CIFARIO: Accuracy Search iterations; (d) Accu-
racy on CIFARIO: I0: vs 2 search iterations (multiple runs); (e) CIFARIO 10: Accuracy Operator
replacing skip-connections: (
CIFARIO: Accuracy Training epochs of the found architecture;
(g)
Epoch-wise on CIFAR 1O0: Accuracy Max cigenvalue v2 Aroh Ceal: (b) Iteration- wise on CI-
FAR100: Accuracy Max eigenvalue V Arch (i) CIFARIÓ: Operator scarch's 's epoch-wise im-
pact on testing accuracy (0 epoch means only searching for the topology): ( CIFARIO 10: The found architecture's 's training epochs' impacts the testing accuracy (same architecture); (k) Testing
curacy: CIFARI0 10 600 evaluation epochs ImageNet 250 evaluation epochs (evaluating after train-
ing the same architecture on different datasets); (I) Testing accuracy: CIFARIO 1200 evaluation epochs- ImageNet 250 evaluation epochs (evaluating after training the same architecture on differ- datasets)
As shown in Figure 3(t) we find that under different number of evaluation epochs, both the ab- solute value and the relative ranking of the same architecture's testing accuracy may vary; i.c.
some architectures performing well within 600 epochs perform poorly after 1200 epochs. However, in general, they still obey positive correlation, with a Pearson correlation coefficient of 0.77, as
shown in Figure 3() In terms of the generalization ability from CIFAR10 to ImageNet, Figure 3() reveals that the architectures performing well after long-term evaluation on CIFAR1O can usually generalize better on ImageNer, with the correlation coefficient of 0.7; yet, as shown in Figure (kk
there no guarantee that those working well on CIFARIO within limited evaluation epochs can also dominate on ImageNet because this only proves that they can quickly converge, not that they can converge to a global optimum.
In Figure 3(g) and 3(h) we show that one epoch is not only optimal choice on CIFARIO, but also enough for the topology-only search on CIFAR100. addition. as the search epochs and iterations increase, the max eigenvalue of the loss's Hessian matrix the validation set increases and the testing accuracy is generally decreasing because the model's generalization ability is dropping. This phenomenon is particularly obvious epoch-wise because, after just few iterations, the model can
8

---

Under review as a conference paper at ICLR 2021
Table Different configurations' impacts FTSO
CIFARIO
ImageNet Err. %))
Search Cost
FTSO's Configuration
Err. %)
(GPU-days)
600
1200
Top1
Top5
CIFAR
ImageNet
CIF. Topo(skip,lit,
2.68
2.54
24.36
7.27
7.87 x 10-6
CIE, Topo(skip.
2.48
2.23
23.60
7.01
2 x 10
CIF. Topo(sk)p.50pp.)
2.77
2.52
0.01
CIF.
2.85
2.59
23.97
7.20
0.01
CIF. (ttp::skip..eppppppppppppp.p
2.59
2.36
23.97
7.12
0.05
CIF. p.t..mppp..pppppppppp....
2.83
2.48
0.05
CIF. T0po(s)p3.50ep.)
2.63
2.48
0.02
CIF. Topo(sep3. (ttps/epp3..0ee..)0pp500500
2.56
2.52
24.73
7.60
0.06
CIF. Topo(3op.50kg)) hetppp00e.++((0eepp..
2.59
2.50
0.05
CIF. (tt.ppp...p+ppppppp
2.68
2.59
0.07
Part ImageNet Topo(skip,lit)
24.03
7.07
0.0002
Part ImageNet Topo(skip,
23.94
7.05
0.0017
Part ImageNet Topo()))p.6pp.) Full ImageNet Topo(skip.
24.59
7.38
0.009
2.35 2.26
23.58
6.80
0.01
'3op' means pool 3x3, skip connect and none; '4op' means: sep conv 3x3, max pool 3x3,
skip connect and none; 'm.p.' means: max pool 3x3; 'sep3' means: sep conv 3x3.
"CIF' means CIFAR 10; "Topo(skip, means search for topology with only skip connec- tions for iteration; 'lpp' means epoch; PPart ImageNet' means to search on part of ImageNet.
already reach a comparable accuracy on the training set. Then the model's performance on the testing set starts to relate with its generalization ability.
GENERALIZATION TO OTHER TASKS AND SEARCH SPACES
As shown in Section 4 FTSO works well under different search spaces and node numbers. Theoret- ically, FTSO's advantages to DARTS can be enlarged while search space and node number increase. This is because FTSO reduces the computational cost from (nn²) (nn²) and avoids over-fitting. Although in this paper, we establish FTSO within differentiable search spaces, in fact, the first topol- ogy second operator strategy
limited within any specific search space or tasks. No matter the search space is discrete continuous, we first shrink the candidate operator set, and only retain the simplest operator. After this, the size of the whole search space reduced in magnitude. Then, we search for the best topology with whatever search algorithm. In this way, promising topology can found. Then, we can either directly assign each edge powerful operator or use gradients to search for operators. Generally, the directly replacing strategy leads to higher accuracy, and the gradient-baas baaee strategy reduces model complexity.
CONCLUSION
In this paper, we propose an ultra computationally efficient neural architecture search method named FTSO, which reduces NAS's search time cost from days to less than 0.68 seconds, while achieving 1.5% and 0.27% accuracy improvement on ImageNet and CIFARTO respectively. Our key idea is to divide the search procedure into two sub-phases. In the first phase, only search for the network's topology with simple operators. Then, in the second phase, we fix the topology and only consider which operators should choose.
Our strategy is concise in both theory and implementation, and our promising experimental results show that current NAS methods contain too much redundancy, which heavily impacts the efficiency and becomes a barrier to higher accuracy. What is more, our method is not bound by differentiable search spaces, also cooperate well with existing NAS approaches.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architec- tures using reinforcement learning. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. http:/pppe//pppaaaei.eeeeeeeeee.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations, 2019. URL https:
//openzeview. htt.://eeee.tttoaaa.a......//...
X. Chen, L. Xie, J. Wu, and Q Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. 2019 IEEE/CVF International Conference on Com- puter Vision (ICCV), pp. 1294-1303, 2019.
Xuanyi Dong, Lu Liu, Katarzyna Musial, and Bogdan Gabrys. NATS-Bench: Benchmarking nas algorithms for architecture topology and size. arXiv preprint 200:::200090043377, 2020.
K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25, pp. 1097- 1105. Curran Associates, Inc., 2012. URL http: nips. CC cc/paper/
4824 imagenet-classee cat ion- with with-deep convolcoiionnnnncc -neurllllerrrl--- weweeurrl-ewwwrrree networks. pdf
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceed- ings of the European Conference on Computer Vision (ECCV), September 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations, 2019. URL htt.::tttt:/ptttt htttps::///peereeiieettt
nett/Forum2id=SleeWooo
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 4095-4104, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http://proceediing ngs mlr. wwwppsewss......
Sa. html
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27- February 1, 2019, pp. 4780 4789. AAAI Press, 2019. doi: 10.1609/aaai v33101.33014780 URL. / htt.:/oi.oorgooooooooooooo 1609// a v33101. 33014780
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJV), 15(3):211-255 2015. doi: 10. 1007////s 1263-015-0816-y.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures leartt by cell-based neu- ral architecture search. In International Conference on Learning Representations, 2020. URL
https::/ net httt://orrrmmm/oo0//222222.
10

---

Under review as a conference paper at ICLR 2021
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA. USA. May 7-9, 2015, Conference Track Proceed- ings, 2015. URL
1409. 1556
C. Szegedy, Wei Liu, Yangqing Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich. Going deeper with convolutions. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1-9, 2015.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In International Conference on Learning Representations, 2019. URL https:// openreview net/ 2ome//oooommddddyggggg
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi. Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-effiiiet architecture search. In International Conference on Learning Representations, 2020. URI TRR.https:/ http::://ppeerevieer www..wiwwwww.................... net. (0--BJ1$6344
forum?
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hut- ter. Understanding and robustifying differentiable architecture search. In International Confer- ence on Learning Representations, 2020. URL
hwtp:/wwwwwwww..eeeeeeeeeeeeeeee htt.:pppnrr.ee..eeeeeoerrrrroraa formmmid
H1 BDgDKDDD
Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pp. 7603- 7613. PMLR, 2019.
prw.s/v9 wttps//////esuus wwwulhoueeee html
B. Zoph, V. Vasudevan, J. Shlens, and Q. V. Le. Learning transferable architectures for scalable image recognition. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 8697-8710, 2018.
Barret Zoph and Quoe V. Le. Neural architecture search with reinforcement learning. In 5th In- ternational Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL (tttst::: URL.ittp:://pperrrriew /oppneeeeew.... net/ htt.//oormmidizeem 1 &
A APPENDIX
A.1 CONFIGURATION DETAILS
All our search experiments are done under the same 11GB VRAM constraint on one RTX 2080Ti GPU.
For the configuration of experiment on CIFARIO, following DARTS, we search for the architecture in a cell manner, where each cell has four intermediate nodes and 16 initial channels during the search. We use half the images (25K) from the training set for kernel weight updating and the other half for architecture parameter updating. When evaluating, we stack 18 normal and two reduction cells to form the entire network.
For the configuration of experiment on ImageNet, when searching, we have two configurations. In the first configuration, following PC-DARTS, we only pick 10% and 2.5% of images from the training set for the kernel weights and architecture parameters' optimizations respectively: in the second configuration, thanks to FTSO's huge computational cost reduction, it is feasible for us to search with the whole of ImageNet. For evaluation, stack 12 normal cells and two reduction cells to form the entire network and train it from scratch for 250 epochs. The detailed configurations are shown in Table
11

---

Under review as a conference paper at ICLR 2021
Table 4: FTSO's searching configurations CIFAR10 and ImageNet
Search Config.
Evaluation Config.
Hyper-parameter
CIFAR10
ImageNet
CIFAR10
ImageNet
Cells (Normal + Reduction)
6 6+2
6 2
18 +8+2 2
12 + 2
Channel proportion
25%
25%
Initial channel number
16
16
36
48 SGDM Linear (0.5, 0)
Kernel optimizer
SGDM
SGDM
SGDM Cos. (0.025, 0)
Kernel learning rate
Cos. (0.025, 0)
0.5
Architecture optimizer
Adam
Adam
Architecture learning rate
x 10
6 10
Some items are because, when evaluating, no architecture parameters need to be updated.
12


Reviews:
[{"review_id": "oyBFIvnpNM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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": "Title: FTSO: EFFECTIVE NAS VIA FIRST TOPOLOGY SECOND OPERATOR\n\nSummary of the paper:\n\nThe goal is to fit the hyper-parameters of the neural network namely topology (i.e. network architecture) and operator (e.g. skip connection or convolution) rather than just fit the parameters (i.e. weights). The approach is similar to DARTS which relaxes the architecture choice to obtain a continuous optimisation.\n\nThe main difference from DARTS is that rather than jointly selecting operator and topology, first the topology and then the operator is selected. It's roughly a form of coordinate descent. \n\nThe paper is empirical in nature and claims good results. \n\nPros:\n\nThe idea of optimising topology then operator appears to work well in practice. \n\nCons:\n\nThe presentation is far from top tier conference standard. \n\nExamples include, this sentence from the introduction (yes, it's one sentence): \n\n\"We first mathematically prove that, by greatly shrinking the graph of the search space, reducing the operators’ complexity in magnitude, lowering the required searching period from 50 epochs to one iteration and significantly easing the Matthew effect, namely that the complex operators may never get the chance to be well tuned, thus the found architecture only contains very simple operators, and performs poorly on the testing set, FTSO reduces the required parameters by a factor of 0.53×108, decreases the FLOPs per iteration by a factor of 2×105 and significantly promotes the accuracy compared to the baseline, PC-DARTS.\"\n\n(Anyway, the \"mathematical proof\" aluded to is an informal argument for an example, essentially saying that searching one coordinate then the other is cheaper than searching both jointly.)\n\nAlso figures 2 and 3 are unreadable on printout. \n\nAlso, there is no code to check the results. This is a significant factor considering the empirical nature.\n\nRecommendation:\n\nThe paper is surely interesting to some, but needs a lot more work.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kBrCZZJrlbT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 work researches the issue of neural architecture search (NAS), which is of significance for practical applications of deep neural networks and has become an active research topic in the past several years. Many methods on NAS have been developed recently. The computational efficiency of search has been one of the obstacles for this line of research.\n\nStrengths of this work: \n\nThe key idea of this work is to decouple the search of network topology and the search of operators. By doing so, the computational efficiency can be substantially increased (say, reducing the search time from several GPU-days to less than one second), while well maintaining the classification performance or even slightly improving it. Experimental study on CIFAR10 and ImageNet demonstrates the advantage of the proposed method, especially the improvement on computational cost. The paper is overall well written.   \n\nWeaknesses:\n\n1. This work can do better on theoretical analysis. Currently, it mainly describes how the decoupled search (FTSO) is implemented (in Section 3). Considering the significance of the improvement on computational efficiency, it will be more valuable to discuss whether such a kind of decoupled search can be generally applied, or it can only work for certain kinds of network architecture, data, or tasks. This will provide more insights on this interesting method and theoretical contribution.\n\n2. This paper has described several interesting observations. It will be better if they are further explained and discussed. \n\n2-1. When conducting topology search, this paper only uses a simple operator (say, skip connection). It is indicated that this supernet can hardly overfit the dataset, which is understandable. Meanwhile, with such a simple operator, will the supernet underfit the data? This needs to be clarified.\n\n2-2. Similarly, in Section 4.1, it is stated that FTSO contains very few parameters and therefore can even achieve comparable performance to PC-DARTS. Why could very few parameters lead to this comparable performance? Please clarify it.\n\n2-3. At the end of Section 4.2, it is found that the best architecture obtained by the search is the shallowest and widest one. The current explanation (provided at the end of this Section) is too brief and vague for such an interesting and surprising finding. This need to be further clarified. \n\n2-4. The part at the top of page 7 discusses the performance with respect to iteration and epoch. It is not very clear. It is stated that \"although one iteration cannot surpass one epoch, it is better than a few iterations.\" However, considering that one epoch consists of multiple iterations, this statement seems to contradict to itself and is a bit hard to follow. Please clarify.   \n\n3. The second paragraph on page 4 compares the computational complexity of DARTS and the proposed method. Since this is the key part of this work, more details shall be provided on how the complexity is worked out. \n\n4. Minor issues:\n\n4-1. The first sentence of the second paragraph on page 2 needs to be revised.\n4-2. Although the investigation of correlation among different architectures is mentioned as the key motivation for this work, how is the correlation of architectures considered in this work is not presented. This shall be improved; \n4-3. In Section 4.2, the resolution of images in ImageNet is reduced to 28x28. Does this imply that the proposed method is not effective enough to deal with images of normal size?\n4-4. Figures 1 and 2 shall be enlarged.\n\n--- Thank the authors for the detailed response. After reading the response and the comments of peer reviewers, the rating is altered as follows. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "iYQgLp4WIrr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 proposes a method for Neural Architecture Search (NAS) with two stages of search. In the first  stage, the topology of the cell is searched with only one operator (skip connection) using graph pruning through gradient descents. In the later stage, there are two ways to search the operators. In the first approach, the found topology is equipped with some operators (e.g., 3x3 convolution,  skip connection, and 3x3 dilated convolution) and then the architecture parameters are optimized. Another approach is to replace all operators with one single operator e.g. convolution. The experiments show that the searching time is reduced significantly compared to DARTS and the results on CIFAR-10 and ImageNet are very competitive.\n\n\nStrengths:\n\n- The search time is reduced significantly from normal DARTS and PC-DARTS.\n- The results are competitive to the prior differentiable NAS methods with less searching time.\n\nWeaknesses:\n\n- It is not very clear how exactly the topology search algorithm ensures that each node is connected?\n- The choice of skip connection as the operator for topology search is not well-justified. Max-pooling has no learnable parameters too. Is there any particular reason why skip connection?\n- The experiments are lacking because there is no evaluation on current benchmarks such as NAS-101, NAs1Shot1, or NAS-201 that can explicitly show how the search algorithm performs. In current experimental results, it is very difficult to judge if the proposed approach has benefits for searching 'good' architectures.\n- The comparison with other differentiable NAS algorithms (e.g., DARTS and PC-DARTS) can be delivered in the form of a table. The information of this comparison is all scattered in the manuscript.\n- In Section 3 \"In FTSO, this problem is almost nonexistent because, the skip connection has no kernel\nweights to tune\", this is not very clear how the problem exists in the DARTS formulation and how the formulation in the proposed approach can mitigate this issue. There is no discussion about the bi-level program in DARTS.\n- It is very difficult to follow the overall approach, it would be better to have an algorithm/pseudocode.\n- \", we take the second strategy as the default configuration because, it is much more efficient, and the large amount of kernel weights, contained in the first strategy, may lead to over-fitting,\nand finally leads to worse performance than the second strategy. \". How do exactly large amount of kernel weights lead to overfit in NAS? Is there any proof/citation about it? The second strategy has no clear evidence to always give better results compared to the first strategy.\n- There is no empirical results how the algorithm works by varying the number of nodes in a cell. This will show that the limit of the proposed approach and also its capacity to handle various number of nodes.\n\n- The manuscript is poorly written,  at least these sentences/paragraphs must be clarified and revised:\n** In Section 3,  \"it might be possible to cluster the architectures according to their connection topologies\"\n** In Subsection 4.3, \"When we do not search for the operators, after the topology search, we assign all the remaining\nedges a fixed operator\" and the rest of the paragraph is difficult to follow.\n** In Section 3, \"Secondly. Because our supernet contains very few parameters, it can hardly over-fit the dataset. Thus, the found architecture may generalize better on new datasets.\". This sentence is a claim without any evidence.\n** Table 3 is not clear, some codes are not described in its caption.\n** In Section 3, please fix \"Firstly. It allows the algorithm to converge within extremely few iterations... and so on..\"", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Three reviewers have reviewed this manuscript, and they had severe reservations regarding the presentation quality and the lack of sufficient theoretical support behind empirical observations. Even after rebuttal, the reviewers maintained that the above issues are not fully resolved. Unfortunately, this paper cannot be accepted in its current form.
Decision: Reject