Understanding Architectures Learnt by Cell-based Neural Architecture Search
Authors: Yao Shu
Wei Wang
Shaofeng Cai
Venue:  (2020)
Keywords: Neural Architecture Search
connection pattern
optimization
convergence
Lipschitz smoothness
gradient variance
generalization

Abstract: Neural architecture search (NAS) searches architectures automatically for given tasks, e.g., image classification and language modeling. Improving the search efficiency and effectiveness has attracted increasing attention in recent years. However, few efforts have been devoted to understanding the generated architectures. In this paper, we first reveal that existing NAS algorithms (e.g., DARTS, ENAS) tend to favor architectures with wide and shallow cell structures. These favorable architectures consistently achieve fast convergence and are consequently selected by NAS algorithms. Our empirical and theoretical study further confirms that their fast convergence derives from their smooth loss landscape and accurate gradient information. Nonetheless, these architectures may not necessarily lead to better generalization performance compared with other candidate architectures in the same search space, and therefore further improvement is possible by revising existing NAS algorithms.

Published as a conference paper at ICLR 2020
UNDERSTANDING ARCHITECTURES LEARNT BY BELL-BASED NEURAL ARCHITECTURE SEARCH
Yao Shu, Wei Wang & Shaofeng Cai School Computing National University of Singapore {shuyao, wangwei, shaof comp. nus. edu.sg
ABSTRACT
Neural architecture search (NAS) scarches architectures automatically for given tasks, e.g., image classification and language modeling. Improving the search ef- ficiency and effectiveness has attracted increasing attention in recent years. How- ever, few efforts have been devoted to understanding the generated architectures. In this paper, we first reveal that existing NAS algorithms (e.g., DARTS, ENAS) tend to favor architectures with wide and shallow cell structures. These favorable architectures consistently achieve fast convergence and are consequently selected by NAS algorithms. Our empirical and theoretical study further confirms that their fast convergence derives from their smooth loss landscape and accurate gra- dient information. Nonetheless, these architectures may not necessarily lead to better generalization performance compared with other candidate architectures the same search space, and therefore further improvement is possible by revising existing NAS algorithms.
INTRODUCTION
Various neural network architectures (Krizhevsky et al. 2012, Simonyan & Zisserman, 2015 He
al., 2016; Huang et al.] (207)) have been devised over the past decades, achieving superhuman performance for a wide range of tasks. Designing these neural networks typically takes substantial efforts from domain experts by trial and error. Recently, there a growing interest in neural archi- tecture search (NAS), which automatically searches for high-performance architectures for the given task. The searched NAS architectures (Zoph et al.] 2018 Real et al.) 2019; Pham et al., 20188) Liu et al. 2019 Xie et al. 2019b Luo et al. 2018 Cai et al. 2019: Akimoto et al.. 2019 Nayman al.
2019 have outperformed best expert-designed architectures on many computer vision and natural language processing tasks.
Mainstream NAS algorithms typically search for the connection topology and transforming opera- tion accompanying each connection from predefined search space. Tremendous efforts have been exerted to develop efficient and effective NAS algorithms (Liu et al. 2019; Xie et al. 2019b Luo attention has been paid to
al., 2018 Akimoto al. 2019 Nayman et al. 2019). However, these searched architectures for further insight. To our best knowledge, there is no related work in literature examining whether these NAS architectures share any pattern, and how the pattern may impact the architecture search if there exists the pattern. These questions are fundamental to under- stand and improve existing NAS algorithms. In this paper, we endeavour to address these questions by examining the popular NAS architecture4]
The recent work (Xie et al. 2019a) shows that the architectures with random connection topologies can achieve competitive performance various tasks compared with expert-designed architectures. Inspired by this result, we examine the connection topologies of the architectures generated by pop- ular NAS algorithms. In particular, These architectures tend to favor wide and shallow cells, where the majority of intermediate nodes directly connected to the input nodes.
find connection pattern of the popular NAS architectures.
'The popular NAS architectures refer to the hest architectures generated by state-of-the-art (SOTA) NAS algorithms throughout the paper. Notably, research the cell-hased NAS algorithms and architectures.

---

Published as a conference paper at ICLR 2020
To appreciate this particular connection pattern, we first visualize the training process of the popular NAS architectures and their randomly connected variants. Fast and stable convergence is observed for the architectures with wide and shallow cells. We further empirically and theoretically show that the architectures with wider and shallower cells consistently enjoy a smoother loss landscape and smaller gradient variance than their random variants, which helps explain their better convergence and consequently the selection of these NAS architectures during the architecture search.
We finally evaluate the generalization performance of the popular NAS architectures and their ran- domly connected variants. We find that the architectures with wide and shallow cells may not gener- alize better than other candidate architectures despite their faster convergence. We therefore believe that rethinking NAS from the perspective of the true generalization performance rather than the convergence of candidate architectures should potentially help generate better architectures.
RELATED WORKS
Neural Architecture Search Neural architecture search (NAS) searches for best-performing chitectures automatically for a given task. It has received increasing attention in recent years due to its outstanding performance and the demand for automated machine learning (AutoML). There three major components in NAS as summarized by [isken et al. (2019), namely search space, search policy (or strategy, algorithm), and performance evaluation (or estimation). To define the search space, the prior knowledge extracted from expert-designed architectures is typically exploited. As for the search policy, different algorithms are proposed improve the effectiveness (Zoph et al. 2018 Real et al. 2019 Tan et al., 2019) Cai et al., 2019) and the efficiency (Pham et al. 2018 Liu et al.] 2019 Xie et al. 2019b; Luo et al. 2018) Nayman al. 2019 Akimoto et al. (019)) of the architecture search. However, no effort has been devoted to understanding the best architectures generated by various NAS approaches. Detailed analysis of these architectures may give insights about the further improvement of existing NAS algorithms.
Evaluation of NAS algorithms Recent works evaluate NAS algorithms by comparing them with random search. Li & Talwalkar (2019) and SSciuto et al. (2019) compare the generalization per- formance of architectures generated from random search and existing NAS algorithms. Interest- ingly, the random search can find architectures with comparable
even better generalization per- formance. Particularly, (Sciuto et al. (2019) show empirically that the ineffectiveness of some NAS algorithms (Pham al. 2018) could be the consequence of the weight sharing mechanism during the architecture search. While these evaluations help understand the general disadvantages of NAS algorithms, what kind of architectures the NAS algorithms are learning and why they learn these specific architectures are still not well understood.
3 THE CONNECTION PATTERN OF POPULAR NAS CELLS
Mainstream NAS algorithms Zoph et al. 2018 Real et al. 2019 Pham et al. 2018 Liu et al, 2019
Xie et al. 2019b Luo al. 2018) typically search for the cell structure, including the connection topology and the corresponding operation (transformation) coupling each connection. The gener- ated cell is then replicated to construct the entire neural network. We therefore mainly investigate these cell-based NAS architectures. In this section, we first introduce the commonly adopted cell representation, which useful to understand the connection and computation in cell space. We then sketch the connection topologies of popular cell-based NAS architectures to investigate their connection patterns. By comparison, we show that there is a common connection pattern among the cells learned by different NAS algorithms; particularly. these cells tend to be wide and shallow.
3.1 CELL REPRESENTATION
Following DARTS (Liu et al. 2019), we represent the cell topology as a directed acyelic graph (DAG) consisting of N nodes, including M input nodes, one output node and (N - M 1) in- termediate nodes. Each node forms a latent representation of the input instance. The input nodes consist of the outputs from M preceding cells. And the output node aggregates (e.g., concatenate) the representations from all intermediate nodes. Each intermediate node connected to M pro- ceeding nodes in the same cell. Each connection transforms the representation from one node via
2

---

Published as a conference paper at ICLR 2020
(a) NASNet, 5c, (b) AmocbaNct,
ENAS, 5c,
(d) DARTS, 3.5c,
(c) SNAS,
Figure| I: Cell topologies of popular NAS architectures. Each sub-figur figure has three sets of nodes from left to right, i.e., the input nodes, intermediate nodes, and output node. The arrows (i.e., operations of the cell) represent the direction of information flow. The caption of each sub-figure reports the name of the architecture, width and depth of a cell following our definition. The width of a cell is computed with the assumption that all intermediate nodes share the same width
(a) Cdarrs 3.5c, (b) Cdarts, 2.5c, (c) G 2.5c,
(d) Cilorte, 2c,
(e) Cdarts 2c, 4
Figure 2: Topologies of DARTS (Liu al. 2019) cell (leftmost) and its variants with random connections. The cell depth increasing and width decreasing from left to right. In particular, the original DARTS cell Cddrrs is widest and shallowest among these cells.
an operation from a predefined operation set, c.g., 3x3 convolution, 3x3 max pooling, etc. The target of NAS algorithm is to search for the best M source nodes for each intermediate node and the best operation for each of the connections between nodes. the literature, the searched cell is then replicated by L times to build the entire neural network architecture"
We abuse the notation C' to denote a cell and also the architecture built with the specific cell in the following sections. Besides, shall CA to denote the best architecture (or cell) searched with the NAS algorithm A (e.g., DARTS (Liu et al.) 2019), ENAS (Pham et al. 2018).. Details on how to build the architecture with given cells are provided in Appendix A.3 A.3
3.2 THE COMMON CONNECTION PATTERN
Recently, Xie et al. 2019a) shows that neural networks constructed by cells with random connec- tion patterns can achieve compelling performance on multiple tasks. Taking this step further, wonder whether cells generated from popular NAS algorithms share any connection patterns, which may explain why these cells are chosen during the architecture search. To investigate the connection patterns, we sketch the topologies of the popular NAS cells with detailed operations omitted.
Figure illustrates topologies of 5 popular NAS cell.F) examine the connection pattern formally, introduce the concept of 'depth' and 'width' for a cell. The depth of cell is defined as the number of connections along the longest path from input nodes to the output node. The width of cell is defined the total width of the intermediate nodes that connected the input nodes. In particular, if some intermediate nodes are only partially connected to input nodes (i.e., have connections to other intermediate nodes). their width is reduced by the percentage of the number of connections to intermediate nodes over all connections. The width of node is the number
A We omit reduction cell here brevity, which used dimension reduction in NAS.
We only visualize normal cells since the number of normal cells is significantly larger than the reduction cells popular NAS architectures.

---

Published as a conference paper at ICLR 2020
of channels for convolution operations; and the width is the dimension of the features for linear operations. Supposing that the width of each intermediate node is c, as shown in Figure [ the width and depth of the DARTS (Liu et al. 2019) cell are 3.5c and 3 respectively, and the width and depth of the AmoebaNet (Real et al. 2019) cell are 4c and 4 correspondingly.
Following the above definitions, the smallest depth and largest width for cell with N 7 and M = 2 are 2 and 4c respectively. Similarly, for a cell with = 8 and M = 2, the smallest depth and largest width are and 5c respectively. In Figure | architectures tend to be the widest and shallowest ones (with width close to 4c/5c and depth close to 2) among all candidate cells in the same search space. Regarding this as the common connection pattern, we have the following observation:
we can observe that cells from popular NAS
Observation 3.1 (The Common Connection Pattern) NAS architectures generated by popular NAS algorithms tend to have the widest and shallowest cells among all candidate cells in the same search space.
THE IMPACTS OF CELL WIDTH AND DEPTH ON OPTIMIZATION
Given that popular NAS cells share the common connection pattern, we then explore the impact of this common connection pattern from the optimization perspective to answer the question: why the wide and shallow cells are selected during the architecture search? We sample and train variants of popular NAS architectures with random connections. Comparing randomly connected variants with the popular NAS architectures, we find that architectures with wider and shallower cells indeed converge faster that they are selected by NAS algorithms (Section 4.1). To understand why the wider and shallower cell contributes to faster convergence, we further investigate the loss landscape and gradient variance of popular NAS architectures and their variants via both empirical experiments (Section and theoretical analysis (Section
4.1 CONVERGENCE
Popular NAS algorithms typically evaluate the performance of a candidate architecture prematurely before the convergence of its model parameters during the search process. For instance, DARTS (Liu et al. 2019). SNAS (Xie et al.) 2019b) and ENAS (Pham et al. 2018) optimize hyper-parameters of architectures and model parameters concurrently. The amortized training time of each candidate architecture is insufficient and therefore far from the requirement for the full convergence. Likewise, AmoebaNet (Real et al. 2019) evaluates the performance of candidate architectures with the training of only a few epochs. In other words, these candidate architectures are not evaluated based on their generalization performance at convergence. As a result, architectures with faster convergence rates are more likely to be selected by existing NAS algorithms because they can obtain better evaluation performance given the same training budget. We therefore hypothesize that the popular NAS architectures may converge faster than other candidate architectures, which largely contributes to the selection of these architectures during the search.
To support the hypothesis above, we compare the convergence of original NAS architectures and their variants with random connections via empirical studies. We first sample variants of popular NAS cells following the sampling method in Appendix A.2 Then, we train both original NAS ar- chitectures and their random variants on CIFAR-10 and CIFAR- 100 following the training details in Appendix A.. During training, we evaluate the testing loss and accuracy these architectures. Since the convergence is dependent on optimization settings, we also evaluate the convergence per- formance under different learning rates.
Take DARTS (Liu et al. 2019) for example, Figure shows the connection topology of the original DARTS cell and its random variants. Figure 3 reports the test loss and accuracy curves of these ar- chitectures during training. As illustrated in Figure 3 the original cell Cdarts known as the widest and shallowest cell, has the fastest and most stable convergence compared with its variants. Further, as the width of cell increases and the depth decreases (i.e., from C2 C1), the convergence be- comes faster. The results of other popular NAS architectures and their randomly connected variants reported in Appendix B.2
4

---

Published as a conference paper at ICLR 2020
C400
Car
60
Cara
64-
75-
20-
230
420
600
420
600
200
402
402
000
(a) CIFAR- 10 10..Os..s Loss
(b) CIFAR-100 100 Loss
(c) CIFAR-10 Accuracy (d) CIFAR-100 Accuracy
Figure 3: Test loss and test accuracy (%) curves of DARTS and its randomly connected variants on 10 and CIFAR-100 during training. The default learning rate is 0.025.
Coatr
60-
20-
(a) CIFAR-10, 0.0025 (b) CIFAR-10, 10, 0.25
(c) 10FA 0.0025 (d) CIFAR- 100, 0.25
Figure 4: Test accuracy (%) curves of DARTS and its randomly connected variants CIFAR-10 and CIFAR-100 during training under different learning rates (0.0025 and 0.25). We only evaluate Cidrris, Cdarrt and Cylarts for illustration. The caption of each sub-figure reports the dataset and the learning rate.
Figure 4 further validates the difference of convergence under different learning rates. The original cell Cuar enjoys the fastest and the most stable convergence among these cells under various learn- ing rates. The difference in terms of convergence rate and stability is more obvious between Cdorts and its variants with a larger learning rate as shown Figure 4 Interestingly, Cg Cdarts completely fails to converge on both CIFAR-10 10 and CIFAR- 100 with larger learning rate of 0.25, While there a minor difference among these cells with a lower learning rate 0.0025, we still find that there is decreasing performance of convergence (i.e., convergence rate and stability) from Cidarta Cddrrt to Cgarrs Overall, the observations are consistent with the results Figure
We have also compared the convergence of popular NAS architectures and their random variants of different operations. Similarly, we sample and train the random variants of operations for popular NAS architectures following the details in Appendix A.2 and Appendix A.3] Figure 5 illustrates the convergence of these architectures. Surprisingly, with the same connection topologies as the popular NAS cells but different operations, all random variants achieve nearly the same convergence as these popular NAS architectures. Consistent results can be found in Figure 12 of Appendix B.2 We therefore believe that the types of operations have limited impacts on the convergence of NAS architectures and the connection topologies affect the convergence more significantly.
With these observations, we conclude that the popular NAS architectures with wider and shallower cells indeed converge faster and more stably, which explains why these popular NAS cells are se- lected during the architecture search. The next question is then why the wider and shallower cell leads to faster and more stable convergence?
4.2 EMPIRICAL STUDY OF FACTORS AFFECTING CONVERGENCE
Since the wide and shallow cell is related to fast convergence, we further conduct the theoretical con- vergence analysis to investigate the cause of fast convergence. In this section, we first introduce the convergence analysis (i.e.. Theorem 4.1) of non-convex optimization with the randomized stochastic gradient method (Ghadimi & Lan 2013). Based on the analysis, introduce the possible factors related to the common connection pattern that may affect the convergence. We then examine these factors empirically in the following subsections.
5

---

Published as a conference paper at ICLR 2020
80
80-
86-
6/'9
65-
65-
Clune
Gpmeto
Cq
Cymmte
75-
75
75
75-
200
402
800
200
400
120
0
200
402
120
200
402
620
(a) DARTS
(b) ENAS
(c) AmoebaNet
(d) NASNet
Figure 5: Test accuracy (%) curves of DARTS, ENAS, AmoebaNet, NASNet and their random
variants of operations on CIFAR-10 during training. The parameter size is attached in Table of
Appendix B.2
Theorem 4.1 Ghadiii & Lan 2013 Let be L-smooth non-convex function, and let be the minimal. Given repeated, independent accesses to stochastic gradients with variance bound o² for (w),, SGD with initial wo, total iterations N > and learning rate Tik < + achieves the following convergence by randomly choosing wi as the final outpul wR with probability π
The where
H H=ΣN Y
E / (wR) 2(ʃ (w)) f*)
Lo
N
7k
In this paper, f' and un denote the objective (loss) function and model parameters respectively. Based on the above theorem, Lipschitz smoothness I. and gradient variance o² significantly affect the con- vergence, including the rate and the stability of convergence. Particularly, given specific number of iterations N, smaller Lipschitz constant L or smaller gradient variance o² would lead smaller convergence error and less damped oscillations, which indicates faster and more stable conver- gence. Since the Lipschitz constant L and gradient variance o² are highly related the objective function, different NAS architectures result in different L and o². In the following subsections, we therefore conduct empirical analysis for the impacts of the cell with and depth on the Lipschitz smoothness and gradient variance.
4.2.1 Loss LANDSCAPE
The constant L of Lipschitz smoothness is closely correlated with the Hcssian matrix of the objec- tive function as shown by Nesterov (2004), which requires substantial computation and can only represent the global smoothness. The loss contour, which has been widely adopted to visualize the loss landscape of neural networks by GGoodelloo putationally efficient and is able report the local smoothness of the objective function. To explore the loss landscape of different architectures, we adopt the method in et al. (2018) to plot the loss contour saa 3) Ep-P [f + aw1 fwz)). The notation f.(-) denotes the loss evaluated at teh instance in the dataset and denotes the distribution of dataset. The notation w" Wi and W2 denote the (local) optimal and two direction vectors randomly sampled from Gaussian distribution respectively. And o, B, which are the x and y axis of the plots, denote the step sizes to perturb w'. The loss contour plotted here is therefore a two-dimensional approximation of the truly high- dimensional loss contour. However, as shown in Li et al. (2018). the approximation is valid and effective characterize the property of the true loss contour.
Vinyals (2015): [Li et al. (2018). is instead com-
:
To study the impact of the cell width and depth on Lipschitz smoothness, we compare the loss landscape between popular NAS architectures and their randomly connected variants trained in Sec- i.on4.1 on CIFAR- 10 and CIFAR-100. Due to the space limitation, we only plot the loss landscape of DARTS [Liu et al. 2019) and its randomly connected variants in Figure G We observe that the connection topology has a significant influence on the smoothness of the loss landscape. With the widest and shallowest cell, (dartt has a fairly benign and smooth landscape along with the widest near-convex region around the optimal. With deeper and narrower cell, Cddrrt and Cdarta have a more agitated loss landscape compared with ddrrts Further, Ciarrts, with the smallest width and largest depth among these cells, has the most complicated loss landscape and the narrowest and steepest near-convex region around the optimum. The largest eigenvalue of the Hessian matrix, which indicates the maximum curvature of the objective function, is positively correlated with Lip-

---

Published as a conference paper at ICLR 2020
CIFAR-100 CIFAR-10
Airrriir Diitiin siitiee
(a) Odarts
(b) Caarrt
(c) C2 Cdarts
(d) C3
Calarts
(c) Cdarts
Figure 6: Loss contours of DARTS and its variants with random connections the test dataset of CIFAR-10. The lighter color of the contour lines indicates a larger loss. Notably, the loss of the blank area, around the corners of each plot, is extremely large. Besides, the area with denser contour lines indicates a steeper loss surface.
(a) Cdarts
(b) Cdarts
(c) Cdlarts
Cdartt (d) C3
(c) Cdlarts
Figure 7: Heat maps of the gradient variance from DARTS and its randomly connected variants around the optimal on the test dataset of CIFAR-10. The lighter color indicates larger gradient variance. Notably, the gradient variance of the yellow area, around the corners of each plot, is extremely large. Obviously, the region with relatively small gradient variance becomes smaller from left to right.
schitz constant as shown by Nesterov 2004). A smoother loss landscape therefore corresponds to a smaller Lipschitz constant T.. Cdarta likely to achieve the smallest Lipschitz constant among these cells.
Consistent results can be found in Appendix B.3 for the loss landscape of other popular NAS cells and their variants. Based on these results, we conclude that increasing the width and decreasing the depth of a cell widens the near-convex region around the optimal and smooths the loss landscape. The constant L of Lipschitz smoothness therefore becomes smaller locally and globally. Following architectures with wider and shallower cells shall converge faster and more stably.
Theorem 4.1
4.2.2 GRADIENT VARIANCE
The gradient variance indicates the noise level of gradient by randomly selecting training instances in stochastic gradient descent (SGD) method. Large gradient variance indicates large noise in the gradient, which typically results in unstable updating of model parameters. Following Ghadimm & Lan (2013). gradient variance defined Var(V)((w)). Similar the visualization of loss landscape in Section 4.2.1 we visualize the gradient variance by g(a, 3) = Var( (ww + oaw, + (w2)). All other notations follow Section 4.2.1
To study the impact of the width and depth of a cell on the gradient variance, we compare the gradient variance between popular NAS architectures and their randomly connected variants trained in Section 4.1 on CIFAR-10 and CIFAR-100. We visualize the gradient variance of DARTS (Liu
ctt al. 2019) and its randomly connected variants Figure and Figure g For better visualization, we plot the figures using the standard deviation (i.e., (g(a, a 3)) to avoid extremely large values in the visualization of DARTS. Obviously, the cell width decreases and the cell depth increases (i.e., from ddrrts to Cdarts)), ) the region with relatively small gradient variance becomes smaller as shown in Figure Consistently, the gradient variance generally shows increasing trend from dartt to

---

Published as a conference paper at ICLR 2020
(a) Cdants
(b) Clarts
(c) Ciaart
(d) Cdarts
(c) Clarts
Figure 8: 3D surfaces of the gradient variance from DARTS and its randomly connected variants around the optimal on the test dataset of CIFAR-100. The height of the surface indicates the value of gradient variance. Notably, the height of the gradient variance surface is gradually increasing from left to right. Especially, ddrrts has the smoothest and lowest surface of gradient variance among these architectures.
Cyerts in Figure Consequently, the gradient becomes noisier in the neighborhood of the optimal, which typically makes the optimization harder and unstable.
Similar results from other popular NAS architectures and their random variants are provided in Appendix B.4 Based on these results, we conclude that the increase in width and the decrease in depth of cell result in a smaller gradient variance, which makes the optimization process less noisy and more efficient. The convergence of wide and shallow cells therefore shall be fast and stable following Theorem 4.1
4.3 THEORETICAL ANALYSIS OF FACTORS AFFECTING CONVERGENCE
Our empirical study so far suggests that larger cell width and smaller cell depth smooth the loss landscape and decrease the gradient variance. Consequently, popular NAS architectures with wide and shallow cells converge fast. this section, we investigate the impacts of the cell width and depth on Lipschitz smoothness and gradient variance from theoretical perspective.
4.3.1 SETUP
We analyze the impact of the cell width and depth by comparing architectures with the widest cell and the narrowest cell as shown in Figure 26 of Appendix C To simplify the analysis, the cells we investigate contain only one input node æ one output node. The input node may be training instances or output node from any proceeding cell. All operations in the cell are linear operations without any non-linearity. Suppose there are n intermediate nodes intermediate node and its associated weight matrix are denoted as (+)) and ( = 1, n) respectively. The output node z denotes the concatenation of all intermediate nodes. Both cells have same arbitrary objective function / following the output node, which shall consist of the arbitrary number of activation functions and cells. For clarity, we refer to the objective function, intermediate nodes and output node of the architecture with the narrowest cell as f. ( and respectively, As shown in Figure 26 the intermediate node (9) and (())) can be computed by y( W(0 x and g( T ( x: respectively. Particularly,
cell, the in
II: W(k) W ((-1)....... ... (1)))) And all the related proofs of following theorems can be found in Appendix
4.3.2 THEORETICAL RESULTS
Due to the complexity of the standard Lipschitz smoothness, instead investigate the block-wise Lipschitz smoothness (Beck & Tetruashvili 2013) the two cases shown in Figure 26 In Theo- rem 4.2 show that the block-wise Lipschitz constant of the narrowest cell is scaled by the largest eigenvalues of the model parameters (i.e., ( 1, 1,... nn)). Notably, the Lipschitz constant of the narrowest cell can be significantly larger than the one the widest cell while most of the largest
eigenvalues are larger than 1, which slows down the convergence substantially. The empirical study in Section 4.2.1 has validated the results.
Theorem 4.2 (The impact cell width and depth on block-wise Lipschitz smoothness Let ( be the largest eigenvalue W(), Gäven the widest cell with objective function I and the
8

---

Published as a conference paper at ICLR 2020
DARTS
ENAS
AmosbaNet
NasNet
Accuracy
810111213 0123466
910111213
Figure 9: Comparison of the test accuracy at the convergence between popular NAS architectures and their randomly connected variants on CIFAR-10. Each popular NAS architecture (index on the æ-axis) is followed by 13 randomly connected variants (from index I to index 13 on the æ-axis), corresponding to C₁ to C13 respectively. The width and depth of these random variants are shown in Table in Appendix B.2 The dashed lines report the accuracy of the popular NAS architectures.
narrowest cell with objective function F. by assuming the block-wise Lipschitz smoothness of the af aw!"
widest cell as aw Lipschitz smoothness of the narrowest cell then can be represented i-1
S ( [ w! for any w and w the block-wise
af ow( o
of
w/
We then compare the gradient variance of the two cases shown in Figure 26 Interestingly, gradient variance suggests a similar but more significant difference between the two cases compared with their difference in Lipschitz smoothness. As shown in Theorem 4.3 the gradient variance of the narrowest cell is not only scaled by the square of the largest eigenvalue of the weight matrix but also is scaled by the number of intermediate nodes (i.e., n). Moreover, the upper bound of its gradient variance has numbers of additional terms, leading to a significantly larger gradient variance. The empirical study in Section 4.2.2 has confirmed the results.
Theorem 4.3 (The impact of cell width and depth on gradient variance ) Let (() be the largest eigenvalue of W(O, Given the widest cell with objective function f and the narrowest cell with ob-
jective function I, by assuming the gradient variance of the widest cell as I. (0 for any WtO, the gradient variance of the narrowest cell is then bounded by
af EE 85 bway
<
aw
af
of aW
(K)
k
E
E
100
aW
A
5 GENERALIZATION BEYOND THE COMMON CONNECTIONS
Our empirical and theoretical results so far have demonstrated that the common connection pattern helps smooth the loss landscape and make the gradient more accurate. Popular NAS architec- tures with wider and shallower cells therefore converge faster, which explains why popular NAS architectures are selected by the NAS algorithms. Nonetheless, we have ignored the generalization performance obtained by popular NAS architectures and their random variants. We therefore wonder whether popular NAS architectures with wide and shallow cells generalize better.
In Figure we visualize the test accuracy of popular NAS architectures and their randomly con- nected variants trained Section 4.1 Notably, petitive accuracy compared with most of the random variants. However, there some random variants, which achieve higher accuracy than the popular architectures. Interestingly, there seems to be optimal choice of depth and width for a cell to achieve higher test accuracy (i.e., C7 for DARTS and C4 for ENAS). Popular NAS architectures with wide and shallow cells therefore are not guaranteed to generalize better, although they typically converge faster than other random variants.
popular NAS architectures can achieve com-
We also adapt the connections popular NAS architectures to obtain their widest and shallowest variants. The adaption is possible due to the fact that the cells (including normal and reduction cell)

---

Published as a conference paper at ICLR 2020
Table 1: Comparison of the test error at the convergence between the original and the adapted NAS architectures on CIFAR-10/100 and Tmy-ImageNNtt200. The entire networks are constructed and trained following the experimental settings reported Appendix [A.3] which may slightly deviate from the original ones. The test errors (or the parameter sizes) of original and adapted architectures are reported on the left and right hand-side of slash respectively.
Architecture
CIFAR-I0
CIFAR- 100
Liny-mmageNet-200
Error(
Params(
(rror(5)
Params(M)
Error(5))
Params(
NASNet Zoph 2018]
2.65/2.80
4.29/4.32
17.06/16.86
4.42/4.45
31.88/32.05
4.57/4.60
AmoehaNet (Real al. 2019
2.76/2.91
3.60/3600
17.55/17.28
3.71/3.71
32.22/33.16
3.83/383
ENAS (Pham el al. 2018
2.64/2.76
4.32/4.32
16.67/16.04
4.45/4.45
30.68/31.36
4.60/4.0
DARTS (Liu et al 2019
2.67/2.73
3.83/3,90
16.41/16.15
3,95/4.03
30,58/31.33
4,08/4,16
SNAS (Xie et al.. (0119b
2.88/2.69
3.14/3.19
17.78/17.20
3,26/3.31
32.40/32.61
3,39/3.45
of popular NAS architectures are generally not widest and narrowest as shown in Figure T While there are various widest and shallowest cells following apply the connection pattern of SNAS cell shown in Figure [e) )) to obtain the widest and shallowest
definition of cell width and depth,
cells. The adapted topologies are shown in Figure 25 of Appendix [B.5
Table T Iillustrates the comparison of the test accuracy between our adapted NAS architectures and the original ones. As shown Table [ the adapted architectures achieve smaller test error on CIFAR-100. Nevertheless, most of the adapted architectures, obtain larger test error than the original NAS architectures on both CIFAR-10 10 and Iin-IImagNNet-200" The results again suggest that the widest and shallowest cells may not help architectures generalize better, while these architectures typically achieve compelling generalization performance.
The results above have revealed that the architectures with wide and shallow cells may not general- ize better despite their fast convergence. To improve current NAS algorithms, we therefore need to rethink the evaluation of the performance of candidate architectures during architecture search since the current NAS algorithms are not based on the generalization performance at convergence as men- tioned in Section 4. Nonetheless, architectures with the wide and shallow cells usually guarantee a stable and fast convergence along with competitive generalization performance, which should be good prior knowledge for designing architectures and NAS algorithms.
CONCLUSION AND DISCUSSION
Recent works have been focusing the design and evaluation of NAS algorithms. We instead endeavour to examine the architectures selected by the various popular NAS algorithms. Our study is the first explore the common structural patterns selected by existing algorithms, why these architectures are selected, and why these algorithms may be flawed. In particular, we reveal that popular NAS algorithms tend favor architectures with wide and shallow cells, which typically converge fast and consequently are likely be selected during the search process. However, these architectures may not generalize better than other candidates of narrow and deep cells.
To further improve the performance of the selected NAS architectures, one promising direction for the current NAS research is evaluate the generalization performance of candidate architectures more accurately and effectively. While popular NAS architectures appreciate fast and stable con- vergence along with competitive generalization performance, we believe that the wide and shallow cells are still useful prior knowledge for the design of the search space. We hope this work can attract more attention to the interpretation and understanding of existing popular NAS algorithms.
ACKNOWLEDGEMENT
This research is supported by the National Research Foundation Singapore under AT Singapore Programme [Award No. AISG-GC-2019-002 and Singapore Ministry of Education Academic Re- search Fund Tier under MOEs official grant number M0E2017-T3-1-007,
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Youhei Akimoto, Shinichi Shirakawa, Nozomu Yoshinari, Kento Uchida, Shota Saito, and Kouhei Nishida. Adaptive stochastic natural gradient method for one-shot neural architecture search. In ICML, volume 97 of Proceedings of Machine Learning Research, pp. 171 171-180. PMLR, 2019.
Amir Beck and Luba Tetruashvili. On the convergence of block coordinate descent type methods. SIAM Journal on Optimization, 23(4):2037-206)) 2013.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. In ICLR (Poster). OpenReview.net, 2019.
Terrance Devries and Graham W. Taylor. Improved regularization of convolutional neural networks with cutout. CoRR, 0tbs/1708.04555 2017.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey.
Journal of Machine Learning Research, 20(55):1-21, 2019.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochastic programming, SIAM Journal on Optimization, 23(4):2341-238) -2-228,,,,,,,,,, 2013.
lan J. Goodfellow and Oriol Vinyals. Qualitatively characterizing neural network optimization prob- lems. In ICLR, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In CVPR, pp. 2261-2269. IEEE Computer Society, 2017.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. Imagenet classification with deep convo- lutional neural networks. In NIPS, pp. 1106-1114, 2012.
Gustay Larsson, Michael Maire, and Gregory Shakhnarovich. Fractalnet: Ultra-deep neural net- works without residuals. In ICLR (Poster). OpenReview.net, 2017.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss land- scape of neural nets. In NeurlPS, pp. 6391-6401, 2018.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In UAI, pp. 129. AUAI Press, 2019.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: differentiable architecture search. In ICLR (Poster). OpenReview.net, 2019.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie-Ya Yan Liu. Neural architecture optimization. In NeurlPS, pp. 7827-7838, 2018
Niv Nayman, Asaf Noy, Tal Ridnik, Itamar Friedman, Rong Jin, and Lihi Zelnik-Manor. XNAS: neural architecture search with expert advice. CoRR, abs/1906.0803. 2019.
Yurii Nesterov. Introductory Lectures on Convex Optimization Basic Course, volume 87 of Applied Optimization. Springer, 2004,
Hieu Pham, Melody Y. Guan, Barret Zoph, Quoc V. Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 4092-494400 4101. PMLR, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In AAAI, pp. 4789. AAAI Press, 2019.

---

Published as a conference paper at ICLR 2020
Christian Sciuto, Kaicheng Yu, Martin Jaggi, Claudiu Musat, and Mathieu Salzmann. Evaluating the search phase of neural architecture search. arXiv preprint arXiv:1922.081422 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. ICLR, 2015.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In CVPR, pp. 1-9. IEEE Computer Society, 2015.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc Le. Mnasnet: Platform-aware neural architecture search for mobile. In CVPR, pp. 2820- 2828. Computer Vision Foundation IEEE, 2019.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. arXiv preprint arXiv:1904.0150 2019a.
Sirui Xie, Hehui Zheng, Chunxiao Liu, and Liang Lin. SNAS: stochastic neural architecture search. In ICLR (Poster). OpenReview.net, 2019b.
Zirui Zhou, Qi Zhang, and Anthony Man-Cho So. 1.p-norm regularization: Error bounds and con- vergence rate analysis of first-order methods. In ICML, pp. 1501-1510, 2015.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V. Le. Learning transferable architectures for scalable image recognition. In CVPR, pp. 8697-8710, IEEE Computer Society, 2018.
12

---

Published as a conference paper at ICLR 2020
APPENDIX A EXPERIMENTAL SETUP
A.1 DATA PRE-PROCESSING AND AUGMENTATION
Our experiments are conducted on CIFAR-10/100 Krizhevsky et al. 2009) and Tiny-ImageNet- 200. CIFAR-10/100 contains 50,000 training images and 10,000 test images of x2x32 32 pixels in 10 and 100 classes respectively. validation images and 10,000 test imaged in 200 classes, We adopt the same data pre-processing and argumentation as described in DARTS (Liu et al. 2019): zero padding the training images with 4 pixels each side and then randomly cropping them back to 32x32 CIFAR- 10/100 and 64 64 on Tiny-Imagels www---mageeee20000 randomly flipping training images horizontally; normalizing training images with the means and standard deviations along the channel dimension.
consists of 100,000 training images, 10,000
A.2 SAMPLING OF RANDOM VARIANTS
For -nnoe NAS cell, there are (M-1) possible connections with M input nodes and one output node. There are therefore hundreds to thousands of possible randomly connected variants for each popular NAS cell. The random variants of operations consist of a similar or even higher amount of architectures. Due the prohibitive cost of comparing popular NAS cells with all variants, randomly sample some variants to understand why the popular NAS cells are selected.
[N-
Given a NAS cell C, we fix the partial order of intermediate nodes and their accompanying op- erations. We then replace the source node of their associated operations by uniformly randomly sampling node from their proceeding nodes in the same cell to get their randomly connected variants. Similarly, given a NAS cell C, we fix the partial order of intermediate nodes and their con- nection topologies. We then replace the operations couping each connection by uniformly randomly sampling from candidate operations to get their random variants of operations.
A.3 ARCHITECTUREE AND TRAINING DETAILS
For experiments on CIFAR-10/100 and Tiny-ImageNet-200 the neural network architectures are constructed by stacking L 20 cells. Feature maps down-sampled at the L/3-th and 2L/3-th the stride of the first convolu-
cell the entire architecture with stride 2. For Tiny-ImageNet-2D0 tional layer is adapted to 2 reduce the input resolution from 64 x 64 to 32 32. A more detailed building scheme can be found in DARTS (Liu et al. 2019).
In the default training setting, apply stochastic gradient descent (SGD) with learning rate 0.025, momentum 0.9, weight decay x 10-4 and batch size 80 to train the models for 600 epochs on CIFAR 10/100 and 300 epochs on Tiny-ImageNet-200 to ensure the convergence. The learning rate is gradually annealed to zero following the standard cosine annealing schedule. To compare the convergence under different learning rates in Section we change the initial learning rate from 0.025 to 0.25 and 0.0025 respectively.
A.4 REGULARIZATION
Since regularization mechanisms shall affect the convergence (Zhou et al. 2015), architectures are trained without regularization for neat empirical study in Section|4] The regularization mechanisms are only used in Section 5 to get the converged generalization performance of the original and adapted NAS architectures CIFAR-10/100 and Imng-ImageNet-2000 as shown in Table
There are three adopted regularization mechanisms on CIFAR-10/100 and Mnny-ImageNet-200 in this paper: cutout (Devries & Taylor (017). auxiliary tower (Szegedy al.) (2055) and drop
path (Larsson et al., 2017). We apply standard cutout regularization with cutout length 16. More- over, the auxiliary tower located at 2//3-th cell of the entire architecture with weight 0.4. We apply the same mmeeall-incceasee drop path schedule as in NASNet (Zoph et al. 2018) with the maximum probability of 0.2.
SSince label is attached to Tiny- Ne2geN test dataset, we instead use its validation dataset to get the generalization performance of various architectures. We still name as the test accuracy/error for hrief.
13

---

Published as a conference paper at ICLR 2020
APPENDIX B MORE RESULTS
B.1 NAS ARCIIITECTURES AND THEIR VARIANTS
We compare the width and depth of popular NAS architectures and their variants of random nections in Table 2 The random variants are sampled following the method in Appendix [A.2] We further show the connection topologies of popular NAS and their partial random variants of connec- tions in Figure 10 and Figure
Table Comparison of the width and depth of popular NAS cells and their randomly variants of con- nections. The name of the popular NAS cell is followed by its width and depth, which is separated by a comma. The width of a cell is conventionally computed by assuming that each intermediate node shares the same width Notably, the width and depth of random variants are in ascending and descending order respectively from C1 to C13. Moreover, the popular NAS architectures achieve the largest width and nearly the smallest depth among all the variants.
Base Cell
C2
C2
C3
C4
Co
Go
C
Ce
Co
Ci
C11
Ciz
Cis
DARTS (3,5c.3)
20.1
2:
2r,
1,50
2.5
2.5c. 3
2.5c,
2.50. 3
3r.
Sc.3
36,5
3.50
3.5c,
26.6
2.5c.6
3.5c, 3
AmuebaNet (dc.4)
1.5
1.5c.5
1.5e.
1.5r.
2e.6
2.5g
2.5c,3
2.5r.3
3.5e,
NASNet (Sc.2)
1.6.
1.c.5
2c,6
2..6
2.5c.5 5
2.5c.5
Sc,
3c,
3.5c.
3.5c,
3.5c, 4
3.5e: 3
3.5c,
(a) 3.5c, 4
(b) 3.5c, 3
(c) 3c,
(d) 2.5c, 5
(c) 2c, 6
Figure 10: Connection topology of AmoebaNet cell (Real et al. 2019) and its part of randomly connected variants. Each sub-figure reports the width and depth of cell separated by comma. The leftmost one is the original connection from AmoebaNet normal cell and others are ones randomly sampled. The width of cell is also computed by assuming that each intermediate node shares the same width c. Notably, the original AmoebaNet cell has the largest width and almost the smallest depth among these cells.
4c,
(b) 3.5c, 3
(c) 3c,
(d) 2.5c,
(e) 2c, 5
Figure 11: Connection topology of SNAS cell under mild constraint Xie et al. 2019b) and its part of randomly connected variants. The width and depth of a cell are reported The leftmost one is the original connection from SNAS normal cell and others are the ones randomly sampled. The width of cell is conventionally computed by assuming that each intermediate node shares the same width c. Notably, the original SNAS cell has the largest width and the smallest depth among these cells.
title of each plot.
14

---

Published as a conference paper at ICLR 2020
65-
6P'9
60-
Cp
Gpmeto
65-
Czune
Cp
Cymmte
75-
75
75
75-
200
402
820
200
402
120
0
200
402
120
200
402
600
(a) DARTS
(b) ENAS
(c) AmoebaNet
(d) NASNet
Figure 12: More test accuracy (%) curves of DARTS, ENAS, AmoebaNet, NASNet and their random variants of operations on CIFAR-10 during training.
Table 3: Comparison of the parameter size (MB) of popular NAS cells and their randomly variants of operations. Cy denotes the original NAS cell and C1 to C1o denote the random variants. Notably, there gap of ~ 30% between the parameter size of the smallest architecture and one of the largest architecture.
Base cell
C
C3
C
C7
Cs
C
Cio
DAKTS 3.86
3,37
2.70
3.19
3.49
3.31
ENAS
3.45
3.19
2.98
2.70
3.67
3.03
3.85
3.26
3.81
3.29
AmoebaNet NASNet
2.86
2.41
3.10
3.28
3.42
2.75
3.83
3.45
3.19
2.98
2.70
3.67
3.03
3.85
3,26
3.81
3,29
B.2 CONVERGENCE
In this section, we plot more test loss curves on CIFAR-10 (Krizhevsky et al. 2009) original popular NAS architectures and their (12) randomly connected variants, shown in Figure 1 Fig- ure 14 and Figure [6 The depth and width of these 12 randomly connected variants can be found in Table Notably, the width and depth of random variants (from C₁ to C12) are in ascending and descending order respectively. Moreover, the popular NAS architectures achieve the largest width and nearly the smallest depth among all the variants. As shown in the following figures, the popular NAS cells, with larger width and smaller depth, typically achieve faster and more stable conver- gence than the random variants. Furthermore, with the increasing width and the decreasing depth, the convergence of random variants approaches to the original NAS architecture.
350
0.50
0.50
350
0.5
0.45
0.45
0.45
8.40
0.43
Gyen
0.43
0.40
Cg
0.3
0.35
0:35
0.35
Cyios
0.0
0.30
0.30
0:30
025
0.25
0.25
0:55
020
452
600
0.20
200
400
0.20
202
400
00
0.0
200
00c
Figure 13: Test loss curves of DARTS and its variants on CIFAR-10 during training.
Canork
Clmokk
Ct
Figure 14: Test loss curves of AmoebaNet and its variants CIFAR-10 during training.
15

---

Published as a conference paper at ICLR 2020
Pm
255-
0.35
400
Figure 15: Test loss curves of ENAS and its variants on CIFAR-10 suring training.
Charee
Cy
Countt
0.2
600
z00
202
410
0.0
500
Figure 16: Test loss curves of NASNet and its variants CIFAR-10 suring training.
B.3 LOss LANDSCAPE
In this section, we visualize loss landscapes for popular NAS architectures and their randomly con- nected variants. The depth and width of cell are highly correlated. For example, the depth and width cannot reach their maximum simultaneously. With the increasing width, the average depth of cells grouped by the same width decreasing shown in Table 2
We therefore only group the results (including the ones from original NAS architectures) with various width levels of cell for a better comparison. Notably, the architectures with wider and shallower cells have smoother and
benigner loss landscape, as shown in Figure 17 Figure 18 Figure 19 and Figure 20 which further supports the results in Section 4.2.1
(a) 2c
(b) 2.5c
(c) 3c
(d) 3.5c
Figure 17: Loss contours of DARTS and its variants with random connections on the test dataset of CIFAR-10.
16

---

Published as a conference paper at ICLR 2020
(a) 1.5c
(b) 2c
2.5c
(d) 3c
(e) 3.5c
Figure 18: Loss contours of AmoebaNet and its randomly connected variants on the test dataset of CIFAR-10.
(a) 1.5c
(b) 2c
(c) 2.5c
(d) 3c
(c) 3.5c
Figure 19: Loss contours of ENAS and its randomly connected variants on the dataset of CIFAR- 10.
(a) 1.5c
(b)
2.5c
(d) 3c
(c) 3.5c
Figure 20: Loss contours of NASNet and its randomly connected variants on the test dataset of CIFAR-10.
B.4 GRADIENT VARIANCE
this section, we visualize the gradient variance (i.e., g(a, 3) as defined Section 4.2.2) for the popular NAS architectures as well their variants with random connection, such AmoebaNet in Figure 21 DARTS in Figure 22 ENAS in Figure 23 and NASNet in Figure 23 The z-axis has been group the results based the width of cells.
scaled by 1 for better visualization. Similarly, Notably, architectures with wider and shallower cells achieve relatively smaller gradient variance, which further confirms the results in Section 4.222
17

---

Published as a conference paper at ICLR 2020
(a) 1.5c
(b) 2c
(c) 2.5c
(d) 3c
(e) 3.5c
Figure 21: 3D surfaces the gradient variance from AmoebaNet and its randomly connected vari- ants on the test dataset of CIFAR-10.
(a) 2c
(b) 2.5c
(c) 3c
(d) 3.5c
Figure 22: 3D surfaces of the gradient variance from DARTS and its randomly connected variants on the test dataset of CIFAR-10.
(a) 1.5c
(b) 2c
(c) 2.5c
(d) 3c
(c) 3.5c
Figure 23: 3D surfaces of the gradient variance from ENAS and its randomly connected variants on the test dataset of CIFAR-10.
18

---

Published as a conference paper at ICLR 2020
(a) 1.5c
(b) 2c
(c) 2.5c
(d)
(c) 3.5c
Figure 24: 3D surfaces of the gradient variance from NASNet and its randomly connected variants on the test dataset CIFAR-10.
B.5 ADAPTED TOPOLOGIES
In this section, visualize the adapted architectures (in Figure 25 Notably, The adapted connection topologies are not only applied in the normal cell but also the reduction cell. The adapted architectures are compared with popular NAS architectures examine the impacts of the common connection pattern on generalization.
investigate in Section 5
X
(a) NASNet, 5c, 2 (b) AmoebaNet, 3c, 2 (c) ENAS, 5c,
(d) DARTS, 4c, 2 (e) SNAS, 1c, 2
Figure 25: Adapted topologies of cells from popular NAS architectures. The title each sub-figure includes the name of the architecture, width and depth of the cell following definition. Notably, these cells achieve the largest width and smallest depth in their original search space.
APPENDIX C THEORETICAL ANALYSIS
C.I
SETUP
Wa
Win
Wrey
(n)
by
(a) case I: widest cell
(b) case 11: narrowest cell
Figure 26: Two architectures to compare in the theoretical analysis: (a) architecture with widest cell; (b) architecture with narrowest cell. The notation i and denote the values of objective function f and f evaluaaed at input respectively.
19

---

Published as a conference paper at ICLR 2020
C.2 BASICS
We firstly compare the gradient of case I and case Il shown in Figure 26 For case I, since y W æ, the gradient to each weight matrix W()) is denoted by
0f of 0y(
x
OW
Similarly, since 7( II== W( x for the case II, the gradient to each weight matrix W is denoted by
of
n
II woif of
Σ
x)
(2)
OW
k=j j=it1
wOlT Of
Σ II
WoyT
k= j=++1
EI
woIj" 0f OW())
(4)
k= j=4+
Exploring the fact that
af ag Ty
we get (4) by inserting (1) into (3).
C.3 PROOF OF THEOREM 4.2
Due to the complexity of comparing the standard Lipschitz constant of the smoothness for these two cases, we instead investigate the block-wise Lipschitz constant (Beck & Tetruashvili (2013). In other words, we evaluate the Lipschitz constant for each weight matrix W while fixing all other matrices. Formally, we assume the block-wise Lipschitz smoothness of case I las
as oʃ a
< (,)()
W(()
W
A ( w
(5)
The default matrix norm adopted is 2-norm. And (()) o denote possible assignments for W(O,
())
Denoting that ( ||WO]] ness of case II as
which is the largest eigenvalue of matrix Wi),, we can get the smooth-
aî Ow
05
WOIST( of ww(h)
as aw? (K)
WO)T
(6)
aw 2
j=
0f
0f
WG
(7)
aw
aw
1=1
(G)
(8)
X
1=1
1-1
(
I (
w w
(9)
5=1
20

---

Published as a conference paper at ICLR 2020
We get the equality in (6) since j > i and WG) keeps the same for the computation of block- Lipschitz constant of W((), Based on the triangle inequality of norm, we get (7) from (6). We get (8) from (7) based on the inequality |[VI|| S [[W]] [|V and the assumption of the smoothness for case I in (5), Finally, since we are evaluating the block-wise Lipschitz constant for W( W(K) W
while + which leads the final inequality (9).
C.4 PROOF OF THEOREM
Similarly, we assume the gradient variance of case I is bounded
0s
af OW(6
2
E
IE
I (o(1)
(10)
OWa
The gradient variance of case II is then bounded by
of
n
of
as
E
E
E
W
E
(11)
(W())
OWG
OW
Ow
k=
jmit1
2
05
0s
nE
W
E
W
(12)
OW
(W
R=
-=
j=1
(k)
1012
(13)
We get (12) from (11) based on
inequality. Based on the inequality |[V]| < [[]] [[V]| and the assumption of bounded gradient variance for case in (10), get the final inequality.
21


Reviews:
[{"review_id": "HJx8NdWaKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\nThis paper tries to understand the characteristics of the architectures found by common NAS methods in the cell-search space. Specifically it characterizes the cell-search space used by DARTS, SNAS, AmeobaNet and finds that a most of these search methods find cells which are wide and shallow in depth (they give a specific definition of width and depth for characterizing cells). In fact these cells are usually the widest and shallowest architectures in their search space. The author empirically find that because these kinds of topologies converge faster during training and inevitably every NAS algorithm during search don't train upto convergence but only up to a bit and make decisions based on partially converged statistics there is a bias in selection towards these topologies. They also provide theoretical intuition to back-up these empirical findings. \n\nSecondly they analyze the generalization performance of such wide and shallow cell structures accidentally emphasized by search procedures. They take the common cell structures found by common NAS algorithms (NASNet AmoebaNet, ENAS, DARTS, SNAS) and make them the widest and shallowest possible in the search space (following the SNAS cell connection pattern) while keeping number of parameters as constant as possible. They find that on cifar10 the test error of the adapted architectures usually increase a bit while on cifar100 the adapted architectures decrease a bit. \n\nComments:\n\n- Overall the paper is interesting and well-written. Definitely liked the fact that wide and shallow networks are being accidentally biased towards during search. Liked the empirical analysis and theoretical insights backing it up.\n\n- The generalization experiments suggest to me that on bigger datasets wider and shallower networks might be better for generalization actually. Can we take the cell architectures found by various algorithms and 'scale-up' to ImageNet by doing the usual trick of replicating more of the cells together and training? At least going by Table 1 I find myself not agreeing with the statement \"The results above have shown that architectures with the common connection pattern may not generalize better despite of a faster convergence.\" On cifar100 wider and shallower is better. Perhaps on ImageNet they will be even better? So NAS algorithms' strategy of training partially may be exactly the right thing to do? Any thoughts?\n\n- Any idea about if this pattern extends to RNN space as well or only limited to CNNs?\n\n- Overall my main gripe is that while it is interesting findings but I am not sure I understood the main takeaway or significance of these results especially the generalization ones and how it informs search algorithm design.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Bke6KMzcqr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper makes an interesting observation and tries to explain what causes it: architecture search methods tend to favor models that are easier to optimize, but not necessarily better at generalization.  I lean towards accepting the paper but there is some clear room for improvement.\n\nThe paper shows that NAS methods comes up with shallower but wider cells. \n- These cells are easier to optimize because they have a smoother loss surface and lower gradient variance. \n- Being easy/fast to optimize is favored by a NAS method because the models are typically not trained to convergence. Instead they are evaluated after a brief period of training. \n- This leaves the question: why are they smoother.\n\nBefore going into the comments I want to state that I am very happy to see that a paper providing an analysis of existing methods to enhance our understanding. This is very much needed in the architecture search community. \n\n==== Comments ====\n- Could you describe what exactly is plotted in Fig. 5, 6 and 7. Specifically what are the aces. . It would make the manuscript more self contained. This point is also one of the main reasons why I did not give the manuscript a higher score. I am unsure of what is plotted but I am giving this manuscript the benefit of the doubt because it is consistent with my own experience.\n\n- So far in the main text, most results focus on DARTS. It would be interesting to see the same consistent behavior is also present when comparing cells originating from different search spaces. (This is slightly different than the setting where the experiment is repeated on isolated search spaces). If this comment is unclear, please ask for a clarification.\n\n- Would it be possible to alter the conclusions by modifying the initialization of the weight matrix. It appears to be the case that the smoothness and the variance both depend on the eigenvalues of the weight matrices. If we could make them more well behaved we could potentially make the narrower architectures train faster?\n\n- Can you use a better term than common connection pattern in the abstract and conclusion. In general the abstract and conclusion could be written in a crisper and more to the point way.\n\n- Please update Table 1 to actually include parameter sizes. This would make the result more reliable. Also the adapted cells need to be explicitly provided. \n\n- Could you provide me with a better understanding of the difference between standard lipschitz and block lipschitz.\n\n==== More minor issues ====\n#) Correction required\nIn section 2, Zoph et al. is cited where it is argued that weight sharing could detrimental for the performance of nas methods. However this paper does not use weight sharing\n\n#) Corrections recommended\nXie et al. 2019 is said to be state of the art. In the actual publication the authors only claim to be competitive. I believe that this is a more balanced statement since those results are not always best on all dimensions (sometimes better on FLOPS but not parameters, unclear whether they would be faster on an actual device, on the large scale results they do lag behind in quality too.)\n\n#) My apologies for the slight digression but I do not think that using the Sciuto et al. paper is a good reference to discount weight sharing approaches or claim that random search is equally good. Some of their experiments are performed on a tiny search space with only 32 models. This gives random search a high probability of getting the right model, while a simple bias in the algorithm might cause it to be sub-optimal. That experiment does not show that random search is as good. Also on the PTB task, their reported results are worse than the open sourced implementation for DARTS. This means to me that this paper cannot be used as a reliable reference. \n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJlFXM9aKB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "--- Update after author's response ---\n\nThank authors for providing the detailed response to all my concerns. I am revising my rating to weak accept.\n\nSpecifically, generalising with 52 different variants of depth-width settings are enough, and the updated version is more solid than the earlier one. I think this paper should be accepted.\n\n\nSummary:\nThe paper observed one common pattern of searched cell by 5 NAS algorithms, which is the cell found usually has large width but small depth structure, and claims the reason of such pattern is because architectures with shallow but wide structure converge fast during training, and thus are sampled by the NAS policy. To justify this fast convergence claim, the paper proposed to 1) define a width-depth level (width based on feature maps dimension, and depth based on its DAG connection) for each cell in the search space, and randomly sampled one architecture at each level on top of some best-cell discovered by NAS algorithms, 2) training them on original task from scratch independently, and provide visualization of training curve under various learning rate settings, loss landscape as well as gradient variance plot. For theoretical analysis, the paper formulates the narrowest and widest cells, and showing the difference of gradient is bounded by its Lipschitz smoothness of parameter matrices, and usually such variance indicates the widest architecture could converge faster than the narrowest one. \n\nWhilst this observation is interesting, I found the empirical and theoretical justifications seem to be insufficient to support the claims for the following reasons, 1) The experiments are overwhelmingly built on top of **1** architecture (even obtained from random sampling) of each width-depth level, and it may not well represent the common behavior in the search space, thus the generalization of these claims remains questionable; 2) Theoretical analysis showing the gradient variance difference of narrowest architecture is bounded comparing to the widest cell, however, in practice, these architectures are not properly evaluated. Without proper extension, it is hard to conclude that such difference bound between a wider and narrower architecture pair; 3) experiments in supplementary negatively affects the generalizability of this paper, since the observed trend on DARTS search space does not agree with the one on AmoebaNet and SNAS cases; 4) paper claims the NAS algorithm tends to pick the fast converging architectures more than those late converged one, while intuitive, without showing some detailed process about how NAS algorithms converge, and which architectures they actually sampled during the search phase. \n\nNevertheless, I do agree that this paper has a clear motivation, and the observation is interesting and important. If the author could show the conclusion still hold after scaling the experiments, I am learning to accept this paper in the end.\n\n\nStrength\n+ Observation of these NAS algorithms tends to pick wide but shallow cell type is interesting, motivation of this work is well justified.\n+ Experiments are throughout, instructive under the paper's current setting.\n+ Theoretical justification for the gradient variance between the narrowest and widest cells are sound. \n+ Paper is well written and easy to follow, the figures are presented clearly.\n\nWeakness\n\n- Insufficient experimental setting to support the claim.\nMy major concern is that under the current experiment design, it is not clear if the observation is well justified, and impedes the main contribution. As mentioned in the review's summary, it is not that convincing that, for each width-depth level, one architecture is enough. I understand exploiting all the variants is resource consuming, however, without such experiments, the current experiments can be impacted by many factors, such as, 1) as in Appendix A2, for each level, the paper \"fixed the partial order of their intermediate nodes\" and \"replace the source node of their associated operations by uniformly randomly sampling a node from their proceeding nodes in the same cell\", if I understand correctly, this means the operations will remain the same. However, since these best architectures are searched over both operation and topology connection, new architectures generated from this way may be sub-optimal, hence the larger gradients or slow convergence is not only because they are \"narrower\" and \"deeper\". Without proper isolation, it is not possible to conclude as in paper. \n\nTo this end, I suggest author provide the following experiments, 1) sampling all the variants at each level, within a search space like NASBench-101[1], where all the architecture performances are known, 2) at least sampling a sufficient number in the current space (probably > 30 to be statistically significant); 3) Random sampling a small topological variances, then run NAS search algorithms to search the best operation set, then redo the experiments in the paper. \n\n- Trending of DARTS evaluation results does not agree with SNAS and AmoebaNet.\nIn Figure  5 (loss landscape plot) and Figure 6 (gradient variance heatmap) for DARTS, the wider-shallower architectures are better comparing to narrower-deeper ones, however, this trend is not significant in Figure 14,16 for AmoebaNet space and Figure 15, 17 for SNAS space. After a closer look, I noticed in Figure 2, the Darts C3 and C4, input node x0 is not connected to the graph, while C, C1, C2, and all the topologies in Figure 10, 11, x0 is connected. Could the author(s) comment on this? Will this be the reason why the C3, C4 DARTS are worse than other architectures?\n\nMinor comments\nPage 1 - Introduction paragraph 3 line 1 - 'typologies': is this referring to 'topologies'?\nTable 1 - Adapted architectures on CIFAR-10 are mostly worse, even on CIFAR-100, they are better in a small margin. This does not support the claim well.\nFigure 9 - Could the author provide the width-depth information for each index? \n\nReference\n[1] Ying et al. NAS-Bench-101: Towards Reproducible Neural Architecture Search, ICML'19.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper reports interesting NAS patterns, supported by empirical and theoretical evidence that the pattern arises due to smooth loss landscape. Reviewers generally agree the this paper would be of interest for the NAS researchers. Some questions raised by reviewers are answered by authors with a few more extra experiments. We highly recommend authors to carefully reflect on reviewers both pros and cons of the paper before camera ready.

Decision: Accept (Poster)