On Redundancy and Diversity in Cell-based Neural Architecture Search
Authors: Xingchen Wan
Binxin Ru
Pedro M Esperança
Zhenguo Li
Venue: ICLR 2022 Poster (2022)
Keywords: NAS
machine learning architectures
AutoML

Abstract: Searching for the architecture cells is a dominant paradigm in NAS. However, little attention has been devoted to the analysis of the cell-based search spaces even though it is highly important for the continual development of NAS. 
In this work, we conduct an empirical post-hoc analysis of architectures from the popular cell-based search spaces and find that the existing search spaces contain a high degree of redundancy: the architecture performance is less sensitive to changes at large parts of the cells, and universally adopted design rules, like the explicit search for a reduction cell, significantly increase the complexities but have very limited impact on the performance.
Across architectures found by a diverse set of search strategies, we consistently find that the parts of the cells that do matter for architecture performance often follow similar and simple patterns. By constraining cells to include these patterns, randomly sampled architectures can match or even outperform the state of the art.
These findings cast doubts into our ability to discover truly novel architectures in the existing cell-based search spaces and, inspire our suggestions for improvement to guide future NAS research.
Code is available at https://github.com/xingchenwan/cell-based-NAS-analysis.

Published as a conference paper at ICLR 2022
ON REDUNDANCY AND DIVERSITY IN CELL-BASED NEURAL ARCHITECTURE SEARCH
Xingchen Wan 15 Binxin Ru Pedro M. Esperança', Zhenguo Li Machine Learning Research Group, University of Oxford Huawei Noah's Ark Lab, London Huawei Noah's Ark Lab, Hong Kong (xwan, rabin) ) @ @robots.co s.rotss.o ox. uk, ceadro.esperaccay. 1i. zhenguo) @huawei. com
ABSTRACT
Searching for the architecture cells is dominant paradigm in NAS. However, little attention has been devoted to the analysis of the cell-based search spaces even though it highly important for the continual development of NAS. In this work, we conduct an empirical post-hoc analysis of architectures from the popular cell- based search spaces and find that the existing search spaces contain high degree of redundancy: the architecture performance is minimally sensitive to changes at large parts of the cells, and universally adopted designs, like the explicit search for a reduction cell, significantly increase the complexities but have very limited impact on the performance. Across architectures found by a diverse set of search strategies, we consistently find that the parts of the cells that do matter for architecture perfor- mance often follow similar and simple patterns. By explicitly constraining cells to include these patterns, randomly sampled architectures can match or even outper- form the state of the art. These findings cast doubts into our ability to discover truly novel architectures in the existing cell-based search spaces, and inspire our sugges- tions for improvement to guide future NAS research. Code is available at ht nttps: //github. . com/
cell based- NAS- analysis.
INTRODUCTION
Neural Architecture Search (NAS), which automates designs of neural networks by task, has seen enormous advancements since its invention. particular, cell-based NAS has become an important technique in NAS research: in contrast to attempts that directly aim to design architectures at once and inspired by the classical, manually-designer architectures like VGGNet and ResNet that feature repeated blocks, cell-based NAS searches for repeated cells only and later stacks them into full architectures. This simplification reduces the search space (although it remains highly complex), and allows easy transfer of architectures across different tasks/datasets, application scenarios and resources constraints (Elsken et al., 2019). Indeed, although alternative search spaces exist, cell-based extraordinary amount of research attention: based on preliminary survey,
NAS has received almost 80 % of the papers proposing new NAS methods published in ICLR, ICML and NEURIPS the past year show least one part of their major results in standard Differentiable Architecture Search (DARTS) sell-based spaces and/or highly related ones; and approx. 60% demonstrate results such spaces only (detailed in App C). It is fair to state that such cell-based spaces currently dominates. However, the lagging understanding of these architectures and the search space itself stands in stark contrast with the volume and pace of new search algorithms. The literature on understanding why this dominant search space works and comparing what different NAS methods have found is much more limited in depth and scope, with most existing works typically focusing exclusively on a few search methods or highlighting high-level patterns only (Shu al., 2020; Zela et al., 2020). We argue that strengthening such an understanding is crucial on multiple fronts, and the lack thereof concerning: first, studying a diverse set of architectures enables us to discover patterns shared across the search space, the foundation of comparison amongst search methods that heavily influences the resultant performances (Yang et al., 2020a): if the search space itself is flawed, designing and iterating new search methods it, which is typically computationally intensive, and unproductive. Conversely, understanding any pitfalls of the existing search spaces informs us on how to design better search spaces in the future, which is critical in advancing the goal of NAS in
be misleading
5 Work done while interning Huawei Noah's Ark Lab, London, UK.

---

Published as a conference paper at ICLR 2022
finding novel and nigh--peffrming architectures, not only in conventional CNNS but also in emerging NAS paradigms such as Transformers (which may also take the form of a cell-based design space). Second, opening the NAS black box enables us to distill the essence of the strong-performin architectures beneath their surface of complexity. Unlike manually designed architectures where usually designers attribute performance specific designs, currently owing the apparent complexity of the design space, the NAS architectures, while all discovered in similar or identical search space, are often compared in terms of final performance on standard dataset only (e.g. CIFAR- 10 test error). This could be problematic, as we do not necessarily understand what NAS has discovered that led the purported improvements, and the metric itself is a poor one on which external factors such as hyperparameter settings, variations in training/data augmentation protocols and even just noise could exert a greater influence than the architectural design itself (Yang et al., 2020a). However, by linking performance to specific designs, we could ascertain whether any performance differences stem from the architectures rather than the interfering factors.
NAS
We aim to address this problem by presenting a post-hoc analysis of the well werl-perforning architectures produced by technically diverse search methods. Specifically, tools to open the NAS black box by inspecting the good- and bad-performing architectures produced by a wide range of NAS search methods in the dominant DARTS search space. We find:
utilise explainable machine learning
Performances of architectures can often be disproportionately attributed to a small number of simple yet critical features that resemble known patterns in classical network designs;
Many designs almost universally adopted contribute to complexity but not performance:
The nominal complexity of the search spaces poorly reflects the actual diversity of the (high- performing) architectures discovered, the functional parts of which are often very similar despite the technical diversity in search methods and the sceming disparity in topology.
In fact, with few simple and human-interpretable constraints, almost any randomly sampled architec- ture can perform on par or exceed those produced by the state-of-the-art NAS methods over varying network sizes and datasets (CIFAR- 1 O//MAGENET). Ultimately, these findings prompt us to rethink the suitability of the current standard protocol in evaluating NAS and the capability to find truly novel architectures within the search space. We finally provide suggestions for prospective new search spaces inspired by these findings.
2 PRELIMINARIES
DARTS space (Fig 1) proposed by Liu et al. (2hch is in turn inspired by Zoph et al. (2018) and Pham et al. (2018)iis the most influ- ential search space in cell-based NAS: it takes a form of Directed Acyclic Graph (DAG), which features 2 inputs (connected to the output of two immediately preceding cells), output and 4 intermediate nodes. The operation (1--) on the (i,j)-th edge is selected from a set of candidate primitives A with size K = 7 to transform (1)), At each intermediate node, the output from the operations on all its predecessors are aggregated: x00)) = Σiej ((.()) And finally the out node concatenates all outputs from the intermediate nodes. As shown in Fig 1, the DARTS cell allows for up 14 edges/operations. However, to ensure that all intermediate nodes are connected in the computational graph, each intermediate node is constrained to have exactly 2 in-edges connected to it from 2 different preceding nodes. Lastly, it conventional search for two cells, namely normal on and reduce o, cells simultancously, with a, placed at 1/3 and 2/3 of the total depth of the networks
sop _op____o_33 (s3)
sep_con sep_conv_5xt sxd (s5)
dil_conv_3xt
dil_conv_5x55
skip connect (skip)
Insur
max, max_pool, _ool_3x3 (mp3)
avg_pool_3xx (ap3)
The DARTS cell. The solid black arrows de- note the concatenation at output which is fixed. The gray dashed arrows denote the 14 potential operation locations. In a valid DARTS cell, 8 of which are filled by one out the seven candidate primitives listed to the right, while the other 6 spots are disabled.
Figure I:
and on everywhere else. In total, there are I 7*((k+1)) 2 10 distinct cells without considering graph isomorphism, and since both on and o, are required to fully specify an architecture, there exist approx. (109)² = 10 distinct architectures (Liu et al., 2019). Other cells commonly used are almost invariably closely related to, and can be viewed as simplified or more complicated variants of the DARTS space. For example, the NAS-Bench-20 Bench-201 (NB201) (Dong & Yang, 2020) search space is simplified from the DARTS cell (detailed and analysed in App D). Other works have increased the number of intermediate nodes (Wang et al., 2021b), expanded the primitive pool & (Hundt et al., 2019) and/or relaxed other constraints (e.g. Shi et al. (2020) allow both incoming edges of the
2
2

---

Published as a conference paper at ICLR 2022
intermediate nodes to be from the same preceding nodes), but do not fundamentally differ from the (NB 101) (Ying et al., 2019a)
DARTS space. Additionally, search spaces like the feature cells where the operations are represented node features, although we believe that the way the cells are represented should not affect any findings we will demonstrate, as the DARTS/NB201 spaces can similarly be equivalently represented in feature-on-node style (Ru et al., 2021; Pham et al., 10) We do not experiment on NB 101 in the present paper, as it features CIFAR- 10 only, NAS-Bench-38e (NB301) (Siems et al., 2020), but the latter is much closer in
which is similar terms of size to a "realistic" search space that the community expects and is more amenable to one-shot methods which are currently mainstream in NAS.
3 OPERATION-LEVER ANALYSIS: REDUNDANCIES IN SEARCH SPACES
The cell-based NAS search space contains multiple sources of complexity: deciding both the specific wiring and operations on the edges; searching for cells independently, etc.; each expanding the search space combinatorially. While this complexity is argued to be necessary for the search space to be expressive for good-performing. novel architectures to be found, it is unknown whether all these sources of complexities are equally important, or whether the performance critically depend on some sub-features only. We argue that answering this question, and identifying such features, they are indeed present, is highly significant: it enables to separate the complexities that positively contribute to performances from those that do not, which could fundamentally affect the design of search methods. At the level of individual architectures, it helps us understand what NAS has truly discovered, by removing confounding factors and focusing on the key aspects of the architectures.
For findings to be generally applicable, we aim not to be specific to any search method; this requires to study a large of archi- tectures that are high-pu high-performing but techmically diverse in terms of the search methods that produce them. Fortunately, the train- ing set of NB301 (Siems et al., architecture performmneee pairs in the DARTS space using a combi- nation of random sampling and more than 10 state-of-the-arr yet technically diverse methods (detailed in App. could used for such an analysis: to build surrogate model that accurately pre- dicts architecture performance across the entire space. We primarily focus on the top-5% (2.589) architectures of the training since we overwhelmingly care about the good-performing architectures by definition in NAS, although we will show, the main findings hold true also for architectures found by methods not covered by NB301 and for other search spaces like the NB201 space. As shown in Fig 2, the top architectures are well-spread out in the search space and are well-separated by search methods, seemingly suggesting that the architectures discovered by different methods are diverse in characteristics. Lastly, the worse-performing cells could also be of interest, as any features observed could be the ones we would actively like to avoid, and we analyse them in App. A.
includes 50,000+
pc. darts
1pm
dmas
random
Figure 2: The top archs provide good coverage of the search space and are seemingly diverse: the t-SNE plot of the top 5% archs (colored markers; grouped by dif- ferent scarch methods. Details in App B.1) and randomly sampled archs in the DARTS search space (gray markers).
Operation Importance To untangle the influence of each part of the architecture, we introduce Operation Importance (01), which measures the incremental effect of the individual operations (the smallest possible features) to the overall performance. We quantify this via measuring the expected change in the performance by perturbing the type or wiring of the operation in question: considering edge-attributed cell a with edge eij currently assigned with primitive og, then the operation importance of on on that edge of cell a is given by:
W(a.es.==o Σ
Ol(a, eig ok) (a eag == on)
1
[v(am)] -v(a,,
(I)
where v(a:) denotes the validation accuracy or another appropriate performance metric of the fully- trained architecture induced by cell a. We are interested in measuring the importance of both the primitive choice and where the operation is located relative the entire cell, and we use N (a e.j = 0x) to denote a set of neighbour cells that differ to a only with the edge in question assigned with another primitive, G.jj A {ox]; I; or with the same primitive og but with one end
3

---

Published as a conference paper at ICLR 2022
10000
10000
0.004
0.004
Number of occurrencs
8000
Number of occurrennss
8000
63
Operativ Imporsere
Opentton importence
0.003
0.002
0.002
6000
6000
d5
skip
0.001
4000
4000
mp3
ap3
0.000
0.000
2000
2000
-9.001
0
Normal
Reduce
Normal
Reduce
-0.002
53
05
05 skpmppapp3
-0.002
05 skgmpaap3
(a) All operations
(b) Imporiant operations
(a) Normal cells
(b) Reduce cells
Figure 3: Distribution of (a) all and (b) important op- Figure 4: or distribution in (a) normal and (b) reduce erations by the primitive types of the top-performing cells. The important operations are shown outside the gray shaded area.
archiectures, organised by primitive type.
node of Cij being rewired to another node, subjected to any constraints in the search space. It is worth noting that OI is an instance of the Permulation Feature Importance (PFI) (Breiman, 2001; Fisher et al., 2019; Molnar, 2019). Given the categorical nature of the "features" in this case, we may enumerate all permutations conventional PFI does. An important operation by Eq (1) would therefore attributed an O1 of large magnitude in either direction, whereas an irrelevant one would have value of zero since altering it on expectation leads to no change in architecture performance. We compute the OT of each operation for the 2.589 architectures. To circumvent the computational challenge of having train all neighbour architectures of (which are outside the NB301 training set) from scratch to compute v(+), we use the performance prediction T-() from NB301. However, as will show, we validate all key findings by actually training some architectures to ensure that they are not artefacts of the statistical surrogate (training protocols detailed in App. B.2).
the edge in question instead of having to rely on random sampling as
Findings The most natural way to group the operations is by their primitive and cell (i.e. normal or reduce) types, and we show the main results Figs. and 4. In Fig. 3(b), we discretise the OT scores using the threshold 0.001 (0.ih)-hhich is similar to the observed noise standard deviation of the petter-performing architectures from NB301- to highlight the important operations with |O|| 2 0.001: these the ones we could more confidently assert to affect the architecture performance beyond noise effects. We summarise the key findings below:
(#1) Only fraction of operations is critical for good performance within cells: If all operations need to be fully specified for good performance (i.e., with both the primitive choice and the specific wiring determined), then perturbing any of them should lead significant performance deterioration. However, this is clearly not the case in practice: comparing Fig. 3(a) and (b), we observe that only fraction of the operations important based our definition.
test ace 1%6)
Most impt
Least impt
To verify this directly beyond predicted performances, we randomly select 30 architectures from the top 5% training set. Within each cell, we sort their 16 operations by their OI in both ascending and descending orders. We then successively disable the operations by zeroing them, and train the resulting architectures with increasing number of operations disabled from scratch' until only half of the active operations remain (Fig. 5). The results largely confirms our findings and shows that the O1, although computed via predicted performance, is accurate in representing the ground-truth importance of the operations. On average, we need to disable 6 low-OI operations to see a statistically significant drop in performance, and almost half of the operations to match the effect of disabling just high-01 ones. On the other hand, disabling the high-01 operations quickly reduce the performance and in some cases stall the training altogether. Noting that the overall standard deviation of the NB301 training set is just 0.8%, the drop in performance is quite dramatic.
Number of operations disabled
Figure 5: Ground- change in accuracy by successively dis- abling the most/least important ops, ordered by their O1. Medians and interquartile ranges shown; stars denote that the drop in ac- curacy is significant p S 0.01 in the Wilcoxon signed-rank test.
(#2) Reduce cells are relatively unimportant for good performance: Searching independently for reduce cells scale the search space quadratically, but Fig. 3(b) shows that they contain much fewer important operations, and Fig. 4 shows that the OT distribution across all primitives are centered close to zero in reduce cells: the reduce cell is therefore less important to the architecture performance. To verify this, we draw another 30 random architectures. For each of the them, we construct and train from scratch the original architecture and 4 derived ones, with (a) reduce cell set identical to normal
Note that we may not obtain NB301 performance prediction on these architectures, NB301 requires all 16 operations be enabled with valid primitives.
4

---

Published as a conference paper at ICLR 2022
cell. (b) reduce cell with all operations set to parameterless skip connections, (c) normal cell set identical to reduce cell and (d) normal cell with operations set to skip connections. Setting the reduce cell to be identical to the normal cell leads to no significant change in performance, while the reverse is not true (Fig. 6). A more extreme example is that while setting cells to consist of skip connections only is unsurprisingly sub-optimal in both cases, doing so on the reduce cells harms the performance much less. This suggests that while searching separately for reduce cells are well-motivated, the current design, which places much fewer reduce cells than normal cells in the overall architecture yet treats them equally during search, might be a sub-optimal trade-off; and searching two separate cells may yield little benefits over the strategy of simply using the same searching rule and applying on both normal and reduce cells.
(#3) Different primitives have vastly different importance profiles with many of them redundant: The set of candidate primitives A consists of operators that are known to be useful in manually- designed architectures, with the expectation that they should also be,
0
Test errar (%)
to varying degrees, useful to NAS. However, this is clearly not the case: while it is already known that some primitives are favoured more by certain search algorithms (Zela et al., 2020), the observed discrepancy in the relative importance of the primitives is, in fact, more extreme: the normal cells (which are also the important cells by Finding #2) across the entire spectrum of good performing archi- tectures overwhelmingly favour only out of possible primitives: separable convolutions and skip connection (Fig. 3())). Even when the remaining primitives are occasionally selected, they are almost never important (Fig. 3(b)). This is also observed in Fig. 4(a) which shows that they have distributions of OI close to O. As we will show later in Sec. 4, we could essentially remove these primitives from A without impacting the performances. Even within the 3 favoured primitives, there a significant amount of variation. First, compar- ing Figs ((a) and (b), sk kips, when present in good architectures, are very likely to be important. We also note that the distribution of OI of skip has a higher variance these suggest that the performance of an architecture is highly sensitive towards the specific locations and patterns of skip connections. detailed study of which we defer to Sec. 4. On the other hand, while both separable convolutions (s and s5) are highly over-represented in the gorf-perg architectures, it seems that they are less important than skip. A possible explanation is that while their presence is required for good performance, their exact locations in the cell matter less, which we again verify in See. 4. Increasingly we are interested in multi-objectives (e.g. maximising performance while minimising costs); we show that even accounting for this, redundant primitives, especially pooling, remain largely redundant (App. G).
original
rede-nor nere-red
rede-skip
none-skip
Figure 6: Ground-truth test er- rors (i.e. not predicted by NB301) of the original archs (original), archs with reduce cells set identical their nor- mal cells (red<-nor)in) Vnormal cells set identical to their reduce cells (nor<-red) and archs with normal/reduce cells fully replaced by skip connections fhorr-skip/zeds-an
* denotes that the performance dis- tribution significantly differs from original at p S 0.01 the Wilcoxon signed rank test.
The findings confirm that both the search space and the cells contain various redundan- cies that increase the search complexity but do not actually contribute much to performance; and that good performance most often does not depend on an entire cell but a few key features and primitives in both individual cells and the search space. This clearly shows that the search space design can be further optimised, but consequently, many beliefs often ingrained in existing search methods can also be sub-optimal or unnecessary. For example, barring a few exceptions (Xie ct al., 2019a; You et al., 2020; Ru et al., 2020; Wan et al., 2022), the overwhelming majority of the current approaches aims to search for a single, fully deterministic architecture, and this often results in dige-iiimesional vector encoding of the cells (e.g. the path encoding of DARTS cell in White et al. (2021) is > 10 dimensions without truncation). This affects the performance in general (White et al., 2020a) and impedes methods that suffer from curse of dimensionality, such as Gaussian Processes, in particular. However, exact encoding could be in fact unnecessary if good performance simply hinges upon only a few key designs while the rest does not matter as much, and finding relevant oowddimensional, approximate representations could be beneficial instead.
Discussions
4 SUBGRAPH-LEVEI ANALYSIS: ARE WE TRULY FINDING NOVEL CELLS?
Sec. 3 demonstrates the presence of critical sub-features within good performing architectures. In this section we aim to find what they actually are and whether there are commonalities amongst the
5

---

Published as a conference paper at ICLR 2022
No.
#
Support
Support
Ratio
edges
in impt
in
skip
5
4
0.0815
0.000386
231
0.0672
0,000772
3 0.0579
0.000772
75.0
10
4
4
0.0556 3
0.000772
72.0
0.0745 3 0.219
indie1
1n
57
In 1822 skpp
42
63
6
3 0.239
0.00579
0.00425
41.3
51.6
0.215
9
3 0.188
0,00888
21.3
10
0.103
0.00541
19.1
11
2 0.572
0.0339
16.8
skip
2 skip
GEL sEip
12
2
0.141
0.336
0.00927
0,0220
15.2
14
3
0.0560
0.00386
14.5
15
4
3
0.0734
0.00541
13.6
Figure 7 & Table I: Frequent subgraphs in the good-performing architectures ranked by ratio of supports and their properties. Almost all subgraphs feature skip residual links with additional connections with I or more sep_convs and neither di convs other parameterless operations.
architectures found by technically diverse methods. Towards this goal, operation levell analysis is insufficient as the performance of neural networks also depends on the architecture topology and graph properties of the wiring between the operations (Xie et al., 2019a; Ru et 2020).
Frequent Subgraph Mining (FSM) FSM aims to "to extract all the frequent subgraphs, in a given data set, whose occurrence counts are above a specified threshold" (Jiang al., 2013). This is immensely useful for our use-case, as any frequent subgraphs mined on the architectures represented by DAGS would naturally represent the interesting recurring structures in the good-performing architectures, and subgraphs are also widely used for generating explanations (Ying et al., 2019b). In our specific case, we 1) convert the computing graphs corresponding to the topology of the same set of top-periien pop-performing architectures in Sec. 3 into DAGS, 2) within each DAG, we retain only the important operations defined in Sec 3 and 3) run an adapted version of the gSpan algorithm (Yan & Han, 2002) for DAGS the set of all architecture cell graphs (Gi, ..., GT) } to identify set of the most frequent subgraphs G "of....,g',, Ayh where each subgraph must have minimum support Sig) of 0.05:
(8(g4)) ) o Vol G where s(g!) (G C CG // T
(2)
One caveat with support is that it favours simpler subgraphs, which more likely to be present "by nature". To account for this bias, we measure the significance of these subgraphs over null reference using the ratio between supports of G and the reference. The readers referred App. I for detailed explanations.
Findings (#4) Functional parts of many good-pen moodppeforrinn archi- tectures are structurally similar to each other and to elements of classical architectures. We show the top subgraphs in terms of the ratio of supports in Fig. 7, and an immediate insight is that the top frequent subgraphs representing the common traits across the entire good-performing region of the search space are highly over- represented over the reference and non non-diverse: almost all subgraphs can be characterised with skip connections forming residual links between one or both input nodes with an operation node, combined with different number and/or sizes of separable convolutions. In fact, we find that this ResNet-style residual link is present in 98. 58.5% (2,815) of the top 2,859 architectures (as a comparison, if we sample randomly, only approximately half of the architectures are expected to contain this feature). With reference to Fig. 8, the residual links drive the importance of skip in Fig. 3. This suggests that skip connections do not just benefit optimisation of NAS supernets but also actively contribute generalisation if they posit as residual connections. The propensity of certain NAS methods of collapsing into cells almost entirely consisting of skip well-know with many possible explanations and remedies, but here we provide an alter- native perspective independent of search methods: more fundamentally, skip is the only primitive whose exact position greatly impacts the performances both positive and negative directions and thus it is more difficult for search methods learn such relation precisely.
0.008
0.006
0.004
Opanation
0.002
0.000
-0.002
others
Figure 8: skips are only use- ful when they form residual links: in0 and inl denote the residual links formed with either inputs, others denote the skip connec- tions not forming residual links and all is the overall distribution of oi of skip connections.
The consensus in preferring the aforementioned pattern also extends beyond the training set of NB301: with reference to Fig. 9, we select some of the architectures produced by the most recent works that are not represented in the NB301 training set, and it is clear that despite the different

---

Published as a conference paper at ICLR 2022
D
White et al. (2021) Chen et al. (2021b) (c) Li al. (2021)
(d) Ru al. (2021) (e) Wang al. (2021e) (i) Chen al. (2021a)
DARTS_ PT and TE-NAS NAS) architectures with the important operations highlighted (the connections to output are omitted since they are all identical across the DARTS search space). Note all cases considered are consistent with the residual link + separable convolution patterns identified, even though the cells and search methods are very different and except for BANANAS, none of the methods here was used to generate the NB301 training set.
Figure 9: Normal cells of various SoTA (left right: BANANAS. DRNAS, GAEA,
search strategies, functional parts of resulting architectures are all characterised by the this pattern of residual connections and separable convolutions, a combination already well-known and well-used both in parts and in sum in successful manually designed networks (e.g. Xception (Chollet, 2017) uses both ingradients). In this sense, many of the existing NAS methods might not have discovered much more novel architectures beyond what we already know; the functional parts of many SoTA NAS architectures could be regarded as variations of the classical architectures, whereas the apparent diversity like the one shown in Fig. 2 is often caused by differences in the non-functional parts of the architectures that in fact minimally influence the performances.
Generating SoTA architectures We showed that many NAS architectures share similar traits, but a stronger test is whether these simple patterns alone are sufficient for good performance. We con- struct architectures simply by random sampling, but with 2 constraints, without additional search:
8.5
Actual tast 1r
7.5
Predicted hest
6.5
6.0
1. Normals cell must contain residual link: for ar- chitecture generation, we simply manually wire
2 skips from both inputs to intermediate node
(0) Predicted
PrinSkip
Random Skip
(b) Actual
Prim PrimSkip
0 (Skip constraint);
Figure 10: Distribution of (a) NB301 predicted and (b) actual test error archs sampled. Random: ran- dom archs without constraints; Skip: archs with resid- ual links and otherwise randomly sampled; Prim: random archs using (s3, s.,, skí skip) only. Prim- Skip: archs satisfying both Skip and Prim.
2. The other operations are selected from {s3, s5) only, with all other primitives removed (Prim constraint).
While it takes a thorough analysis to study the pat- terns, the constraints which encode our findings themselves are simple, numan-interrreetaa specifying exact wiring; Prim simply constrains sampling to a smaller subspace). We then sample 100 architectures within both constraints with the same rule for both normal and reduce cells and report their predicted test errors in Fig 10(a). To ensure that we are not biased by the NB301 surrogate, we actually train 30 of the 100 architectures from scratch (protocols specified in App. B.2) and report results in Fig 10(b). To verify the relative importance of each constraint, we also sample the same number of architectures with no constraints or with either constraint activated. We note that both constraints effectively narrow the spread of both predicted and actual test errors, with almost any architecture in the PrimSkip group performing similarly to the SoTA only 11 of the training set of NB301 perform better than the mean predicted test error of the PrimSkip group (5.24%) in Fig 10(a), while only 5% perform better than the worst (5.46%.. Apart from the two constraints, the architectures produced are rather varied otherwise in terms of depth/width and exact wiring (see App. E) this shows that the two moderate constraints already determine the performance to great extent, potentially eclipsing other factors previously believed to influence performance. We believe that it might even be possible to fully construct architectures manually from the identified patterns to achieve better results, but the main purpose of this experiment is to show that we may narrowly constrain performance to a very competitive range using very few rules without exactly specifying the cells, instead of aiming for the absolute best architecture in an already noisy search space. Lastly, we analyse NB201 space similarly in App. and very similar findings hold.
and moderate (note that only Skip is a "hard" constraint
Large architectures We have so far followed the standard NB301 training protocol featuring smaller architectures trained with fewer (100) epochs, generalisation performance on which does not necessarily always transfer to larger architectures (Yang et al., 2020a: Shu et al., 2020). Since the computational cost is much larger, here we first evaluate on PrimSkip architectures from Sec. 4 with different width/depth profiles, but stack it into a larger architectures and train longer to make the results comparable those reported the literature. To ensure that the results are completely comparable,
7

---

Published as a conference paper at ICLR 2022
Table 2:
Test error of the state-of-tee of-te-of-the-art ahe- architectures CIFAR- 10 and IMAGENET (mobile setting).
CIFAR- 10. All bavelines re- ev-allluated using procedure (b) ImageNet. All baselines are taken from original papers App. B.2 to ensure the results are completely comparable.
evaluation is too costly in this case.
Archiiecture
Top- I test ervre (5) Original
Edit dist.
Architecture
Test crtur (%)
Params (M)
Edited
Top-1
Top-5
DARTS²2 (Liu al., 2019)
2.44
2.36 -0.08)
DARTS/2 (Lin et al., 2019)
26.7
8.7
4.7
BANANAS (White et al., 2021)
2.39
2.12(=0.000)
SNAS (Xie et al., 20196)
21.3
9.2
4.3
DINAS (Chen et al., 2021b)
2:27
2.31
GDAS (Dong & Ying. 2020)
8.5
5-3
GAEA al., 20211
2.31
2.18( (113)
DeNAS' (Chen et al., 2021b)
24.2
7.3
5.2
NAS LLS-BOWLIIE (Ru et 2021)
2.33
2:23: -0.10)
GAEACIO) (Li ct 2021)
21.3
1.3
5.3
NoisyDARTS (Chu et. 2020)
2.57
2.42. -0.15)
GAEAAlmgeNeu (Li 2021)
7.3
5.6
SGAS_PT (Wang at., 2021c)
SDARTS_ PT (Wang et al. 2021e)
DARTS PT (Wang et al., 2021c]
2.16
2.92
2:33
2.36 -D.10)
2:35i +0.02)
2.18( -0.1))
PC-DART SclnoeeS(
PC- (CCDDARTICI)) (Ku et al., 2020)
PIDARTS (Chen at., 2019)
20120)
24.4
26.1
7.3
7.8
7-4
5.3
4.8
5.3
PrimSkip Arch
21.4
7-4
5.7
PrimSkip Arch
2:27
PrimSkip Arch 2
23.9
7.0
3.7
PrimSkip Arch
2.20
"i scarched dincelly on ImageNet.
on CIFAR-10 10 experiments we do not simply take the baseline results from the original papers; instead, we obtain the cell specifications provided in some of the most recent papers (see App. E for detailed specifications), re-train each from scratch using a standardised setup (See App. B.3 for details), and show the performance in the "Original" column of Table 2a. Recognising that the performance on CIFAR-10 is usually quite noisy (std dev around 0.05 0.1%). the sampled architectures perform at least on par with the SoTA architectures produced from much more sophisticated search algorithms. To further verify our findings, we conduct an additional experiment where we edit the SoTA ar- chitectures minimally to make them comply to the PrimSkip constraints: whenever cell contains primitives outside (s3, , s5, sk skip), we replace them with ones that are in this set, and we always set the reduce cell to be identical to the normal cell (see App. E for detailed specifications of the architectures). We also create residual links if they not present, and replace non non-residual skips with s / s5 between operations, if any; we do not alter any wiring. Most architectures are already close to conforming to the constraints, so the number of edits required is often small (edit distances are under "Edit dist." " column in Table 2a); in fact, the GAEA cell is already fully-compliant and we only replace its reduce cell with the normal cell). We show the test errors of the edited architectures along with the change from the original ones in "Edited" column of Table 2a: the edits result in an improvement in test error up to 0.44% in 6/9 cases, and even where test errors increase after the edits, the differences are marginal and probably within margins of error. This shows that at least for the architectures we consider, the SoTA architectures can all be consistently explained by the same simple pattern identified. We finally train the same sampled PrimSkip architectures on ImageNet using a training protocol adopted in the literature (App. B.3) and the results are shown in Table 2b. Accounting for the estimated evaluation noise (most NAS papers do not run ImageNet experiments with multiple seeds, but comparable works like Xie et al. (2019a); Goyal et al. (2017) estimate a noise standard deviation of 0.2 0.5% in Top-1 error), it is fair to say that both PrimSkip architectures perform on par to, if not better than, the SoTA, even though some of the SoTA architectures are searched on ImageNet directly, an extremely expensive procedure in terms of computational costs.
Discussions We find that the despite the different search methods and the belief that the search space contains diverse solutions, the key features of many top architectures in the DARTS (and NB201) space are largely similar to each other, and may collectively viewed as variants to classical architectures. This suggests a gap between the apparent and effective diversity of the search space, potentially explaining the discrepancy between the huge search space and the small performance variability. We also show highly complicated So methods fail to significantly outperform random search with few mild constraints, further demonstrating that it is these simple traits, and not other complexities, that drive the performance. Consequently, we argue that we should rethink the role that existing cell-based search spaces play as the key (and sometimes the only) venue on which the search methods develop and iterate. While it is reassuring that we find elements known to perform well, we should not over-rely on such search spaces but should continuously improve on them. Also, while we do not rule out the possibility that there could be other wrod-performing architectures not represented by the patterns identified, it is doubtful whether the search space, while nominally huge, truly contains novel and performant architectures beyond our knowledge.
5 RELATED WORKS
There are multiple previous works that also aim to explain and/or find patterns in cell-based NAS: Shu et al. (2020) find search methods in the DARTS space to favour shallow and wide cells but conclude they do not necessarily generalise better, and hence the pattern does not explain performances. Ru et al. (2021) also use subgraphs to explain performances, but only consider first-order Weisfeiler-Lehmmnn
8

---

Published as a conference paper at ICLR 2022
(WL) features which could be overly restrictive (note that most subgraphs we find in Fig. 7 are not limited to 1-WL features) and specific to the search method proposed. Zela et al. (2020) account for failure mode of differentiable NAS, but ultimately focus while the current work is search method-agnostic. On a search space level, a closely related work is use extensively, but they mainly identify problems, not
family of related search methods
Yang et al. (2020a), findings from whom explanations; Xie et al. (2019a), Ru et al. (2020) and You et al. (2020) relate performances with graph theoric properties of networks, but it is unclear to what extent these apply to standard cell-based NAS as the search spaces considered are significantly different (e.g. they typically feature much fewer primitive choices). Lastly, in constructing NAS benchmarks, Dong & Yang (2020); Siems et al. (2020); Ying et al. (2019a) have also provided various insights and patterns. but current work advances such understanding further via a comprehensive and experimentally validated investigation.
6 SUGGESTIONS FOR FUTURE NAS PRACTICES
We believe this work be useful as an investigation of the existing cell-based NAS as well to inspire future ones, not only on conventional CNNs but also emerging architectures like Transformers. On a search space level, we find a mismatch between the nominal and the effective complexity: complexities are as useful as they contribute to performance and novelty, and thus in a hypothetical new space, we should aim to be aware of these non-functional complexities, and not simply augment the number of primitives available and/or expanding the sizes of the cells. However, identifying such redundancies in a new search space is very challenging a- a-priori, but fortunately the analysis tools used in this paper are model-agnostic, and thus could be applied to any new search space candidates. Also, while we use the NB301 predictors which train a huge number of architectures to ensure the findings representative
possible, we show in App. F that combined with an appropriate surrogate regression model, we may reproduce most findings by training as few as 200 architectures (or 0.4% of the full training set); this suggests that the techniques used could also be cost-effective tools to inspect new search spaces. Another under-explored possibility would be iterative yearch-and and-prune at the search space level, as opposed the architecture level which relatively well studied. Using the tools and metries we introduced to incrementally grow the search space from simpler structures and prune out those redundant ones in a principled manner.
Notwithstanding the issues identified, we believe that the cell-based design paradigm remains valuable for proper benchmarking and comparison of NAS methods, but the many woes could be due to the over-engineered cells and the under-engineered macro-connections often fixed in way that is heavily borrowed from classical networks. Here we identify three promising directions that would hopefully resolve or at least alleviate some of the problems identified: Firstly, could simplify the cells but relax the constraints on how different cells are connected in the search space. Secondly, as discussed, we might be implicitly biased to favour architectures that resemble known architectures, preventing NAS to discover truly novel architectures. A possible solution is to search on a more fundamental level free of the bias of existing designs such as the paradigm championed by Real et al. (2020). Lastly, considering how much benchmarks have democratised and popularised NAS research, there is also a need for NAS benchmarks beyond simple cell-based spaces. The readers are referred to App. J for a more detailed discussions on our suggestions for future NAS researchers.
7 CONCLUSION
We present a post-hoc analysis of architectures in the most popular cell-based search spaces. We find mismatch between the nominal the effective complexity, as many pood-performing architectures, despite discovered by very different search methods, share similar traits. We also find many redundant design options, as performances of the architectures disproportionately depend on certain patterns while the rest are often irrelevant. We conclude that like the rapidly iterating search methods, the search spaces also need to evolve to match the progress of NAS and we provide suggestions based on the main findings in the paper, the latter of which also form some of the most evident directions of future work. Lastly, while cell-based NAS focusing on image classification is currently mainstream and the present paper focuses exclusively on such, alternative spaces and/or tasks exist (Howard et al., 2019; Wu et al., 2019; Cai et al., 2019; Duan et al., 2021; Tu et al., 2021), 1).. By adopting a macro focusing
search framework issues identified. Since the tools presented in the paper are largely search space- aggestin,, a further future direction would also be to extend some of the analyses to them.
alternative task, they might be less subjected to some of the
9

---

Published as a conference paper at ICLR 2022
ETHICS STATEMENT
While we do not see immediate ethical repercussions of our work in particular, we believe that the general topics of neural architecture search and automated machine learning (AutoML) that our work focuses on do involve broader interests at stake. On the positive side, gaining more knowledge on AutoML and NAS could lead to improved democratisation of deep learning models to non-experts as they automate machine learning pipelines that previously could require immense human expertise. On the negative side, it is worth noting that NAS and AutoMI. (including some of our suggestions for future directions in Sec. 6) are often computationally expensive. Advancement in AutoML and NAS might prompt more practitioners to use them instead of off-the-shelf models, which could lead to increased monetary and environment ethically neural, there is possibility for them be misused in ethically dubious ways. We believe that ultimately the practitioners and researchers have to make the judgement call to ensure that ethical use of the technologies in their domain of application is always ensured.
costs, Finally, while AutoML and NAS themselves are
REPRODUCIBILITY STATEMENT
The implementations details to reproduce the major experimental results of the paper are in- cluded in App. B. The code is open-sourced at pettps:/githhn com/ xingchenwan/ cell-based NAS- MAAS-analysis
REFERENCES
James Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter optimization. Advances neural information processing systems, 24, 2011.
Leo Breiman. Random forests. Machine learning, 45(1):5-32, 2001.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. International Conference on Learning Representations (ICLR), 2019.
Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: theoretically inspired perspective. arXiv preprint arXiv:2102. 1535, 2021a.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. Drnas: Dirichlet neural architecture search. International Conference Learning Representutions (ICLR), 2021b.
Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap hetween search and evaluation. In Proceedings of the IREF/CVF International Conference Computer Vision, pp. 1294-1303, 2019.
François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1251-1258, 2017.
Xiangxiang Chu, Zhang, and Xudong Li. Noisy differentiable architecture search. arXiv preprint (xXiv:2005.03566 2020.
Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. (DARTS)-: Robustly step- ping out of performance collapse without indicators. In International Conference on Learning Representations, 2021. URL https: /ww./roeeeeeeeeeeeeeeeeeeeeeeeee ew. net forum? d- KLH L...II.
Tom Den Outllaner, Arkadiy Dushatskiy. Marco Virgolin, and Peter AN Bosman. Local search is remarkably strong baseline for neural architecture search. In International Conference Evolutionary Multi-Criten Optimization, pp. 465 479. Springer, 2021.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. International Conference on Learning Representations (ICLR), 2020.
Yawen Duan, Xin Chen, Hang Xu, Zewei Chen, Xiaodan Liang, Tong Zhang, and Zhenguo Li. Transnas-bench- 101: Improving transferability and generalizability of cross-task neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 5251 1-560, 2021.
Lukasz Dudziak, Thomas Chau, Mohamed S Abdelfattah, Royson Lee. Hyeji Kim, and Nicholas D Lane. Brp-nas: Prediction pradettion-based nas using gens, Advances in Neural Information Processing Systems (NeurIPS) 33, 2020.
10

---

Published as a conference paper at ICLR 2022
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. The Journal of Machine Learning Researck, 20(1):199722017, 2019.
Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, hut many useful: Learning variable's importance by studying an entire class of prediction models simultaneously. J. Mach. Learn. Res., 20(177):1-81, 2019.
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He. Accurate, large minibatch sgd: Training imagenet in hour, arXiv preprint arXiv: 001./0066..2222 02677, 2017.
Andrew Howard, Mark Sandler, Grace Chu, Liang- Chich Chen, Bo Chen, Mingxing Tan, Weijun Wang. Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1314 1324, 2019.
Andrew Hundt, Varun Jain, and Gregory Hager. sharpdarts: Faster and accurate differentiable architecture search. arXiv preprint VrXii::103.09900 2019.
Chuntao Jiang, Frans Coenen, and Michele Zito. A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review, 28(1) 28(5):5--105, 2013.
Hayeon Lee, Eunyoung Hyung, and Sung Ju Hwang. Rapid neural architecture search by learning to generate graphs from datasets. In International Conference Learning Representations, 2021. URL https: // //openreview net /tt//oouuue wwr.mrruuioomm wtw.uu//ioooooouuuuoogoooo
Liam Li, Mikhail Khodak, Maria-Florina Balcan, and Ameet Talwalkar. Geometry-aware gradient algorithms for neural architecture search. International Conference on Learning Representations (ICLR), 2021.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. International
Conference on Learning Representations (ICLR), 2019.
Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tin-Yan Liu. Semi-supervised neural architecture search. arXiv preprint arXiv:2002. 10389, 2020.
Christoph Molnar. Interpretable Machine Learning. 2019. https://christtpphe g tutttuu thub, io/ Enterpretable-mi--oon
Niv Nayman, Yonathan Aflalo, Asaf Noy, and Lihi Zelnik-Mani Hardcore-nas: Hard constrained differentiable neural architecture search. International Conference on Machine Learning, 2021.
Vu Nguyen, Tam Le, Makoto Yamada, and Michael A Osbome. Optimal transport kernels for sequential and parallel neural architecture search. In International Conference on Machine Learning, pp. 8084-8095. PMLR, 2021.
Hieu Pham, Melody Guan, Barret Zoph. Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In International Conference on Machine Learning, pp.
PMLR, 2018.
Kenneth Price, Rainer M Storn, and Jouni A Lampinen. Differential evolution: practical approach global optimization. Springer Science Business Media, 2006.
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, volume 33, pp. 4780-4789, 2019.
Esteban Real, Chen Liang, David So. and Quoe Le. Automl-zero: Evolving machine learning algorithms from scratch. In International Conference on Machine Learning, pp. 8007-8019. PMLR, 2020.
Binxin Ru, Pedro Esperanca, and Fabio Carlucci. Neural architecture generator optimization. Advances in Neural Information Processing Systems (NeurIPS) 33, 2020.
Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael Osborne. Interpretable neural architecture search via bayesian optimisation with weisfeiler- Ichman kernels. International Conference on Learning Representations (ICLR), 2021.
Han Shi, Renjie Pi, Hang Xu. Zhenguo Li, James T Kwok, and Tong Zhang. Bridging the gap between sasple-based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 2020.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. International Conference on Learning Representations (ICLR), 2020.
11

---

Published as a conference paper at ICLR 2022
Julien Siems, Lucas Zimmer, Arber Zela, Jovita Lukasik, Margret Keuper, and Frank Hutter. Nas-bench-301 and the case for surrogate benchmarks for neural architecture search. arXiv preprint arXiv:2008 09777, 2020.
Xiu Su, Shan You, Tao Huang, Fei Wang, Chen Qian, Changshui 7hang, and Chang Xu. Locally free weight sharing for network width search. International Conference on Learning Representations, 2021a.
Xiu Su, Shan You, Mingkai Zheng, Fei Wang, Chen Qian, Changshui Zhang, and Chang Xu. K-shot nas: Learnable weight-sharing for nas with k-shot supernets. International Conference on Machine Learning. 2021b.
Renbo Tu, Mikhail Khodak, Nicholas Roberts, and Ameet Talwalkar, Nas-bench-360: Benchmarking diverse tasks for neural architecture search. arXiv preprint arXiv:21 2021.
Xingehen Wan, Binxin Ru, Pedro M Esparança, and Fabio Maria Carlucci. Approximate neural architecture search via operation distribution learning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pp. 2377-2386, 2022.
Dilin Wang. Chengyue Gong, Meng Li, Qiang Liu, and Vikas Chandra. Alphanet: Improved training of supemet with alpha-divergence. International Conference Machine Learning, 2021a.
Jiaxing Wang, Haoli Bai, Jiaxiang Wu, Xupeng Shi, Junzhou Huang, Irwin King, Michael Lyu, and Jian Cheng. Revisiting parameter sharing for automatic neural channel number search. Advances in Neural Information Processing Systems, 33, 2020.
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian, Sample-efficient neural architecture search by learning action space. IEEE Transactions on Pattern Andyssis and Machine Intelligence, 2021b.
Ruochen Wang, Minhao Cheng, Xiangning Chen, Xiaocheng Tang, and Cho-Jui Hsieh. Rethinking architecture selection in differentiable nas. International Conference on Leurning Representations (ICLR), 2021c
Colin White, Willie Neiswanger, Sam Nolen, and Yash Savani. A study on encodings for neural architecture search. Advances in Neural Information Processing Systems, 2020a.
Colin White, Sam Nolen, and Yash Savani. Local search is state of the art for nas benchmarks. arXiv preprint arXiv:2005.00 02960, 2020b.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. AAAI Conference on Artificial Intelligence, 1()), 2021.
Bichen Wu, Xiaoliang Dai. Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pp. 10734-10742, 2019.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 1284-1293, 1293, 2019a.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. International Conference on Learning Representations (ICLR), 2019b.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi. Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-effiiient architecture search. International Conference on Learning Representations (ICLR), 2020.
Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? Advances in Neural Information Processing Systems, 33, 2020.
Shen Yan, Colin White, Yash Savani, and Frank Hutter. Nas-hench-x11 and the power of learning curves. Neural Information Processing Systems (NeurIPS), 2021.
Xifeng Yan and Jiawei Han. gspan: Graph-based substructure pattern mining. In 2002 IEEE International Conference on Data Mining, 2002. Proceedings. pp. 721 -244. IEEE, 2002.
Antoine Yang, Pedro M Esperança, and Fabio M Carlucci. Nas evaluation is frustratingly hard. International Conference on Learning Representations (ICLR), 2020a.
Yibo Yang. Hongyang Li, Shan You, Fei Wang, Chen Qian, and Zhouchen Lin. Ista-nas: Efficient and consistent neural architecture search by sparse coding. Advances in Neural Information Processing Systems (NeurIPS) 33, 2020b.
12

---

Published as a conference paper at ICLR 2022
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-101. Towards reproducible neural architecture scarch. International Conference on Machine Learning, pp. -114. PMLR, 2019a.
Rex Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitaik, and Jure Leskovec. Gun explainer: A tool post-hoc explanation of graph neural networks. arXiv preprint /903, 038844 2019b.
Jiaxuan You, Jure Leskovee, Kaiming He, and Saining Xie. Graph structure neural networks. International Conference on Machine Learning, pp. 10881-108800 PMLR, 2020.
Arber Zela, Thomas Elsken, Tonmoy Saikia, Yassine Marrakchi, Thomas Brox, and Frank Hutter. Understanding and robustifying differentiable architecture search. International Conference on Learning Representations (ICLR), 2020.
Hongyi Zhang, Moustapha Cisse. Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint 1rXiv:1710.09412. 2017.
Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, Zongyuan Ge, and Steven Su. Differentiable neural architecture search in equivalent space with exploration enhancement. Advances in Neural Information Processing Systems, 33, 2020.
Yiyang Zhao, Linnan Wang, Yuandong Tian, Rodrigo Fonseca, and Tian Guo. Few-shot neural architecture search. In International Conference Machine Learning, pp. 12707-12718, PMLR, 2021.
Pan Zhou, Caiming Xiong, Richard Socher, and Steven C. H. Hoi. Theory-inspired path- regularized differential network architecture search. Advances in Neural Information Processing Systems, 2020.
Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. arviv preprint 1rxiv:161.00157 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference computer vision and patlern recognition, pp.
8697-8710, 2018.
13

---

Published as a conference paper at ICLR 2022
APPENDICES
A ANALYSIS ON WORST-PERFORMING ARCHITECTURES
5000
0.000
0.010
Number of occurrences
Number of occureecce
5000
2000
oppeshion Impertance
0.005
4000
0.000
0.000
3000
3000
-9.005
-2.005
2000
2000
-0.000
-2.010
1000
1000
-0.015
Normal
Reduce
Normal
Reduce
-0.020
3kpmppapp
-0.020
appmp3ap3
(a) All operations
(b) Imporiant operations
(a) Normall cells
(b) Reduce cells
Figure 11: Distribution of (a) all and (b) important op-
Figure 12: fox-and-whisker plots showing the distri-
crations by the primitive type the worst-performing colls. The gray dashed line in (a) denotes the expected number of occurrences if the operations are uniformly sampled in each cell.
bution of the operations importance (a) normal and (b) reduce cells by primitive types. The important oper- ations by the dcfinition of the paper are shown outside the gray shaded area.
We also conduct operation-level analysis on the worst 5% performing architectures of the NB301 training data and the results are shown in Figs 11 and 12, and we find that both pooling operators almost never contribute to good performing architectures as shown in Sec 3, but they actively hurt performance in the poor architectures: from Fig 11, it is clear that the worst performing cells are both characterised by large number of pooling operators (Fig 1 (a) and a large number of important pooling operators actively degrading performance: this is unsurprising and also pointed out in the analysis in the original NB301 paper (Siems et al., 2020) as cells with a large number of pooling operations aggressively cause loss of information. Other than that, both dilated convolution operations remain rather neutral and the separable convolutions remain positive in operation importance even in poorly-pent porry-performing architectures. Skip connections in this case are quite negative in general but still have a very large spread - this could be either due to a large number skip connections in the cell which is known failure mode of many differentiable NAS algorithms Zela et al. (2020) that skip connections need to be paired with separable convolutions as shown in Fig 7 for positive effects, which is not the case in these poor architectures where separable convolutions
underrepresentee. We also repeat the subgraph-level analysis these architectures (Fig 13). An interesting insight is that the poorly performing subgraphs are much more "diverse" than the good ones, and the primitives in the two groups almost never overlap: the none of positive subgraphs in 7 contains (d3, d5, mp3, ap3), }. whereas none of the negative subgraphs contains ( (s3, s5). This shows that in the present search space the primitives are somewhat "separable" and the redundant primitives (d3, d5, mp3, ap3) may simply be discarded without affecting the resulting performances we argue this should not the case in a well-designed ideal search space. In principle, every primitive should be a building block that that potentially contribute to architectures positively at least in some cases.
B IMPLEMENTATION DETAILS
B.I DATA
We primarily use the data from the training set of the NB301 benchmark (Siems et al., 2020), available at the official repository at https://///t.... / l/ggttttn tht......................... com/ httm//uuomm//aaa///a/ /ttm///tt/m/mmmmme///0/0// /aa.beeccbnh..... To obtain sound performance surrogate over the entire DARTS search space, NB301 trains more than 50,000 architectures using the protocol listed in App B.2, and use the architectures and their corresponding test performance on CIFAR-10 as inputs and labels to train a number of surrogate models as performance predictors, including GIN, XGBoost and LGBoost (in this paper, we always use the XGBoost surrogate as is shown to be the best on balance according to Siems et al. (2020)). The architectures are produced from a number of technically diverse methods representing almost all mainstream genres of cell- based NAS like gradient-basse reinforcement learning and simpler methods like local search and random search: DARTS (Liu et al., 2019), DRNAS (Chen et al., 2021b), GDAS (Dong & Yang, 2020), reinforcement learning (RL) (Zoph & Lee, 2016), differential evolution (DE) (Price et al., 2006), DC_DARTS (Xu et al., 2020), Tree parzen
methods, Bayesian optimisation,
14

---

Published as a conference paper at ICLR 2022
mom
mpm
mop3
up3
mp3
mpp
indir1
mmp
Ingur2 20.3
op3
ing
mpaa
8
Ingur2
Ingut1
day
sp3
mp3
mpp
mp3
mp3
mp3
db
Figure 13: Frequent subgraphs in the good performing architectures ranked by ratio of supports between the important subgraphs and the reference and properties of the discovered frequent subgraphs in the worst performing architectures.
estimator (TPE) (Bergstra al., 2011), local search (L.S) (Den Ottelander et al., 2021; White et al., 2020b) and regularised evolution (RE) (Real et al., 2019).
B.2 TRAINING PROTOCOLS ON DARTS ARCHITECTURES
We exactly follow the NB301 protocols for all experiments involving architecture training (except for the larger architectures on CIFAR- 10 and ImageNet, which we outline below at App B.3). Specifically, we train architectures obtained from stacking the cells 8 times (8-layer architectures) with initial channel count of on the CIFAR- 10 dataset using the standard train/val split, and we use the hyperparameters below on a single NVIDIA Tesla V100 GPU:
Optimizer: SGD
Initial learning rate: 0.025
Final learning rate: 1e-8
Learning rate schedule: cosine annealing
Epochs: 100
Weight decay: 3e-4
Momentum: 0.9
Auxiliary tower: True
Auxliary weight: 0.4
Cutout: True
Cutout length: 16
Drop path probability: 0.2
Gradient clip:
Batch size: 96
Mixup: True
Mixup alpha: 0.2
B.3 EVALUATION PROTOCOLS ON DARTS ARCHITECTURES
For the evaluation, we use larger architectures obtained from stacking the cells 20 times (20-layer architectures) with initial channel count of 36 on the CIFAR-I0 dataset. The other hyperparameters (mostly consistent with those used in App B.2 except for the number of epochs trained) used are:
CIFAR-10
Optimizer: SGD
Initial learning rate: 0.025
Final learning rate: 1e-8
Learning rate schedule: cosine annealing
Epochs: 600
Weight decay: 3e-4
Momentum: 0.9
Auxiliary tower: True
Auxliary weight: 0.4
15

---

Published as a conference paper at ICLR 2022
Cutout: True
Cutout length: 16
Drop path probability: 0.2
Gradient clip: 5
Batch size: 96
Mixup: True
Mixup alpha: 0.2
This protocol is identical to the original DARTS protocol (Liu et al., 2019), with the only exception that be consistent with the NB301 protocol, we also incorporate the Mixup regularisation (Zhang et al.. 2017) during evaluation. This accounts for the fact that the accuracy reported in this paper is generally better than those reported the literature. However, as mentioned the main text, we re-train every architectures from the scratch, including the baselines, using the identical protocol listed above, instead of simply taking the numbers from the original papers. As result, no architecture has been given unfair advantage because of the more effective regularisation used in this paper. We also conduct all experiments on a single NVIDIA Tesla V100 GPU.
ImageNet On ImageNet, we use a protocol that is identical to Chen et al. (2021b). It is also almost identical to those used Xu et al. (2020); Chen et al. (2019); Liu et (2019) except for batch sizes (which depend on the availability of hardware; larger batch size is only available for parallel many-GPU setup) and the corresponding linear scaling learning rates. Specifically, we form 14-layer architectures with initial channel count of 48 using 8x NVIDIA Tesla V100 GPUs. Note that since we are unable to re-evaluate all the baselines using a standardised training protocols in this case due to the extreme computational cost, we works with the additional Mixup regularisation in CIFAR-10 disabled in the ImageNet experiments ensure the comparability of the results. The other hyperparameters are followed:
protocol that strietly adheres to the existing
Optimizer: SGD
Initial learning rate: 0.5
Learning rate schedule: linear annealing
Epochs: 250
Weight decay: 3e-5
Momentum: 0.9
Auxiliary Tower: True
Auxliary weight: 0.4
Cutout: True
Cutout length: 16
Drop path probability: 0
Gradient clip:
Label smoothing: 0.1
Mixup: False
Batch size:
C LIST OF REFERENCED PAPERS
We present the details covered our preliminary survey on the NAS search methods papers published in top machine learning conferences during the past year in Table
16

---

Published as a conference paper at ICLR 2022
Table 3:
A list of NAS methods papers (L.e. excluding, e.g. review benchmark papers) published in the past year top machine learning conferences. Cells-based means the work demonstrates at least one part of the major results in the DARTS cell-based search space and/or highly related ones (such as the various and/or those otherwise highly resemble DARTS), Cells-only means the works only demonstrate the results in aforementioned search space(s). Whenever paper not cell-based or cells-only, other spaces evaluated shows the alternative spaces the papers report results on. The list potentially incomplete, as we only select papers that explicitly mention NAS in the title and/or abstract.
Venue
Name
Reference
Cells based
Cells-only Other spaces evaluaaed
NeurIPS 2020
BRP ARP-NAS
Dudziak al. (2020)
NAGO
et al. (2020)
NAGO space
ISTA-NAS
Yang (2020b)
arch2vec
Yan et al. (2020)
White et (2020s)
PR-DARTS
Zhou al. (2020)
E'NAS
Zhang al. (2020)
APS
Wang et (2020)
Channel/width search
SemiNAS
Luo al. (2020)
MobileNet space
BONAS
Shi et al. (2020)
ICLR 2021
NAS-BOWL
Ru (2021)
DENAS
Chen al. (2021b)
GAEA
ei al. (2021)
DARTS-
Chu (2021)
TE-NAS
Chen et al. (2021a)
DARTS_PT PT, etc
Wang et al. (2021c)
MobileNet space
MetaD2A
Lee (2021)
MobileNet space Channel/width search
CafeNet
Su ct (2021a)
ICML 2021
BO-TWADPP
Nguyen et al. (2021)
AlphaNet
Wang al. (2021a)
MobileNet space
CATE
Wang et al. (2021a)
HardCoRe-NAS
Nayman al. (2021)
MobileNet space
K- K-Shot NAS
Su al. (2021h)
MobileNet Net space
Few-shot NAS
Zhao et al. (2021)
ProxylessNAS space, RNN, AutoGAN
Total
(79%)
(58 96)
D ANALYSIS ON
Fig 14 shows the NB201 search space, a popular NAS benchmark commonly used that is highly similar to the DARTS cell, but 1) only one cell (instead of two) is searched, 2) each cell is con- nected to its immediate preceding layer only, and 3) is with reduced set of primitives. Also, unlike the DARTS cell, all edges in the NB201 cell are enabled.
2
avg wwo.pool_Bco (ap3)
skip, connect (skrg)
conv. 1x2 (ct)
We also conduct brief analysis in similar manner to the main text on top 5% performing architectures on NB201 dataset, and we show the operation importance distribution of each primitive in Fig 15. We observe that due to the smaller cell size and the primitive set, the operations a NB201 cell is typically more important and the only redundant operations is ap3. We hypothesise that the reason is similar the DARTS search space as the manually specified macro connection between the cells already include pooling operations, rendering them unncessary within the cells.
The NB201 (Dong & Yang, 2020) cell. which is highly similar to the DARTS space but much simpler. All 6 locations (denoted by gray dashed arrows) are available for search, and each is filled by out of the four candidate primitives (or None, which disables the edge).
Figure 14:
The second experiment to conduct is verifying whether the NB201 search space the good performing cells are also characterised by the patterns we identified in Sec 4. To do so, we adapt the Skip and Prim constraints the NB201 space:
1. Skip constraint: in the NB201 search space, the only way to form a residual connection is to place skip edge 0 - (with reference to Fig 14.
2. Prim constraint: apart from the manually specified edge, all other operations are sampled from the reduced primitive set (c1, c3 consisting of convolutions only.
Similar to our procedure in Sec 4, we sample 50 architectures within each group (no constraint, either constraint and both constraints), and we show their test performance in Fig 16. It is also worth noting
17

---

Published as a conference paper at ICLR 2022
0.00
0.32
0.00
Qetttonn Insorbico
0.06
0.30
0.08
0.08
0.04
0.01
0.02
0.00
-0.01
2012
ap3
13
2815
403
CIFAR-10
(b) CTFAR100
(c) ImageNat1661
Figure 15: Box-and-whisker plots showing the distribution of the operation distribution in NB201 benchmark on (a) CIFAR-IO, (b) CIFAR-100 and (c) ImageNet16-122 datasets. The gray shaded areas denote noise standard deviation which differs each dataset.
that the ground-truth optimum each dataset is known in NB201 and accordingly marked in Fig 16. Differing from the observations in DARTS search space results, in this case Skip constraint alone does not impact the performance significantly, but again the PrimSkip group with both constraints activated perform
range very close the optimum: datasets, while different from each other, all belong to the PrimSkip group and are found by random sampling with fewer than 50 samples. This again confirms that our findings in the main text similarly generalise to NB201 I space.
fact, the optimal architectures in all
Test VICIFAR-10)
Test error (% (CIFAR- 100)
75
20
40
70
15
65
10
60
error
555
Random Skip Prim PrimSipp
Random Skip Prim PrimSiip
Random Skip Prim PrimSkpp
(a) CIFAR-10
(b) CIFARI00
(c) ImageNet16-120
Figure 16: Distribution of the test errors on (a) CIFAR-1O. (b) CIFAR-I00 100 and (c) ImageNet of NB201 architectures. Note that since NB201 tabular benchmark that exhaustively trains and evaluates all the architectures within search space, all errors reported here actual, not predicted.
E ARCHITECTURE SPECIFICATIONS
In this section, show the specifications of (a.k.a genotypes) the different architectures in the DARTS search space.
E. ORIGINAL AND EDITED GENOTYPES FROM BASELINE PAPERS
Here we show the genotypes original and edited (corresponding to the results in the "Fdited" column Table 2a) architectures (Fig. 17 24). all figures, "Normal" and "Reduce" denote the normal and reduce cells of the Original architectures where "Edited" denote the normal and reduce cells of the edited architectures (note that the edited architectures always have identical normal and reduce cells).
(b) Reduce
(a) Normal
(c) Edited
Figure 17: Genotypes of BANANAS architecture (White et al., 2021)
18

---

Published as a conference paper at ICLR 2022
(a) Normal
(b) Roduce
(c)
Figure 18: Genotypes of DRNAS architecture (Chen et al., 2021b)
(a) Normal
(b) Reduce
(c) Edited
Figure 19: Genotypes of GAEA architecture (Li et al., 2021). Note that the edited genotype is identical to the original normal genolype as is already compliant with both Prim Skip constraints.
(a) Normal
(b) Reduce
(c) Edited
Figure 20: Genotypes of NASBOWL architecture (Ru et al., 2021).
Normal
(b) Reduce
(c) Edited
Figure 21: Genotypes of NOISYDARTY architecture (Chu et al., 2020)
(b) Reduce
(a) Noemal
(c) Edited
Figure 22: Genotypes DARTS_PT architecture (Wang al., 2021c)
(a) Normal
(6) Edited
(b) Reduce
Figure 23: Genotypes of SDARTS_PP PTT architecture (Wang al., 2021c)
19

---

Published as a conference paper at ICLR 2022
Reduce
(a) Normal
(c) Edited
Figure 24: Genotypes SGAS architecture (Wang et al., 2021c)
E.2 RANDOM GENOTYPES SAMPLED IN THE PRIMŠKIP GROUP
We show some examples of the genotypes generated via the constrained random sampling in the PrimSkip group in Sec 4 in Fig 25, while the two architectures selected for the CIFAR- CIFAR-10/ImageN/ experiments the larger architectures is shown Figs 26 and 27.
skip connect
sep_conv
skip_conneet
3c
c_ c_
cony _33
sp.aen
sep_conv_3r _x33
[_]
2
0 [k-]
sep_conv_50 555
Sop_conv_55t
sep_conv_55t
[k-2
sp.oen 20
Ap.oszal
Xp.stex
AbLosrad
Figure 25: Some of the randomly sampled architectures in the PrimSkip group.
ovent
ep.coer_50
LIMI
(b) Reduce
(a) Normal
Figure 26: Randomly selected PrimSkip architccture experiments on the larger architectures
20

---

Published as a conference paper at ICLR 2022
1750
1750
0.004
0.004
Number of accureenes
1500
Number of occureecce
1500
Opeetton Importanee
0.001
Opertoon Imporance
0.007
1250
d3
0.002
0.002
1000
1000
skip
0.001
0.001
750
750
mp3
500
ap3
0.000
250
250
-0.001
-0.011
Normal
-0.002
23 55
63
65 app
-0.002
25
d5 akpmppapp
operations
(b) Imporiond operations
(a) Normal cells
(b) Reduce cells
Figure 28: Distribution of (a) all and (b) important operations by the primitive types according to the BA- NANAS surrogate. The gray dashed line in (a) denotes the expected number of occurrences if the operations are uniformly sampled.
Figure 29: Box plots showing the distribution of the operations importance in (a) normal and (b) reduce cells according the BANANAS surrogate. The important operations by the definition outside the gray shaded area.
paper are shown
C.AA
scp coe
(a) Normal
(b) Reduce
Figure 27: Randomly selected PrimSkip architecture 2 for the experiments on the larger architectures
F REPRODUCING RESULTS WITH LESS TRAINING DATA
In this section, we show that it is possible to reproduce many results in the paper using less than 0.4% of the data compared the full of more than 50,000 the NB301 surrogate, thereby motivating the use of the tools introduced in this paper as a generic, cost-effective search space inspector: For the experiments conducted, we use the surrogate from BANANAS (White et al., 2021), which combines a neural ensemble predictor with path encoding of the architectures it worth noting that alternative surrogates may also be used, but preferable to use sample-efficient surrogate that is capable of finding meaningful relations in the input data with a modest number of evaluations. Specifically, we randomly sample 200 architectures from the search space and query their NB301 predicted performance proxy for the ground-truth performance. We then compute the path encoding each architecture and train a predictor with the default hyperparameters from White et al. (2021).
pairs used in
first verify whether the surrogate using less data is able to learn meaningful patterns by drawing another 200 random unseen architectures in the search space and compare the predictions by the neural ensemble predictor vs the NB301 prediction (Fig 30) and it is clear that the regression performance is already satisfactory (with Spearman rank coefficient of 0.77) despite using much less data.
Spearman = 0.999
Spearman p = 0.77
0.94
0.94
Prod
N8301 Pred
0.93
0.92
0.91
0.91
0.94
0.92
0.94
Surragate Pred
Surrogate Pred
(a) Train
(b) Validation
Figure 30: Regression performance of BANANAS predictor with training data vs the NB301 surrogate with more than 50,000 training data.
We then repeat the analysis in the main text, and show the operation-leve findings (Sec 3) in Figs 28 and 29 and the important subgraphs corresponding to Sec 4 in Fig 31. It is worth noting that most of
21

---

Published as a conference paper at ICLR 2022
the findings are already highly similar to those in the main text, although, for example, the operation importance distributions in Fig 29 have a larger variance due to the less certain predictions. The main purpose of this study is to show that combined with the explanability tools used in the present work, an appropriate performance surrogate, which is only used as a vessel towards searching in some search methods far, can be itself valuable. We demonstrate that it could shed insights into the strengths and weaknesses of an arbitrary search space with a modest number of observations for example, during design of new search space, we may randomly sample and evaluate modest number of architectures and similarly fit surrogate. We may then use the explainability tool to inspect the search space in similar procedure this section we believe this could potentially prevent some of the pitfalls described in the existing cell-based search spaces to recur in prospective new ones during the design process.
dhp
skip
skip
6
8
9
10
53
3kpp
sklp
skip
skip
Figure 31: Frequent subgraphs in the good-performing architectures ranked by ratio of supports between the important subgraphs and the reference and properties of the discovered frequent subgraphs according to the BANANAS surrogate. Note that the residual link + separable convolution patterns are highly similar to those identified in Fig in the main text
G PRIMITIVE REDUNDANCIES WITH MULTIPLE OPTIMISATION OBJECTIVES
Most of the findings of the paper, including the current definition of the O1, are based on maximising test accuracy as the sole objective, as the majority of the existing literature on cell-based NAS (at least those surveyed in App. C) focuses maximising performance the primary performance metric. However, alternative cost metrics often expressed in terms of FLOPS or number of parameters, sometimes also incorporated as a part of the objective (e.g. maximising test accuracy while minimising the number of parameters in the resulting architecture) especially for deployment on cost- sensitive platforms like mobile devices. This give rises to a multi-objective optimisation problem, and a reasonable question to ask is that whether some of the main findings, in particular the redundancy of primitives identified in the paper, still hold, as some of the primitives redundant or unimportant for maximising performance might be useful for minimising costs. In this section, we show some preliminary results that at least terms of cost metrics like FLOPs and/or number of parameters, the otherwise redundant primitives are still rather unimportant.
We consider the PrimSkip group of architectures described in Sec 4 since find that they give rise to the best performing architectures in the search space. Here, to obtain the trade-off between performance and number of model parameters while still maintaining the PrimSkip constraints, instead of sampling only from {s3, s5) primitives for the operation spots (except for the fixed residual connections), we introduce another parameter p E 1J. which denotes the probability that the parameterless skip is chosen instead of the separable convolution primitives except the two fixed residual connections: when p = skip will be selected for every possible operation spot, giving rise to the most lightweight possible architecture. On the other hand, when p = 0. we are back at the base scenario where the only ski ps are the residual connections fixed a-priori.
To investigate the importance of the pooling operations ((mp3, ap3 }), we then sample from another group of architectures that is identical to above, except that for the parameterless primitive, we may additionally choose from the pooling operations in addition to skip. For both groups, we sample 1,000 architectures from the constrained search spaces with random p [0, 1] and show the
22

---

Published as a conference paper at ICLR 2022
trade-off's in terms of 2D Pareto fronts between accuracy and number of parameters (Fig. (2) and between accuracy and FLOPs (Fig. 32(b)): if the pooling operations are indispensable to achieve good accuracy trade-off, we should have observed dominating Pareto fronts of the PrimSkip+PPol group of architectures over the PrimSkip group only. Nonetheless, we observe broadly comparable Pareto front for both groups (in terms of FLOPs, PrimSkip seems to find marginally more Pareto efficient solutions), suggesting that even after accounting for the conflicting objectives, it seems that in the existing search space design, pooling operations reduce costs largely because they are parameterless, and skip connections, which are similar parameterless, can be used to construct similarly performant/lghiweighh models but with reduced redundancies in primitive choices. It is nevertheless worth emphasising that this does not suggest that the pooling operations in general are not valuable; we hypothesise that the primary reason leading to the redundancies of pooling, as we also mentioned in the main text, is because the existing cell-based search space manually inserts pooling layers between cells, rendering pooling within cells unhelpful, for performance and/or for costs.
Poool
Primi kip Pool krp
PrimSkip
6.5
6.5
6.0
5.5
5.5
#Params(MB)
FLOPs
1e8
Figure 32: Test errors against number of parameters (a) and FLOPs (b) of the sample architcctures in the two groups.
H PERFORMANCE OF NAS ALGORIHTMM IN PRIMSKIP SEARCH SPACE
Another interesting experiment to consider the performance the existing NAS algorithms in the Prim- Skip space opposed to the original DARTS search space. In this section, we conduct experiments on two search methods, each representing a dominant genre in NAS: DARTS (Liu et al., 2019) as the seminal differentiable search method, and NAS-BOWL (Ru et al., 2021), the state-of-the-a query- based NAS method. For BOWL, we run 5 repetitions with a query budget of 100 architectures. For DARTS, use the default hyperparameters provided in the original DARTS paper train the supernetwork for 50 epochs. We show the trajectories of test errors and the final Fig. 33 (DARTS is not query-based, end of each epoch, as if it DARTS is terminated and discretised at that epoch. This metric is also referred to by, for example, oracle test error previous works (Li al., 2021)): it is evident that conducting search in the constrained search space leads to massive speed-ups compared to doing so in the original search space, again confirming that the simple rules identified in the paper have constrained the architectures to a very high- gegh-performin region of the search space.
Fig 33(b) shows the test error of the architecture proposed by DARTS the
DETAILED EXPLANATION OF THE FREQUENT SUBGRAPH MINING PROCEDURE IN SEC 4
As mentioned in Sec 4, support, which measure the number of times a subgraph occurs in set of graphs. favour simpler subgraphs as they appear more frequently "by nature": for example, consider the simplest subgraph such one consists of single operation (e.g. s3) as a single edge. is much more likely, even by random generation, for graph to contain s3 compared to another more complicated subgraph such as a triangle, with operations on edges being ( (s3, s5, skip). As result, s will have a much larger support in the set of graphs, but it does not imply it is a more significant subgraph.
Therefore, a more interesting and meaningful metric is how much more over-repreeented (or under- represented) subgraph is, within set of graphs, beyond its "natural" level of occurrences. An
23

---

Published as a conference paper at ICLR 2022
6.75
DARTS DARTS(PrimSkip)
NASBOWL
7.0
6.50
6.5
Test error
6.25
Test Error
6.00
6.0
5.75
5.5
5.50
5.25
5.0
0
20
40
60
80
100
0
20
40
Architectures evaluated
# Epochs
(a) NAS-BOWL
(b) DARTS
Figure 33: Performance of NAS-BOWL and DARTS in the constrained PrimSkip search space. The NAS-BOWL results shown with mcan = std random sceds.
Full architectures
Important subgraphs
Random subgraphs as the aull reference
1 44
Figure 34: Demonstration of the frequent subgraph mining procedure in the important subgraphs. Full architec- tures shows the DAGS representing the entire search colls; Important subgraphs (the coloured subgraphs) shows the subgraphs of each full architecture consist of only the important operations (i.e. those with OI above some threshold). Random subgraphs (the coloured subgraphs) architectures G and its important subgraph g' with m edges, we randomly sample exactly m edges from each G. possibly with multiple repetitions, to form g". the corresponding random subgraph(s) of G.
the null reference in this
consider full
intuitive way to measure this over-representation thus to compute ratio between the support of the subgraphs in the target set and that of some null reference set. As shown by the demonstration in Fig 34, the target in this case is simply the important subgraphs as defined in Sec 4. The null reference, as explained in the captions of Fig 34, are constructed from the randomly sampled subgraphs of each full architecture DAG. The key intuition here is that if subgraph has high support simply by virtue of its simplicity or otherwise, should have high support values both the target and null reference sets and taking the ratio would cancel out its influence (due to the high denominator value). the other hand, if there exists an underlying mechanism such that certain subgraphs are more likely to be important (which is the primary objective of the FSM in this context to identify whether there exists sub-structures within cells that correlate with good performances), then they will likely be more over-represented in the target set than in the null reference. Indeed, the top subgraphs as identified in Fig 7 all feature rather more complicated structures and low "natural" incidence, but they nevertheless appear recurring patterns in the important subgraphs, suggesting that they have strong connection to the overall good performance of the cells.
J SUGGESTIONS FOR FUTURE DIRECTIONS
In this section, we elaborate in detail the two promising future directions that we identify in Sec that would hopefully guide future NAS researchers and practitioners to build better search spaces:
24

---

Published as a conference paper at ICLR 2022
Simplify the cells but relax the macro-connection between cells: Current cell-based NAS almost overwhelmingly focuses on cells but manually fix the inter-cell connections in a linear manner similar to the classical networks (e.g. ResNet) that are known to do well. On the other hand, other search spaces like the MobileNet space, are arguably more flexible but are purely macro-based in our opinion, there could be potential to preserve the convenience of the search cell, but the same time to give more freedom on how different cells are connected. By relaxing the constraints on how the different cells may be connected, there is not only potential for much larger and expressive search space, but also be greater variability in overall graph theoric topological properties (as opposed to topological properties within cells only) and widths/depthhs of the resulting networks, which have been shown to significantly influence the performance (Xie et al., 2019a; Ru et al., 2020). We leave the detailed specification of such search space to a future work, but a concrete direction would be to further investigate and improve on the hierarchical search spaces such as the one proposed in Ru et al. (2020).
Towards lower-level searching: As hypothesised in the main text, the current search methods might be implicitly encouraged to find something similar to the existing architectures, as the current NAS pipelines often borrow heavily from the classical network designs (e.g. the linear macro connections between cells and the manually inserted conv and pooling layers are often found in the manually-designee networks). While this is not necessarily bad on its own, we might be making more difficult for search methods to find novel architectures beyond what is already known. An alternative could be that instead of searching on high-level primitives and operators, we could search something more fundamental like searching for sequences of mathematical operations. The pioneering work is Real et al. (2020), but similar to some early-stage NAS works, it was built evolutionary algorithms, which are particularly sample- and computation cost-efficient (as opposed to later works like one-shot/differentaab NAS which dramatically reduced computing cost of NAS). Thus, another promising direction would be explore searches on more fundamental level that is free of bias from existing design, but to develop more scalable and tailored solutions to make the problem more tractable.
NAS Benchmarks beyond simple cells: The advent of the NAS benchmarks have greatly democra- tised NAS and has partially led to the booming of recent NAS research. While exceptions may exist, the most popular NAS benchmarks on computer vision problems, which greatly facilitate faster iteration of search methods. are currently based on the cell-based spaces 101/202/301/xI (Ying et al., 2019a; Dong & Yang, 2020; Siems al., 2020; Yan et al., 2021). An improved search space would be made more widely accepted in much easier way if a suitable benchmarking tool is developed. Therefore, we argue there is need is to build NAS benchmarks beyond the current cell-based spaces.
25


Reviews:
[{"review_id": "VZtHeptebyO", "reviewer": "Reviewer_7BWB", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n- Comprehensive studies on the DARTS search space, particularly operation importance and common subgraphs. These anlysis in a sense expose that redundancy and diversity issues that exist in the cell design of DARTS.\n- The paper gives some suggestions in the design of search space and benchmark for NAS: 1) search (grow the search space) and prune (remove redundancy). 2) focus on macro design choices rather than cell design choices.\n- Originally I am skeptical about using surrogate benchmark, as using predicted performance may draw biased conclusion on operation importance etc. The paper did verify this as seen in Figure 5 and Figure 10 (b).\n\nCons:\n- **Open questions are not discussed**: Despite many interesting findings, the authors left many questions in the end. What is a good search space? Can the authors suggest a list of good practices when designing a search space? \n- **Mainly based on NAS-Bench-3 / DARTS search space**: The analysis is mostly based on the DARTS cell. This show that problem exists in the DARTS search space, but it doesn't suggest that cell-based search space suffer from the same problems. As the authors also mentioned in the appendix, redundancy in NAS-Bench-201 is less significant. For example, the skip constraint does not impact the performance as much as DARTS.\n- **Merit of cell-based search space**: The paper heavily criticizes the cell-based search space. However, I am not convinced that the existing cell-based search space is not valuable. It is ideal if we can find SOTA model in the search space, but the main point of NAS search space is to provide a fair common ground to compare NAS methods. \n- **Operation importance**: Related to the previous point, the search space provides design trade-off but the operation importance is not considering this aspect. For example, one may find a model with better FLOPS or latency. Would the 'unimportant' operations such as pooling actually contribute to reducing computation cost?\n", "summary_of_the_paper": "This paper strongly criticized the current cell-based NAS approach is limitiing research in NAS. The main points are:\n1. Redundancy in the cell-based search space: Performance of architecture is mostly attributed to a few important operations, while the 'unimportant' operations only add complexity to the search space. Essentially, the high-performing models share similar sub-graphs.\n2. Constrianting cells to similar patterns yields better results: By limiting the search space to important operations and similar sub-graphs, random sampling in NAS performs on par with most other NAS algorithms.", "summary_of_the_review": "The findings in this paper are inspirataional. However, the analysis is limited to particular search space which doesn't mean that the cell-based approach is not valuable in general. The paper is trying to provide some insights on search space design but I would like to see more elaboration in this direction for this paper to be accepted.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Tyl8rfd_Nz", "reviewer": "Reviewer_1mk2", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "\n# Merits\n\n- The paper addresses arguably one of the main challenges in current neural architecture search, the search space design. The provided results question the popular argument that a higher dimensional search space is automatically more expressive and leads to new promising architectures.\n\n- While one could argue that experiments are based mostly on the NASBench301 surrogate model, I do think they are sufficiently reliable. First, the surrogate models has been shown to provide reliable predictions and, second, the paper shows the same results emerge on a subset of architectures trained on the original data.\n\n- Even though I honestly found the results of the paper less surprising, I think the paper has a high chance to impact the future development of new search spaces\n\n- Overall I found the paper well written and easy to follow. Also, the proposed techniques to analyse operators and subgraphs seem sensible.\n\n\n\n\n# Concerns\n\n- The paper focuses mostly on the DARTS search space and NB201, which is a simplified version of the former. However, other search spaces (e.g NB101) assign operations to nodes instead of edges which might exhibit different properties than DARTS based search spaces. While I do not think that it effects the main findings, it would be great if the authors could comment on that in the paper.\n\n- I haven't fully understood how you account for the bias towards simpler subgraphs in your subgraph-level analysis in Section 4. How does this reference set of architectures with randomly sampled operations correct this bias?\n", "summary_of_the_paper": "The paper analyses cell-based search spaces for neural architecture search based on the NASBench301 dataset. The main finding are that a) only a subset of the operations actually contribute to the final performance and b) well performing architectures exhibit common patterns from the literature (e.g res-net style motifs), questioning whether we actually find entirely new configurations with current search spaces.", "summary_of_the_review": "The paper points out several shortcomings of cell-based search spaces which are arguably the default in neural architectures search. In the long run, I think the paper can have a significant impact and help us to define better search spaces.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CVSgP9MXmw9", "reviewer": "Reviewer_zTwP", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\n1. The findings are very relevant to the NAS community. Rather than searching over all the operations and  spending a lot of computational effort during the search, by using all the operations, it is better to search on a subset if we know it is more promising\n2. By showing that skip connection is crucial for training as a residual connection, they point out that same intuition behind the designing of ResNet. \n3. Although the authors did not mention this, reducing the number of operations search space alleviates the problem of the ranking of the architectures sampled from supernet  based on their weight-sharing accuracy and the ranking of the same architectures when trained from scratch is not highly correlated. This has been plaguing the community and one of the solutions is to gradually pruning the less importations operations on an edge as the training proceeds. \n\nAdditional experiments requested:\n1. Could you create an additional table by running Darts and Bananas (and other NAS algorithm of if you have more time) on PrimSkip search space for Cifar 10 and transfer it to Imagenet space and see what the best accuracy is? How much is the run time reduced by? \n2. For Darts, what is the correlation of the ranking between the architectures based on their Supernet accuracy and that when trained from scratch in PrimSkip search space and the original darts search space? \n\nWeakness:\n 1. The only issue is the reliance on the surrogate model. In Figure 10(b), they did train the architectures, but 30 is very small to make a conclusive decision.  Also, for figure 10(a), could you increase the networks to 100?\n", "summary_of_the_paper": "This paper examines the NASNET cell spaced search space in NASBENCH-301 (darts search space) and NASBENCH-201. They conclude that Separable convolution and skip connections are the most important operations. By replacing the current operations with just this subset and also enforcing the skip connection to be used as a residual connection, they are able to achieve accuracy very similar to the networks discovered by other SOTA algorithms. They also demonstrate that one does not have to search for reduce cell and that it can just use the same architecture as that of the normal cell. Finally, they replace the SOTA architectures found by the most popular NAS algorithms and replace the cells to use only Separable conv and skip connections and show that the accuracy of the network is very close to the original network.", "summary_of_the_review": "This paper focuses on an important topic of understanding the search spaces better. In addition to developing new algorithms, one also needs to investigate the characteristics of the search space and how one can improve it.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "CNT20HN06wu", "reviewer": "Reviewer_eT12", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Pros:\n\nThe paper is overall well-written and solid in terms of empirical studies. A key message to me is that high-performance architectures in the cell-based search space lie in a low-dimensional “manifold” which can be explained by several simple factors such as the inclusion of key ops and specific topological patterns. While this seems a known fact implied by several existing works on random search & performance predictors, results in this work are still quite informative (e.g., the authors explicitly summarized some of the most useful design choices of the best models).\n\nCons:\n\nOne of the main findings the authors reveal is that random search could perform well when augmented with simple heuristics, which further implies that the current search space is not practically interesting. This is only partially correct to me because the useful constraints discovered in the paper are arguably the outcomes of a search algorithm -- namely the one performed by nas-bench-301 (“50,000 architecture-performance pairs in the DARTS space using a combination of random sampling and more than 10 state-of-the-art yet technically diverse methods”). In other words, the constrained random search in this work is in fact heavily based on the prior knowledge discovered by search.\n\nAs far as I can tell the scope of the paper is restricted to cell-based NAS. However, people have also explored many other types of search spaces, such as the ones used in ProxylessNAS, MobileNetV3, EfficientNet, TuNAS and FBNets. Unlike the cell-based ones, those search spaces emphasize macro instead of micro decisions hence are less subject to the concerns raised. There are also other types of search spaces that are presumably less restrictive in terms of the choice of primitives, such as AutoML-Zero. While I agree with the authors that cell-based search spaces are still the mainstream for weight-sharing NAS, it would be more comprehensive to discuss the aforementioned works.\n\n", "summary_of_the_paper": "The paper performs a detailed analysis of the DARTS search space commonly used for weight-sharing neural architecture search. The authors used several simple statistical methods to identify salient features (ops or graphlet) that can best explain the higher-quality candidates. They also looked into the discovered patterns and reached the conclusion that the popular cell-based search space is highly redundant, as simply imposing two of the discovered constraints can result in strong performance even using random search.", "summary_of_the_review": "Overall speaking, this is a good paper attempting to address an important topic in neural architecture search regarding search space redundancies. The message is not groundbreaking in my option given several existing works with similar implications, but the analysis and results are interesting enough to be informative.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AnFxyhClt95", "reviewer": "Reviewer_2nKR", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1. Reducing the complexity of search spaces in NAS is a strong motivation.\n2. The authors identify multiple interesting redundancies that may help influence future designs.\n3. Paper is reasonably easy to read, although numerous grammatical errors (see comments for just the first part).\n\nWeaknesses:\n1. It is not at all clear how a result like this generalizes beyond CIFAR. While it is clear that, if the goal is to search for the best architecture on CIFAR, then reducing the search space in this way is useful. However, the point of CIFAR is really just to be a testing ground for algorithms run on other tasks. On those it is entirely unclear that the less useful operations will still not be useful; for example, larger dilations are good for sequence modeling while max-pooling is important for local invariance. The focus on CIFAR is interesting as a baseline but does not give evidence that these restrictions would work on other datasets.\n2. Another missing component is the question of compute time/energy use, which depends on the topology and operations. Many search spaces focus on more efficient architectures, which may themselves be more redundant in the full space and thus will be ignored in this study.\n\nComments:\n1. [*This simplification reduces the search space (but still highly complex),*] Unclear parenthetical.\n2. [*it is fair to state that such cell-based spaces currently dominates.] -> dominate\n3. [*high-level patterns only (Shu et al., 2020; Zela et al., 2020) We*] Missing period.\n4. [*NAS paradigms such as transformers*] -> Transformers\n5. [*Note that we may not obtain NB301 performance prediction on these architectures, as NB301 requires all 16 operations to be enabled with valid primitives.*] This does not make sense to me. If NB301 contains all architectures in DARTS, surely it contains those that do not have any of the removed operations.\n6. [*Fig. 4 shows that the OI distribution across all primitives are centered close to zero in reduce cells: both suggest that reduce cell is less important to the architecture performance.*] Unclear how this shows the reduce cell is unimportant, and not that it contains redundant operations.", "summary_of_the_paper": "Summary:\nThis paper studies the DARTS search space using predicted results from NAS-Bench-301 and presents several findings that suggest that SOTA performance on CIFAR-10 can be obtained via a relatively small subset of the space. They leverage these findings to suggest a simplified search space in which random architectures achieve strong performance and also to give suggestions for future development of NAS algorithms.", "summary_of_the_review": "While the discoveries in the paper are interesting and may be useful for searching CIFAR, it is entirely unclear how they extend to more practical NAS settings, e.g. tasks beyond CIFAR and constraints beyond just the DARTS search space. Indeed the findings may not be relevant if they do not hold in other settings NAS may be applied to. I view answering these questions as critical and so lean against acceptance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper makes the important, albeit somewhat unsurprising, finding, that cell-based NAS search spaces, and in particular the DARTS search space, include some operations that are much better than others. Reducing the search space to these allows even random architectures to yield good performance, similarly to the findings of "Designing Network Design Spaces", https://openaccess.thecvf.com/content_CVPR_2020/html/Radosavovic_Designing_Network_Design_Spaces_CVPR_2020_paper.html

This paper received mostly positive scores (5,6,6,8). While I agree with the negative reviewer that it would be good to study this on other benchmarks as well, I follow the positive reviewers in recommending acceptance. I encourage the authors to fix the remaining typos (there are still many) and to open source their code. This would increase the paper's impact a lot.

Finally, I would like to ask the authors to avoid protraying the misconception that we don't need large and powerful search spaces. In fact, as already hinted on in Section 6, we *do* need larger and more exciting search spaces in order to discover entirely novel architectures. Also the multi-objective nature of NAS is not to be undervalued, so the take-away of the paper should *not* be that we should design NAS benchmarks with really small & strong search spaces, but that, given a specific problem and objective, it may be prudent to evaluate whether the whole power of a given NAS search space is needed or whether it can be reduced to its essential parts.
Decision: Accept (Poster)