Rethinking Architecture Selection in Differentiable NAS
Authors: Ruochen Wang
Minhao Cheng
Xiangning Chen
Xiaocheng Tang
Cho-Jui Hsieh
Venue: ICLR 2021 Oral (2021)

Abstract: Differentiable Neural Architecture Search is one of the most popular Neural Architecture Search (NAS) methods for its search efficiency and simplicity, accomplished by jointly optimizing the model weight and architecture parameters in a weight-sharing supernet via gradient-based algorithms. At the end of the search phase, the operations with the largest architecture parameters will be selected to form the final architecture, with the implicit assumption that the values of architecture parameters reflect the operation strength. While much has been discussed about the supernet's optimization, the architecture selection process has received little attention. We provide empirical and theoretical analysis to show that the magnitude of architecture parameters does not necessarily indicate how much the operation contributes to the supernet's performance. We propose an alternative perturbation-based architecture selection that directly measures each operation's influence on the supernet. We re-evaluate several differentiable NAS methods with the proposed architecture selection and find that it is able to extract significantly improved architectures from the underlying supernets consistently. Furthermore, we find that several failure modes of DARTS can be greatly alleviated with the proposed selection method, indicating that much of the poor generalization observed in DARTS can be attributed to the failure of magnitude-based architecture selection rather than entirely the optimization of its supernet.

Published as a conference paper at ICLR 2021
RETHINKING ARCHITECTURE SELECTION IN DIFFER- ENTIABLE NAS
Ruochen Wang', Minhao Cheng', Xiangning Chen', Xiaocheng Tang', Cho-Jui Hsich' DDepartment of Computer Science, UCLA, DDiDi AI Labs (ruocwang, Bacceng)@ucia.... edu (xiangning, chohsieh ucla.edi xi siocchengtanggddddgggloo.....c.
ABSTRACT
Differentiable Neural Architecture Search is one of the most popular Neural Ar- chitecture Search (NAS) methods for its search efficiency and simplicity, accom- plished by jointly optimizing the model weight and architecture parameters in weight-sharing supernet via gradient-based algorithms. At the end of the search phase, the operations with the largest architecture parameters will be selected form the final architecture, with the implicit assumption that the values of archi- tecture parameters reflect the operation strength. While much has been discussed about the supernet's ' optimization, the architecture selection process has received little attention. We provide empirical and theoretical analysis show that the magnitude of architecture parameters does not necessarily indicate how much the operation contributes to the supernet's performance. We propose an alternative iitibattionbbbscd architecture selection that directly measures each operation's s influence on the supernet. We re-evaluate several differentiable NAS methods with the proposed architecture selection and find that is able to extract significantly improved architectures from the underlying supernets consistently. Furthermore, we find that several failure modes of DARTS can be greatly alleviated with the proposed selection method, indicating that much of the poor generalization ob- served in DARTS can be attributed to the failure of magnitude-base architecture selection rather than entirely the optimization of its supernet.
INTRODUCTION
Neural Architecture Search (NAS) has been drawing increasing attention in both academia and in- dustry for its potential to automatize the process of discovering high-performance architectures, which have long been handerafted. Early works on NAS deploy Evolutionary Algorithm (Stanley & Mikkulainen, 2002; Real 2017 Liu et al. (211)) and Reinforcement Learning (Zoph & Le) 2017 Pham et al. 2018 Zhong et al.] to guide the architecture discovery process. Recently, several one-shot methods have been proposed that significantly improve the search efficiency (Brock
ct al. 2018 Guo et al., 2019: Bender et al. 2018).
As particularly popular instance of one-shot methods, DARTS (Liu et al., 2019) enables the search process to be performed with a gradient- optimizer in an end-to-end manner. It applies contin- uous relaxation that transforms the categorical choice of architectures into continuous architecture parameters a. The resulting supernet can be optimized via gradient- based methods, and the opera- tions associated with the largest architecture parameters are selected form the final architecture. Despite its simplicity, several works cast doubt on the effectiveness of DARTS. For example, sim- ple randomized search (Li Talwalkar 2019) outperforms the original DARTS: Zela et al. (2020) observes that DARTS degenerates to networks filled with parametric-free operations such the skip connection or even random noise, leading to the poor performance of the selected architecture.
While the majority of previous research attributes the failure of DARTS to its supernet optimization Zela et al. 2020 Chen & Hsich| 2020 Chen et al.) 2021). little has been discussed about the validity of another important assumption: the value
reflects the strength of the underlying operations. In this paper, we conduct an in-depth analysis of this problem. Surprisingly, we find that in many cases, does not really indicate the operation importance in supernet. Firstly, the operation associated

---

Published as a conference paper at ICLR 2021
with larger does not necessarily result in higher validation aceuracy after discretization. Secondly, as an important example, we show mathematically that the domination of skip connection observed in DARTS (i.e. Oskip becomes larger than other operations.) is in fact reasonable outcome of the supernet's optimization but becomes problematic when we rely on a to select the best operation.
If a is not a good indicator of operation strength, how should we select the final architecture from pretrained supernet? Our analysis indicates that the strength of each operation should be evaluated based on its contribution to the supernet performance instead. To this end, we propose an alternative perturbation-base architecture selection method. Given a pretrained supernet, the best operation on an edge is selected and discretized based on how much perturbs the supernet accuracy; The final architecture is derived edge by edge, with fine-tuning in between so that the supernet remains converged for every operation decision. We re-evaluate several differentiable NAS methods (DARTS (Liu et al. 2019), SDARTS (Chen & Hsieh] 2020), SGAS (Li et al., (0200) and show that the proposed selection method is able to consistently extract significantly improved architectures from the supernets than magnitude-based counterparts. Furthermore, find that the robustness issues of DARTS can be greatly alleviated by replacing the magnitude-based selection with the proposed perturbation-baaee selection method.
BACKGROUND AND RELATED WORK
Preliminaries of Differentiable Architecture Search (DARTS) We start by reviewing the for- mulation of DARTS. DARTS' search space consists of repetitions of cell-based microstructures. Every cell can be viewed as a DAG with N nodes and E edges, where each node represents a latent feature map x², and each edge is associated with an operation o (e.g. skip_connect sep_conv_3xe from the search space O Continuous relaxation is then applied to this search space. Concretely, every operation on an edge is activated during the search phase, with their outputs mixed by the ar- chitecture parameter to form the final mixed output of that edge m(x*) Eoeo E. exp espee__(x") o(x²).
exp
This particular formulation allows the architecture search to be performed in differentiable manner: DARTS jointly optimizes a and model weight w with the following bilevel objective via alternative gradient updates:
min (wa aa) s.t. =" arg min Ltrain (W, a).
(1)
We refer to the continuous relaxed network used in the search phase as the supernet of DARTS. At the end of the search phase, the operation associated with the largest as on each edge will be selected from the supernet form the final architecture.
Failure mode analysis of DARTS Several works cast doubt the robustness of DARTS Zela et al. (2020) tests DARTS on four different search spaces and observes significantly degenerated performance. They empirically find that the selected architectures perform poorly when DARTS' supernet falls into high curvature areas of validation loss (captured by large dominant eigenvalues of the Hessian V2 Ca (wr, oz)). While Zela al. 2020) relates this problem the failure of supernet training in DARTS, we examine it from the architecture selection aspects of DARTS, and show that much of DARTS' robustness issue can be alleviated by better architecture selection method.
Progressive search space shrinking There is line of research on NAS that focuses on reducing the search cost and aligning the model sizes of the search and evaluation phases via progressive search space shrinking (Liu et al., 2018 Li et al.) 2019) Chen et al., 2021 Li et al. 2020). The general scheme of these methods is to prune out weak operations and edges sequentially during the search phase, based on the magnitude of a following DARTS, Our method orthogonal to them in this respect, since we select operations based on how much it contributes to the supernet's performance rather than the a value. Although we also discretize edges greedily and fine-tune the network in between, the purpose is to let the supernet recover from the loss of accuracy after discretization to accurately evaluate operation strength on the next edge, rather than to reduce the search cost.
2

---

Published as a conference paper at ICLR 2021
3 THE PITFALL OF MAGNITUDE-BASER ARCHITECTURE SELECTION IN DARTS
In this section, put forward the opinion that the architecture parameter does not necessarily rep- resent the strength of the underlying operation in general, backed by both empirical and theoretical evidence. As important example, we mathematically justify that the skip connection domination phenomenon observed in DARTS is reasonable by itself, and becomes problematic when combined with the magnitude- architecture selection.
3.1
a MAY NOT REPRESENT THE OPERATION STRENGTH
0.
00
05
Magelaabe of (Gefiracal) Dicratication sourayy atoooaggen
Mag llsb (ookra
Mayn of (lellmendd Daur Douiiaaiionn ausseny consargana
Obucri oulic accmaity consargera
84-
8
243
340
senoect
come 243
coo. 542
2x3
cone 3x5
310 Me
5G
263
2,00 366
2x3
2G
Figure 1: a vs discretization accuracy at convergence of all operations on randomly selected edges from pretrained DARTS supernet (one subplot per edge). The magnitude of a for each operation does not necessarily agree with its relative discretization accuracy at convergence.
(a) Magnitude
(b) Strength
Figure 2: Operation strength on each edge of S2 (skip_conneed .conncct, eep_conv_33t (a). Operations associated with the largest a. (b). Operations that result in the highest discretization validation accuracy at convergence. Parameterized operations are marked red.
Following DARTS, existing differentiable NAS methods use the value of architecture parameters a to select the final architecture from the supernet, with the implicit assumption that represents the strength of the underlying operations. In this section, we study the validity of this assumption in detail.
Consider one edge on pretrained supernet; the strength of an operation on the edge can be naturally defined as the supernet accuracy after we discretize this operation and fine-tune the remaining net- work until it converges again; we refer to this as "discretization accuracy at convergence" for short. The operation that achieves the best discretization accuracy convergence can be considered as the best operation for the given edge. Figure [] shows the comparison of a (blue) and operation strength (orange) of randomly select edges on DARTS supernet. As we can see, the magnitude of for each operation does not necessarily agree with their relative strength measured by discretization accuracy at convergence. Moreover, operations assigned with small as are sometimes strong ones that lead to high discretization accuracy at convergence. To further verify the mismatch, we inves- tigate the operation strength on search space S2, where DARTS fails dramatically due to excessive skip connections (Zela et al. 2020). S2 is variant of DARTS search space that only contains two operations per edge (skip_connect. rep_conv_3x3) on (left) and operation strength (right) all edges on S2. From Figure 2a can that askip connect > &eep conv 3r3 on 12 of 14 edges. Consequently, the derived child architecture will lack representation ability and perform poorly due to too many skip connections. However, as shown
Figure 2 shows the selected operations based
3

---

Published as a conference paper at ICLR 2021
in Figure 2b the supernet benefits more from discretizing to sep_conv than skip-connect on half of the edges.
3.2 CASE STUDY: SKIP CONNECTION
Several works point out that DARTS tends assign large skip connections, resulting in shallow architectures with poor generability (Zela et al.) 2020; Liang et al. 2019 Bi et al. connection domination" issue is generally attributed to the failure of DARTS supernet optimiza- tion. In contrast, we draw inspiration from research on ResNet (He et al.
all] 2019). This "skip
2016) and show that this
phenomenon by itself is a reasonable outcome while DARTS refines its estimation of the optimal feature map, rendering askip ineffective in the architecture selection.
In vanilla networks (e.g., VGG), each layer computes new level of feature map from the output feature map of the predecessor layer; thus, reordering layers at test time would dra- matically hurt the performance (Veit et al. 2016). Unlike vanilla networks, Greff al. (2077) and Veit et al. (2016) discover that suc- cessive layers in ResNet with compatible chan- nel sizes are in fact estimating the same optimal feature map that the outputs of these layers stay relatively close to each other at convergence; As a result, ResNet's test accuracy remains robust under layer reordering. Greff al. (2017) refers to this unique way of feature map estimation in ResNet as the "unrolled estimation."
Table I:
Test accuracy before and after layer (edge) shuffling on cifar10. For ResNet and VGG, randomly swap two layers in each stage (de- fined as successive layers between two downsam- pling blocks. For DARTS supernet, randomly swap two edges in every cell.
VGG
ResNet
DARTS
Before After
92.69
93.86
88.44
9.83 1 0.33
83 23,2015 1 2.03
81.09 1.87
DARTS' supernet resembles ResNet, rather than vanilla networks like VGG, in both appearance and behavior. Appearance-wise within a cell of DARTS' supernet, edges with skip connection are in direct correspondence with the successive residual layers in ResNet. Behavior-wise, DARTS' supernet also exhibits high degree of robustness under edge shuffling. As shown in Table D randomly reordering edges on a pretrained DARTS' supernet test time also has little effect on its performance. This evidence indicates that DARTS performs unrolled estimation like ResNet as well, i.e., edges within a cell share the same optimal feature map that they try to estimate. In the following proposition, we apply this finding and provide the optimal solution of in the sense of minimizing the variance of feature map estimation.
Proposition 1. Without loss of generality, consider one cell from simplified search space consists of two operations: (skip, conv). Let m² denotes the optimal feature map. which is shared across all edges according to the unrolled estimation view (Greff et al. 2017). Let ox(2x) be the output of convolution operation, and let Ie be the skip connection (ie.. the imput feature map of edge e). Assume m², O (xte and xe are normalized to the same scale. The current estimation of m² can then be written as:
exp(Aeeno)
exp(asship)
(xe) exp(Accooo) + exp(asskip)
(Ze) exp((iconn) + exp(
Fee
where Oconoo and Sssip are the architecture parameters defined in DARTS. The optimal &cons and 0 Saksp minimizing var (xx) - m²), the variance of the difference between the optimal feature map m² and its current estimation me(Fe), are given by:
aronn x varlxe m²)
(3)
Oakip var(o (xe) m²)
We refer the reader to Appendix A.4 for detailed proof. From eq. ( and eq. (4). we can see that
the relative magnitudes Osskip and Cioonv come down to which one xe or oe (Te) is closer to m in variance:
xe (input of edge e) comes from the mixed output of the previous edge. Since the goal of every edge is to estimate m" (unrolled estimation), &e is also directly estimating m
"rroposition] I Jnfoldd the optimal in principle and does not constraint the particular optimization method (i.c., bilevel, single-level, or blockwise update) to achieve it. Moreover, this proposition can be readily extended various other search spaces since we can group all non-skip operations into single o-().
4

---

Published as a conference paper at ICLR 2021
(Iee is the output of a single convolution operation instead of the complete mixed output of edge e, so it will deviate from m even at convergence.
Therefore, in well-optimized supernet, ze will naturally be closer m than (x causing Oskip to be greater than come-
07
Our analysis above indicates that the better the supernet, the larger the (atskip acone) gap (softmaxed) will be- come since Ze gets closer and closer m the supernet optimized. This result is evidenced in Figure S where mean mean(askip (cconv) continues to grow as the supernet gets better. In this case, although Otakip > Oleonn is rea- sonable by itself, becomes an inductive bias NAS if we were to select the final architecture based on a.
08
05
01
00
60.5
65.7
Accumny Supernet
4 PERTURBATION-BASEE ARCHITECTURE SELECTION
Figure 3: mean(Oasip Ocone) (soft- maxed) v.s. supernet's validation accu- racy. The gap of (a'skip acono) in- creases as supernet gets better.
Instead of relying the value to select the best opera- tion, we propose to directly evaluate operation strength in terms of its contribution to the supernet's performance. The operation selection criterion is laid out we describe the entire architecture selection process.
in section 4.1 In section 4.2
4.1 EVALUATING THE STRENGTH OF EACH OPERATION
In section 3.1
define the strength of each operation on given edge as how much it contributes to the performance of the supernet, measured by discretization accuracy. To avoid inaccurate eval- uation due large disturbance of the supernet during discretization, we fine-tune the remaining supernet until it converges again, and then compute its validation accuracy (discretization accuracy convergence). The fine-tuning process needs to carried out for evaluating each operation on an edge, leading to substantial computation costs.
To alleviate the computational overhead, we consider more practical measure operation strength: for each operation on given edge, we mask it out while keeping all other operations, and re-evaluate the supernet. The one that results in the largest drop in the supernet's validation accuracy will be considered the most important operation that edge. This alternative criterion incurs much less perturbation to the supernet than discretization since only deletes one operation from the supernet time. As result, the supernet's 's validation accuracy after deletion stays close to the unmodified supernet, and thus alleviates the requirement of tuning the remaining supernet to convergence. Therefore, implement this measurement for the operation selection in this work.
Algorithm 1: Perturbation-based Architecture Selection
Input: A pretrained supernet S. Set of edges & from S, Set of nodes N from S Result: Set of selected operations )
while El > 0 do
randomly select an edge e E & (and remove from E);
forall operation o on edge e do evaluate the validation accuracy of S when is removed (ACC
end
select the best operation for e: of + arg min, AC
discretize edge e to of and tune the remaining supernet for a few epochs;
end
4.2 THE COMPLETE ARCHITECTURE SELECTION PROCESS
Our method operates directly top of DARTS' pretrained supernet. Given supernet, randomly iterate over all of its edges. We evaluate each operation on an edge, and select the best one to be discretized based on the measurement described in section 4.1 After that, we tune the supernet for
5

---

Published as a conference paper at ICLR 2021
few epochs recover the accuracy lost during discretization. The above steps repeated until all edges are decided. Algorithm summarizes the operation selection process. The cell topology is decided in similar fashion. We refer the reader to Appendix A.3 for the full algorithm, including deciding the cell topology. This simple method is termed "perturbation-aase" architecture selection (PTY" in the following sections.
EXPERIMENTAL RESULTS
In this section, we demonstrate that the perturbation-base architecture selection method able to consistently find better architectures than those selected based on the values of a. The evaluation is based on the search space of DARTS and NAS-BBnch-22 (Dong & Yang. 2020), and we show that the perturbation- architecture selection method can be applied to several variants of DARTS.
5.1 RESULTS ON DARTS' CNN SEARCI SPACE
We keep all the search and retrain settings identical to DARTS since our method only modifies the architecture selection part. After the search phase, we perform perturbation-base
architecture selection following Algorithm I on the pretrained supernet. We tune the supernet for epochs between two selections as it is enough for the supernet recover from the drop of accuracy after discretization. We run the search and architecture selection phase with four random seeds and report both the best and average test errors of the obtained architectures.
As shown in Table 2 the proposed method (DARTS+PT) improves DARTS' test error from 3.00% 2.61 %, with manageable search cost (0.8 GPU days). Note that by only changing the architecture selection method, DARTS performs significantly better than many other differentiable NAS methods that enjoy carefully designed optimization process the supernet, such as GDAS (Dong & Yang 2019) and SNAS (Xie et al. 2019). This empirical result suggests that architecture selection is crucial to DARTS: with the proper selection algorithm, DARTS remains a very competitive method.
Our method is also able to improve the performance of other variants of DARTS, To show this, evaluate our method on SDARTS((s) and SGAS (Chen & Hsich| 2020 Li et al. 2020). SDARTS((s) is variant of DARTS that regularizes the search phase by applying Gaussian perturbation to a. Unlike DARTS and SDARTS, SGAS performs progressive search space shrinking. Concretely, SGAS progressively discretizes its edges with the order from most least important, based novel edge importance score. For a fair comparison, we keep its unique search space shrinking process unmodified and only replace its magnitude-based operation selection with see from Table 2 our method consistently achieves better average test errors than its magnitude- based counterpart. Concretely, the proposed method improves SDARTS' test error from 2.67% to 2.54% and SGAS' test eтror from 2.66% to 2.56%. Moreover, the best architecture discovered in our experiments achieves test error of 2.44%, ranked top among other NAS methods.
As can
5.2 PERFORMANCE ON MAS-BENCH-201 SEARCH SPACE
Relatteleneeeee Belotion Magi habotazall Bokskko
Partabukoniuredd Scecdon Muge Nogalaatsooord Delocann
That Poanaay 20
00
60
Netubbacce-ceel Selection
Mays Magrlaabllareel
Search Epooh
Soarch Eaoch
SoarchEachh
8corth Epoch
Figure& 4: Trajectory of test accuracy on space JAS-Bench-200 and three datasets (Left: cifar 10, Middle: c0f Right: Imagenet16- 120)). The test accuracy of our method is plotted by taking the snapshots of DARTS' supernet at corresponding epochs and run our selection method on top of it.
To further verify the effectiveness of the proposed perturbation- duct experiments on similar to DARTS. Every architecture in the search space is trained under the same protocol three
architecture selection, we NAS-Bend MAS--ench-200 provides a unified cell-based search space

---

Published as a conference paper at ICLR 2021
Table 2: Comparison with state-of-the-art image classifiers on CIFAR-10.
Architecture
Test Eiror
Params
Search Cost
Search
(%)
(M)
(GPU days)
Method
DenseNet-BC (Huang al. 2017
3,46
25.6
manual
NASNet-A (Zoph et al. 2018
2.65
3.3
2000
RL
AmochaNet-A [een et ar 2019
3.34 0.06
3.2
3150
evolution
AmoehaNet-B (Real
2.55
0.05
2.8
3150
evolution
PNAS (Liu 2018
3.41 1:1::00 0.09
3.2
225
SMBO
ENAS (Pham
20718
2,89
4.6
0.5
RI.
NAONeE [Loo
2018
3.53
0.4
NAO
SNAS (moderate) Xie
2019
2.85 = 0.02
2.8
1.5
gradient
GDAS Dong & Ying 2019
2,93
3.4
0.3
gradient
BayesNAS (Zhou et 2019
3.4
gradient
ProxylesNNAS (SSTCCar
2.08
gradient
NASP Yao et 20,22020
2.83 0.09 0.09
3.3
0.1
gradient
P-DARTS (Chen ef 2019
2.50
3.4
0.3
gradient
PC-DARTS [Xu
2020
2.57 0.07
3.6
0.1
gradient
R-DARTS (Z2)/Zen
2020
2.95 0.21
1.6
gradient
DARTS (Liu et al. 2019
0.10
3.3
0.4
gradient
SDARTSFRS (Chen Fixieh
2020
2.67 0.08
3.4
0.4
gradient
SGAS (Cri avgieLr (rrrrreaaa 2020
0.24
3.7
0.25
gradient
DARTS+PT (avg)"
0.08
3.0
0.8
gradient
DARTS+PT (best)
2.48
3.3
0.8
gradient
SDARTS- (avg)"
2.54 + 0.10
3.3
0.8
gradient
SDARTS-RS+PT (best)
2.44
3.2
0.81
gradient
SGAS+PT ICrit. avg)"
2.56 0.10
3.9
0.29:
gradient
SGAS+FT (Crit.l best)
2.46
3.9
0,291
gradient
Obtained on different space with PyramidNet (Han al. 2017] as the backbone.
Recorded single GTX 1080Ti GPU.
Obtained by running the scarch and retrain phase under four different seeds and computing
the average test error derived architectures.
datasets (cifar10, cifar100, and imagenet 6- 1-0,, and their performance can be obtained by querying the database, As section 5.1 we take the pretrained supernet from DARTS and apply our method on top of it. All other settings are kept unmodified. Figure 4 shows the performance trajectory of DARTS+PT compared with DARTS. While the architectures found by magnitude-based selection degenerates over time, the perturbation- based method is able to extract better architectures from the same underlying supernets stably. The result implies that the DARTS' degenerated performance comes from the failure of magnitude based architecture selection.
ANALYSIS
6.1 ISSUE WITH THE ROBUSTNESS OF DARTS
Zela al. 2020) observes that DARTS tends to yield degenerate architectures with abysmal per- formance. We conjecture that this robustness issue of DARTS can be explained by the failure of magnitude-basee based architecture selection.
Table 3: DARTS+PT S1-S4 (test error (%)).
To show this, we test DARTS' perfor- mance with perturbation-based architec- ture selection on four spaces proposed by Zela al. (2020) (S1-S4). The complete specifications of these spaces can be found in Appendix A.2 Given a supernet, the performs poorly across spaces and datasets (column 3 in Table However, method is able to consistently extract meaningful archi- tectures with significantly improved per- formance (Column in 33)
Datasel
DARTS
DARTS#PT (Ours)
DARTS+PT (lix
3.54
330
2.35
S2
4.85
2.79
2.59
2.49
$4
7.20
2.64
2.58
S2
26.05
23.16
23.30
C100
28.90
22.03
21.94
architecture selected based
22.85
20.80
20.66
4.58
261
2.39
2.53
2.32
SVHN
53
3,41
2.42
2.32
This column will he explained later Section 6.3
Notably, DARTS+PT is able to find meaningful architecture S2 (skip-connect, sep_conv_3xx and S4 (noise, sep conv 3x3), where DARTS failed dramatically. As shown Figure [5] on S2, while magnitude- based selection degenerates to architectures filled with skip connections, DARTS+PT is

---

Published as a conference paper at ICLR 2021
able to find architecture with 4 convolutions; On S4, DARTS+PT consistently favors sep_conv_3xx on edges where a selects noise.
S2 (DARTS)
(b) S2 (DARTS+PT)
(DARTS)
(d) S4 (DARTS+PT)
Figure 5: Comparison normal cells found on S2 and S4. The perturbation based architecture selection (DARTS+PT) is able to find reasonable architectures in cases where the signituddebasee method (DARTS) fails dramatically. The complete architecture can be found in Appendix A.9 Non-trivial operations marked red.
6.2 PROGRESSIVE TUNING
In addition to operation selection, we also tune the supernet after edge is discretized so that the supernet could regain the lost accu- racy. To measure the effecctiveness of our op- cration selection criterion alone, we conduct an ablation study the progressive tuning part. Concretely, we test a baseline by combining progressive tuning with magnitude-basee op- eration selection instead of our selection crite- rion, which we code-named DARTS+PT-Mag. Figure [6 plots the change of validation accu- racy of DARTS+PT and DARTS+PT-Mag dur- ing the operation selection phase. As we can see, DARTS+PT is able to identify better op- erations that lead to higher validation accuracy than the magnitude-basee alternative, revealing the effectiveness of operation selection cri- teria. Moreover, DARTS+PT-Mau is only able obtain test error of 2.85% DARTS space
accuracy (96)
50
epoch
Figure 6: The trajectory of validation accuracy in the operation selection phase S2. DARTS+PT able select better operations that lead to higher accuracy of the supernet than DARTS+PT- Mag.
on cifar O0 much worse than DARTS+PT (2.61 %), indicating that the operation selection part plays crucial role in method.
6.3 FIXING a UNIFORM
Since the proposed method does not rely on a for architecture selection, a natural question is whether it is necessary to opti- mize stand-alone a. We find that by fix- ing = 0 (uniform weights for all the op- erations) while training supernet and ap- plying perturbation-baul based architecture se-
Table 4: DARTS+PT v.s. DARTS+PT (fixed a) more spaces (test eiror %) on cifar10.
Space
DARTS
DARTS+PT
DARTS+PT (fix a)
DARTS Space
3.00
2.61
2,87
Bench--n
45.7
6.20
lection, the resulting method performs on-par with DARTS+PT, and some cases even better. For example, PARTS+PT (fix a) achieves better performance than DARTS+PT on NAS-Bench-201. On DARTS' search space and its variants S1-S4, DARTS+PT (fix a) performs similarly to DARTS+PT. and Table This surprising finding suggests that the most naive approach, simply training a supernet without a, will be competitive method when combining with the proposed perturbation- based architecture selection.
The results can be found in Table and
8

---

Published as a conference paper at ICLR 2021
7 CONCLUSION AND DISCUSSION
This paper attempts to understand Differentiable NAS methods from the architecture selection per- spective. We re-examine the magnitude-basee architecture selection process of DARTS and provide empirical and theoretical evidence on why it does not indicate the underlying operation strength. We introduce an alternative perturbation-base operation strength via its contribution to the supernet performance. The proposed selection method able to consistently extract improved architecture from supernets trained identically the respec- tive base methods on several spaces and datasets.
architecture selection method that directly measures the
Our method brings more freedom in supernet training as does not rely on a to derive the final architecture. We hope the perturbation- based architecture selection can bring new perspective to the NAS community to rethink the role of a in Differential NAS.
ACKNOWLEDGEMENT
This work is supported in part by NSF under IIS-1901527, 11S-2008173, IIS-2048280 and by Army Research Laboratory under agreement number INF-202--001
REFERENCES
Gabriel Bender, Pieter-Jan Kindermans, Barret Zoph, Vijay Vasudevan, and Quoc Le. Understand- ing and simplifying one-shot architecture search. In Jennifer Dy and Andreas Krause (eds.), Pro- ceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 550-559, Stockholmsmässann Stockholm Sweden, 10-15 Jul 2018. PMLR. URL / hww.tttp:ppprcceednggg./ mlr pttpss///0//eeeeerree11
html
Kaifeng Bi, Changping Hu, Lingxi Xie, Xin Chen, Longhui Wei, and Qi Tian, Stabilizing darts with amended gradient estimation on architectural parameters, 2019.
Andrew Brock, Theo Lim, J.M. Ritchie, and Nick Weston. SMASH: One-shot model architecture search through hypemetworks. In International Conference Learning Representations, 2018. URL httthhttts:://penreeee eew net forum? www.:eww.wwweeee/eee/ee w iidrrddCEhssrss
Han Cai, Ligeng Zhu, and Song Han. ProXylessNAS: Direct neural architecture search on target task
and hardware. In International Conference Learning Representations, 2019. URL https:
//openreview. net/ tere//fore www.ooomddddyyyyaeeeeee
Xiangning Chen and Cho-Jui Hsieh. Stabilizing differentiable architecture search via perturbation- based regularization. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th Interna- tional Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Re- search, pp. 1554-1565 PMLR, 13-18 Jul 2020. CRL/ttpp:/pproceddie www.eediiins.m..........m......e mtt.sress/.p.ps//////m w119/chen205s html
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. DrNAS: Dirichlet neural architecture search. In International Conference on Learning Representations, 2021. URL htttttts////eeeeeeettt
www.//eetwwoiiieaeeeeeee.... 9FWas
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Confer- ence on Computer Vision, pp. 1294-1303, 2019.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In Proceed- ings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1761 1770, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations (ICLR), 2020.
Klaus Greff, Rupesh K. Srivastava, and Jürgen Schmidhuber. Highway and residual networks learn unrolled iterative estimation. In International Conference on Learning Representations (ICLR), 2017.

---

Published as a conference paper at ICLR 2021
Zichao Guo, Xiangyu Zhang, Haoyuan Mu, Wen Heng. Zechun Liu, Yichen Wei, and Jian Sun. Single path one-shot neural architecture search with uniform sampling, 2019.
Dongyoon Han, Jiwhan Kim, and Junmo Kim. Deep pyramidal residual networks. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jul 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Puttern Recognition, pp. 770-778, 06 2016. doi: 10.1 20.1109/VVR..201.990
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR), Jul 2017. doi: 10.11009/yp.22017.225. URL http:
11.09/
CVPR. 201 2017.243
Guilin Li, Xing Zhang, Zitong Wang, Zhenguo Li, and Tong Zhang. Stacnas: Towards stable and consistent differentiable neural architecture search, 2019.
Guohao Li, Guocheng Qian, Itzel Delgadillo, Matthias Muller, Ali Thabet, and Bernard Ghanem.
Sgas: Sequential greedy architecture search. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 1620-1630, 2020.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search, 2019.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping, 2019.
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. Lecture Notes in Computer Science, pp. 19-35 2018.
Hanxiao Liu, Karen Simonyan, Oriol Vinyals, Chrisantha Fernando, and Koray Kavukcuoglu. Hi- erarchical representations for efficient architecture search, 2017.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference Learning Representations, 2019.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architec- ture optimization. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 7816-7827. Curran Associates, Inc., 2018. URL /ttt:://papera www...cc.ppp......ee.eeeeo.pp 1007-nee 1e17-nnural-arre architet-a wwt.:oottttttioioo.commmm
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. 4104, Stockholmsmässsan Stockholm Sweden, 10-15 Jul 2018. PMLR.
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoe V. Le, and Alexey Kurakin. Large-scale evolution of image classifiers. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, pp. 2902-20922 2911- JMLR.org, 2017.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. Proceedings of the AAAI Conference on Artificial Intelligence, 33: 4780-4789, Jul 2019. ISSN 2159-5399. doi: 10.1609/aau 10.16099aaai3331101.30.4444 33300.3301.8888 URL http:
10. 609 aaai vv33 3301 4780
Kenneth O. Stanley and Risto Miikkulainen. Evolving neural networks through augmenting topolo- gies. Evolutionary Computation, 10(2):9--127 2002, 2002, doi: 10. 10.1162/00666650220001111.. URL
10

---

Published as a conference paper at ICLR 2021
Andreas Veit, Michael Wilber, and Serge Belongie. Residual networks behave like ensembles of relatively shallow networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 550- -558. Curran Associates, Inc., 2016.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In International Conference on Learning Representations, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi. Qi Tian, and Hongkai Xiong. PC- DARTS: Partial channel connections for memory-efficient architecture search. In International Conference on Leurning Reprexentations, 2020. httphhttps//operevviieee net net.:orumttfmm forum?
id=BJJS634TPP
Quanming Yao, Ju Xu, Wei-Wei Tu, and Zhanxing Zhu. Efficient neural architecture search via proximal iterations. In AAAI, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. In International Conference on Learning Representations, 2020.
Zhao Zhong. Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. Practical block-wisc neural net- work architecture generation. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2018, 2018.
Hongpeng Zhou, Minghao Yang. Jun Wang, and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. In ICML, pp. 7603-7613, 2019. URL http::/proccedinng/
m wtw. 2tt.pprrs///77/oolleee html
Barret Zoph and Quoc V. Le. Neural architecture search with reinforcement learning. Interna- tional Conference Learning Representations (ICLR), 2017. URL htt.hsss/://aaxiv.orgg
abs abs/1611. 01578
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc Le. Learning transferable architectures for scalable image recognition. 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, Jun 2018. doi: 10. 20.1109/cvp..018.0000 8.0907. URL http://dx. doi wwtp:/ooo...gg///// 1rg/10.
1109/CVPR. 2018.. 00907

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 DESCRIPTION ABOUT OUR BASELINE MODELS
A.1.1 DARTS
DARTS (Liu et al. 2019 a pioneering work that introduces the general differentiable NAS frame- work, which we reviewed in section 2 In DARTS, the topology and operation are searched together. Concretely, at the end the search, it selects one operation for every edge the normal (reduction) cell based on the architecture parameter a. Then it selects two input edges for each node in the cell by comparing the largest of every input edge. The final architecture consists one operation on each of the eight edges in the normal (reduction) cell. The operation on an edge will be selected from a pool of seven candidates: skip_connection avg-pool_3x3, max-pool_3x3, sep_conv_3se sep conv 5x5, dil conv 3x3, and dil conv 5x5. In addition to these operations, DARTS also main- tains a "none" op, which used exclusively for determining the topology rather than treated as an operation (Liu al. (019). Since the main focus of paper is operation assignment, omit none op when applying the proposed selection method on DARTS.
A.1.2 SDARTS
SDARTS (Chen & Hsich 2020 is variant of DARTS aiming at regularizing the bilevel opti- mization process in DARTS via random Gaussian perturbation, inspired by the recent finding that regularizing DARTS' supernet leads improved performance. While the optimization of architec- ture parameter in SDARTS is identical to DARTS, it distorts the architecture parameters with random Gaussian noise while training the model weights w. This simple yet effective regularizer able to consistently improve the robustness and performance of DARTS.
A.1.3 SGAS
SGAS (Li et al. 2020) represents a line of research on improving the search efficiency of differen- tiable NAS by progressively shrinking the search space. It first trains the model weights alone for 10 epochs. After that, it selects one edge from the supernet and then selects the best operation on that edge based
be discretized. The edge selection is based on the ranking of the proposed
edge importance score. The process stops after all eight edges of the final architecture are decided.
A.2 MICROARCHITECTURE OF SPACE S1 S4
Zela al. (2020) introduces four variants of the DARTS' space (S1, S2, S3, and S4) study the robustness of DARTS. These spaces differ from DARTS' original space only in the number and types of operations each edge. Apart from that, everything else is the same.
S1 is a pre-optimized search space consisting of top2 operations selected by DARTS. As result, each edge contains a different set of operations to be searched from.
S2 consists of two operations: skip cotpect and sep sep_cony.. conv__ov3333 _33..
S3 consists of three operations: none, skip_connect and sep_comv_3x3
S4 consists of two operations: noise and sep_conv3x33. The noise operation outputs random Gaussian noise (000 1) regardless the input. This operation generally hurts the performance of discretized architecture, and should be avoided by NAS algorithm.
12

---

Published as a conference paper at ICLR 2021
A.3 THE COMPLETE ALGORITHM OF PERTURBATION BAAAAD ARCHITECTURE SELECTION
Algorithm 2: Perturbation based Architecture Selection
Input: A pretrained Supernet S, Set of Edges & from S, Set of Nodes N from S Result: Set of selected operations {or Jeee, and top2 input edges for each node {(eh)). (2)x JnEN
while E|> do // operation selection phase randomly select edge E & (and remove it from E);
forall operation o on edge e do evaluate the validation accuracy of S when is removed (ACC)o): end
select the best operation on e: o + arg min, ,CC,a
discretize edge e to of and train the remaining supernet until it converges again; end
while W| do // topology selection phase randomly select node n E N (and remove from N);
forall input edge of node do evaluate the validation accuracy of S when e is removed (ACC),.)
end
(2)*) set top2 edges on )eli",
to be the ones with lowest and second lowest ACC,,s
prune out all other edges of and train the remaining supernet until it converges again; end
A.4 PROOF OF PROPOSITION
Proof. Let skip = toftma((Osksp)) and Oconv = So Softmaz(O.oow)). Then the mixed operation can be written as (xxe = I deonvee (Ie) + Oskipiee We formally formulate the objective to be:
min Gakag Doans
Var(mo((e) m²)
(5)
s.t.
Oskip + Pconv =
(6)
This constraint optimization problem can be solved with Lagrangian multipliers:
L(O Ocanvs A)
V (Trr(Te((Te) m²) - A(Oakip + Oconv - 1) Var(Deono (xx) + Oskipte - -m²) )- A(0akip + O Oconv - 1)
(7)
(8)
Var(Ocono
(xxe (o
m²) + Ockipp(re - -m"))
A(Oshri + Ocons - 1)
Var(Oconno (O mn) }) + Var(DasippT m ))
2Co0 (Ze) - m ), 9 Akkkpp(pe -m²))
A(Oskip + Oconv - 1)
(10)
2 V ar (o - m + ship Var (Ie m²)
+ 20con O O (x.) - m - m
A(Oskip + Oconv 1)
(11)
Setting:
aL
Aconv + Oskipp 1= 0
(12)
0X
0L
20 V var(oc -m") + 20 Cou(oee - m Ie -m")
00.omm
-x=0
(13)
0L
-m, 20 cono Cou(o -m", The m²) + 20 20 Var(se m²)
08 00.kip
A=0 0
(14)
13

---

Published as a conference paper at ICLR 2021
Solving the above equations will give
(15)
0 Var(Te - -m") - Cov((s( m1 Itc. -m²")
(16)
Var(Oc(Ie) -m") Cou(oc( m. , -m²))
-mm²
Kkksp
(17)
7
Where Z = Var(o mm") ((te) -te - + Var(see m²) - Coov(o
m. Ie m²). Aligning basis with DARTS, we get:
a'one = log Var(ae m²) - Coo(oc(Ie) m², m")] + C
(18)
Kkipp log [Var(o.(ze) m²) - Cov(oc(Fe) m m +C
(19)
The only term that differentiates Oskip from O'conv is the first term inside the logarithm, therefore:
Coonv var(Ne mm))
(20)
dskip x var(Oe(Te) - mmn)
(21)
A.5 MORE FIGURES ON a AND DISCRETIZATION ACCURACY AT CONVERGENCE
We provide extra figures similar Figure D to take into account the randomness of supernet's s train- ing. We first train 6 supernets with different seeds, and then randomly select 1 edge from each of them. can see that the results are consistent with Figure [ As shown in Figure 7 the magni- tude of for each operation does not necessarily agree with its relative discretization accuracy convergence.
Vagnitude
Megeitude
Magrituuee
not por t0
mg to
coonect
wo con te coyy Jat ol cone set on con Ae
not nog menot td
connect
He one
coyy Set Coy
not, pert 30 mgg Ad
connect
Ae comy bet
cony
03
Vageit
Uagritateo
Magritale
anry comagggrr
senuary Moroeggeeo
soruacyy stroneergezee
04
29t 2001 340
Soot 3e3
Sin., 343
wng Juny 565
al 2.mm 3x3
Laty 3t
ol 2000 30
915
363
we www. 3r3
Srary 215
dLonon 2x3
5.
skg
wet
sko
de
Figure/ 7: a v.s. discretization accuracy at convergence of all the operations on 6 randomly selected edges from DARTS' supernet trained with different seeds (one subfigure for each edge).
A.6 PERFORMANCE TRAJECTORY OF DARTS+PT (FIX a) ON NAS- -ES-CINC1--01
We plot the performance trajectory of DARTS+PT (fix a)) on NAS- Bench-201 similar to Figure As shown in Figure 8 it consistently achieves strong performance without training all, indicating that the extra freedom of supernet training without a can be explored to develop improved search algorithm in the future.
14

---

Published as a conference paper at ICLR 2021
(5)
Thel Kenurezc of tore
DWATSHFT
Search
Search
Epoch
Figure 8: Trajectory of test accuracy architectures found by DARTS+PT (fix a) on space NAS- Bench-201 and datasets (Left: cifar10, Middle: cifar100, Right: Imagenet16-120),
Table 5: Evaluation of the derived architecture on ImageNet in the mobile setting.
Test Error( %)
Params
Search
Architecture
top-1
top-5
(M)
Method
DARTS (Liu et al. 2019
26.7
8.7
4.7
gradient
DARTS+PT
25.5
8.0
4.6
gradient
A.7 ABLATION STUDY ON THE NUMBER OF FINE-TUNING EPOCHS
As described in section 4.2 perform fine-tuning between two edge decisions recover supernet from the accuracy drop after discretization. The number of fine-tuning epochs is set to 5 for all experiments because empirically we find that is enough for the supernet to converge again. this section, we conduct an ablation study on the effect of the number of fine-tuning epochs. As shown in Figure 9 the gain from tuning the supernet longer than 5 epochs marginal.
Teat Accunccy (%) the Derived Architattuees
80.0
89.5
88.5
67.5
8r.0g
10
Number of Epodht the Fine-luring Slep
Figure 9: Performance DARTS+PT under different number fine-tuning epochs on NAS-Bench-
201. Tuning the supernet longer results in marginal improvement the proposed method.
A.8 ARCHITECTURE TRANSFERABILITY EVALUATION ON IMAGENET
We further evaluate the performance of the derived architecture ImageNet. We strictly follow the training protocals as well as the hyperparameter settings of DARTS (Liu et al. 2019) for this experiment. As shown in Table 5 the proposed method improves the topl performance of DARTS by 1.2%.
A.9 SEARCHED ARCHITECTURES
15

---

Published as a conference paper at ICLR 2021
2
259 con.. 3x3
seg conv Tx3
CLE4
Slip connect
M00 cony
(b) Reduction Cell Figure 10: Normal and Reduction cells discovered by DARTS+PT on cifar10
Normal Cell
pood 3c3
cl. 11,cam
3e3
0
302 20..sr..330 345
max JMAt 3r3
BL 363
(a) Normal Cell
(b) Reduction Call
Figure 11: Normal and Reduction cells discovered by SDARTS+PT cifar10
max pool 3x3
corw
550. www..ony.ce 3x3
cony.
keg_ comy. 3xT
CLEK3
Normal Cell
(b) Reduction Cell
Figure 12: Normal and Reduction cells discovered by SGAS-PT on cifar10
Oa post
(a) Normal Cell
(b) Reduction Cell
Figure 13: Normal and Reduction cells discovered by DARTS+PT on cifar on Space $1
(a) Normal Cell
(b) Reduction Coll
Figure 14: Normal and Reduction cells discovered by DARTS+PT cifar 10 Space $2
skip connect
Scp_comned
spp sep_oon
(k)
epp, cany, 365
Gp cone 3x3
(k<1)
up cone
skip connect
Normal Cell
(b) Reduction Cell
Figure 15: Normal and Reduction cells discovered by DARTS+PT on cifar 10 on Space $3
16

---

Published as a conference paper at ICLR 2021
Sep conv 3x2
F_ [k:21
tep. 3o3
conv. 3x3
(k-1)
conv 3x3
sep_sonv
conv
(k:1
19g, cony.oryyy 3x3
(k-2
Seg_conv, 3x3
Normal Cell
(b) Reduction Cell
Figure 16: Normal and Reduction cells discovered by DARTS+PT on cifar on Space $4
Normal Cell
(b) Reduction Cell
Figure 17: Normal and Reduction cells discovered by DARTS+PT on cifar 100 on Space
Mi.ORA 20
(b) Reduction Cell Figure 18: Normal and Reduction cells discovered by DARTS+PT on cifar100 on Space S2
(a) Normal Cell
sep conv 3x3
sep_come 3x3
sep 3x3
(_
sknn_connect
(k)
sep_conv 3x3
2
c (k-1)
sep_conv 3x3
skip skip_connect
conv _sp_conv33x3
(a) Normal Cell
(b) Reduction Cell
Figure 19: Normal and Reduction cells discovered by DARTS+PT cifar 1f0 on Space S3
17

---

Published as a conference paper at ICLR 2021
sep_conv
sep_ cony 3x3
sep_cony 3x3
sep. 3x3
sep_conv 3x3
eep_conv_330 _x3
c_ (k-2)
c (
sep_conv 3x3
3
sep_ cep__onv____ 3x3
3
C_ (k)
(k}
sep_conv_ 3x3
sep_conv_ _x33
2
2
c_ (k-)
C_ {k--
sep_cony 3x3
sep_ 3x3
sep_conv _onv_333
sep cep_conv__cc 3x3
sep_ conv 3x3
sep_conv 3x3
(b) Reduction Cell Figure 20: Normal and Reduction cells discovered by DARTS+PT on cifar 100 on Space S4
(a) Normal Cell
(b) Reduction Cell Figure 21: Normal and Reduction cells discovered by DARTS+PT on svhn Space S1
(a) Normal Cell
Ma DRT 363
seg 107
280, cany,
(b) Reduction Cell Figure 22: Normal and Reduction cells discovered by DARTS+PT on svhn on Space S2
(a) Normal Cell
Sig. roneee
9ig Comnnn
(b) Reduction Cell Figure 23: Normal and Reduction cells discovered by DARTS+PT svhn Space S3
(a) Normal Cell
340 OITY,
30
(a) Normal Cell
(b) Reduction Cell
Figure 24: Normal and Reduction cells discovered by DARTS+PT on svhn on Space S4
18


Reviews:
[{"review_id": "rKa26ZHA1g2", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "-- Short Summary --\n\nThis paper proposes a new policy for selecting the optimal architecture in neural architecture search (NAS), in particular for methods that involve a one-shot model and that deploy gradient-based methods for the search. The proposed algorithm sequentially prunes and fine-tunes the one-shot (aka supernet or weigh-sharing) model until the operations that contribute the most in the one-shot validation performance remain at each edge of the cell (represented as a DAG).\n\n-- Detailed comments --\n\nPositive points: \n- The structuring of the sections.\n- The paper investigates an interesting aspect of gradient-based NAS algorithms.\n- I liked the theoretical justification on the issue with the high \\alpha values for skip connections in many DARTS [1] and the experimental backup for that in table 1.\n\nIssues and concerns:\n- The proposed algorithm does not seem that elegant and still uses another proxy for true performances of stand-alone architectures, even though indirectly in a lower level, i.e. the drop in performance of the one-shot model after removing one operation at a time in each edge is used to assess the optimal operations operation that will be present in the final architecture. Furthermore, this procedure seems to induce quite some variance by randomly sampling the edges in the cell and then executing the operation drop & fine-tuning steps. Did the authors investigate this by running multiple times their proposed procedure on the same one-shot model?\n- Another issue with the algorithms seems to be that it does not scale well with the number of operation and edges in the cell.\n- I am not fully convinced by the experiment conducted in 3.1. It seems the authors discretize only one edge of the supernet and fine-tune it further with the discretized edge. In this case the other edges (not discretized) contribute to the network performance together with the single discretized edge and this might be misleading when assessing the importance of an operation. Ultimately, we care about the final network performance, and how this single operation in the discretized edge would perform when combined with all other possible choices in the other edges (still intractable to compute of course). Another potential issue is that the fine-tuned supernet might not correlate well with the discretized stand-alone architecture performance. Can the authors please elaborate on this experiment further in more details?\n- Do the theoretical and experimental backup for that hold for other sampling-based methods, e.g. GDAS [2] or SNAS [3]?\n- I think the reported search costs in Table 2 are inaccurate. The authors should also add on top of their method the costs of the base algorithm (e.g. 1GPU day for DARTS 2nd order on one GTX 1080Ti).\n\nMinor:\n- There are a lot of grammatical errors throughout the text. I would recommend to do a detailed proof read of the paper.\n- section 3.2, second paragraph: The acronym VGG does not stand for vanilla networks\n- The data in Fig. 1 would look better as a scatter plot, which would also more nicely show the miscorrelation between the 2 quantities that are being compared.\n- I like the structuring of the paper, however I think the experiment in the conclusion should not be there, but in the benchmark tables.\n- In conclusions: why do you fix \\alpha = 0? Did you mean \\alpha = 1?\n\n-- References --\n\n[1] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In ICLR 2019\n\n[2] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. In CVPR 2019\n\n[3] Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR 2019", "extra_scores": {}, "extra_text": {}}, {"review_id": "UwfUB2i6kic", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "Summary:\n\nIn one-shot differentiable NAS, a supergraph is usually trained (via bilevel optimization as in DARTS, or other approximations to bilevel such as gumbel softmax, etc). After supergraph training, a final architecture is obtained by taking the operator at each edge which has the highest architecture weight magnitude. This step is usually termed as the 'finalization' step. (In DARTS the finalization step actually orders incoming edges by the max of the architecture weight magnitudes at each edge and selects the top two edges and the corresponding maximum architecture weight in them as the final operators.). This paper examines this quite ad hoc step very closely. It finds that the magnitude of architecture weights (alphas commonly in this niche literature) are misleading. It shows by careful ablation experiments that alpha magnitudes are very much not useful in selecting good operators. \n\nBy taking inspiration from the \"unrolled estimation\" viewpoint of ResNet prior work it shows that DARTS converging to degenerate architectures where alphas over parameters operators like skipconnect is actually to be expected when finalization step relies on the magnitude of alpha. \n\nThe paper proposes a much more intuitive finalization step which just picks the operator at each edge which if removed from the supergraph results in the largest drop in validation accuracy. To bring back the supergraph to convergence a few epochs of further training is carried out between operator selection.  \n\nExperiments show that just by carefully thinking about the finalization step in differentiable one-shot NAS, one can obtain much better performance. In fact, one does not even need architecture weights at all! Don't worry about complicated bilevel optimization, gumbel softmax approximation, etc. Just train a supergraph and pick operators progressively. \n\nComments:\n\n- The paper is wonderfully written! Thanks!\n\n- As I read a paper I try to think without looking at the experiments, what set of experiments I would try to run to prove/disprove the hypotheses proposed. Afterwards I go through the experiments and see if those experiments were actually run (or if they differed why). In this case, every experiment and more were already run. Particularly towards the end I was thinking what if we just got rid of all the alphas and just trained a supergraph as usual and did the PT finalization as proposed. And lo and behold, it actually works better!\n\n- This paper is actually throwing a big wrench in one-shot differentiable NAS literature. Many papers are being written which try to improve/fix DARTS and DARTS-like methods. If I were to believe the experiments, I don't actually need to do any of that. I have some questions I hope to discuss with the authors:\n\n1. Is all the complicated bilevel optimization (often popular as 'metalearning' currently) not useful in the case of NAS? (This is not really the authors' burden to answer but I am just hoping to see if they have any insights.)\n\n2. Can we view the PT finalization step as a progressive pruning step?  So if I were to turn this into a method which produces a pareto-frontier of models (e.g. accuracy vs. memory/flops/latency etc), we first train a big supergraph and then progressively prune out operators one at a time as proposed here and take a snapshot of the supergraph and plot it on the x-y plot (where say x is latency and y is accuracy) and pick the ones clearly on the pareto-frontier and train them from scratch? (Again not really authors' burden but curious if they have any insights)\n\n3. Figure 4 suggests that training the supergraph anymore than 20 epochs only hurts performance (no matter which finalization procedure is used, of course PT has far less of a drop). Does bilevel optimization actually hurt with weight sharing?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PIkEMho0dRl", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "Pros\n- The work analyzes the differential NAS methods from a new perspective that the value alpha is not suitable for selecting edges. Based on this observation, the author proposes a new method to evaluate the edge strength.\n- The motivation is clear and the finding of the residual path is interesting.\n- The proposed method is effective and shows good results.\n\nCons\n- All experiments are based on the Cifar10 dataset, the author may consider extending the proposed method to a larger dataset such as ImageNet.\n- The efficiency of the proposed method, what is the computational cost?\n- Some descriptions and figures are not very clear.  E.g., in Figure 1, what do the three figures stand for respectively?\n- Except for the residual connection, can the same rules be found in other layers?\n\nThe paper is interesting and has found some values for the NAS community by rethinking the representation ability of the important factor $\\alpha$. The paper may need proof-reading and do some experiments on a more widely used large-scale dataset. I tend to accept this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "AI2NA_QQ9wA", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "# post rebuttal\n\nI have no further concerns and increase the rate to accept.\n\n# Summary\n\nThis paper identifies an interesting phenomenon that on DARTS based method, the operation can not be simply chosen based on the maximum value of trained weights. The authors propose a new selection paradigm. For each operation, one should first discretize the soft weights encoding into a one-hot, then fine-tune the network for some iterations, and use the performance as a metric to select the operation. \nIt provides an interesting and novel analysis on the question of why DARTS always converges to skip-connections. The experiments are conducted on CIFAR-10, 100, and SVHN on DARTS space and NASBench-201 over three datasets.\n\n\n# Strength\n\nI enjoyed reading this paper although there are some flaws in terms of presentation. It tackles one of the most critical problems in the DARTS domain, why the skip-connection dominates after the super-net training converges. All earlier works propose some solutions in an ad-hoc manner, by early stopping. This is the first time I have seen a simple and reasonable explanation of this phenomenon, and by itself is a great contribution to the NAS community. The toy example constructed in section 3 Figure 3 also evidences this explanation, though the theoretical part only discussed a simple case with two operations. \n \n\n# Weakness\nI am looking forwards to hearing back from the authors and improve my scores if these issues are fixed/explained. \n\n## Effectiveness of the method \nThe proposed solution is simple yet effective, though there is not another analysis of why discretization and fine-tune will triumph except comparison with baselines. On page 6 we can see the perturbation based method, test accuracy drops for both your method and the baseline after 20 epochs. Does it mean the current approach is still not working well? Training for longer simply destroys the search and without proper training, the network is essentially in a random search state, i.e. it goes back to the game that DARTS do not out-perform random search. This trend is consistent over three datasets. \n\n## Other questions\n\n- Ablation on the finetuning. In the algorithm part, you mentioned to train for a few epochs, but do you have some rule for that? I saw you doing this on DARTS space (Figure 6), but will this be more reasonable on NASBench-201?\n\n- Table 1:  Will it because the swapped edges belong to the same node? For example, you could control the swap that it only happens, e.g. edge 0->2 and 2->4?\n\n\n- Discretization accuracy is not clearly defined. Say for the operation weights in DARTS, [0.2, 0.4, 0.2, 0.2], does this mean you will directly evaluate the accuracy over [0, 1, 0, 0] given the supernet? Or first, make it one-hot and train to convergence while using the original super-net as a warmup? (I think I found it on page 3 after reading it again but please also help me to confirm.)\n\n- Figure 1: NAS methods are not stable over one set of training, could authors provide another visualization, say training the darts super-net for multiple times, and shows the average of these training the alpha and its discretization accuracy? Showing three selected edges is not convincing.\n\n## suggestions on the presentation\n- Section 2.1, 2.2 and 2.3 can be a `\\paragraph` instead of subsections. They are too short.\n- Grammar issues\n\t- Abstract: one of the most ... methods (s)\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new selection paradigm for selecting the optimal architecture in neural architecture search (NAS), in particular for methods that involve a one-shot model and that deploy gradient-based methods for the search. Basically, the paper focuses on examining the max selection very closely and found the magnitude of architecture weights are misleading. Instead, the paper proposes much more intuitive finalization step, pick the operator that has the largest drop in validation if the edge is removed. All reviewers agreed that the idea is interesting, the paper is well-written, and the results found in the paper are interesting. In addition, author response satisfactorily addressed most of the points raised by the reviewers, and most of them increased their original score. Therefore, I recommend acceptance.
Decision: Accept (Oral)