Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis
Authors: Wuyang Chen
Wei Huang
Xinyu Gong
Boris Hanin
Zhangyang Wang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Neural Network Gaussian Process
Convergence
Neural Network Architecture

Abstract: Advanced deep neural networks (DNNs), designed by either human or AutoML algorithms, are growing increasingly complex. Diverse operations are connected by complicated connectivity patterns, e.g., various types of skip connections. Those topological compositions are empirically effective and observed to smooth the loss landscape and facilitate the gradient flow in general. However, it remains elusive to derive any principled understanding of their effects on the DNN capacity or trainability, and to understand why or in which aspect one specific connectivity pattern is better than another. In this work, we theoretically characterize the impact of connectivity patterns on the convergence of DNNs under gradient descent training in fine granularity. By analyzing a wide network's Neural Network Gaussian Process (NNGP), we are able to depict how the spectrum of an NNGP kernel propagates through a particular connectivity pattern, and how that affects the bound of convergence rates. As one practical implication of our results, we show that by a simple filtration of "unpromising" connectivity patterns, we can trim down the number of models to evaluate, and significantly accelerate the large-scale neural architecture search without any overhead.

Deep Architecture Connectivity Matters for Its Convergence: A GrainGr Analysis
Wuyang Chen University of Texas at Austin
Wei Huang" RIKEN AIP
Xinyu Gong University of Texas at Austin
Boris Hanin
Zhangyang Wang University of Texas at Austin
Princeton University
Abstract
Advanced deep neural networks (DNNs), designed by either human or AutoML algorithms, are growing increasingly complex. Diverse operations are connected by complicated connectivity patterns, e.g., various types of skip connections. Those topological compositions loss landscape and facilitate the gradient flow in general. However, remains elusive to derive any principled understanding of their effects the DNN capacity or trainability, and to understand why or in which aspect one specific connec- tivity pattern is better than another. In this work, theoretically characterize the impact of connectivity patterns on the convergence of DNNs under gradient descent training in fine granularity. By analyzing wide network's Neural Net- work Gaussian Process (NNGP), we are able to depict how the spectrum of an NNGP kernel propagates through particular connectivity pattern, and how that affects the bound of convergence rates. As one practical implication of our results, we show that by simple filtration on "unpromising" connectivity patterns, we can trim down the number of models to evaluate, and significantly accelcrate the large-scale neural architecture search without any overhead. Code is available https: / thub. com Cwoo//vITA-rreee ar aarchitenn wwthiitecttreeeeeeeeeeeeeeeeeeee tew.utteeeeeeeeeeeeennc...
empirically effective and observed to smooth the
Introduction
Recent years have witnessed substantial progress in designing better deep neural network architectures. The common objective is to build networks that are easy to optimize, of superior trade-offs between efficiency and accuracy, and are generalizable diverse tasks and datasets. When developing deep networks, how operations (linear transformations and non-linear activations) are connected and stacked together is vital, which is studied in network's ss convergence
[88 71 75 complexity [47 50
21), generalization
14 g 61]. loss landscapes [36] 20 5T] etc.
Although it has been widely observed that the performance of deep networks keeps being improved by advanced design options, our understanding remains limited on how a network's 's properties influenced by its architectures. For example, in computer vision, design trends have shifted
to manually elaborated connectivity patterns (ResNet 25 DenseNet (28). etc.). While people observed smoothed loss landscapes (36), mitigated gradient vanishing problem [4. and better generalization (29], these findings only explain the effectiveness of adding skip connections in general, but barely lead to further "finer-grained" insight on more sophisticated composition of skip connections beyond ResNet. Recently, the AutoML community tries to relieve human efforts and propose automatically discover novel networks from
from vanilla chain-like stacked layers 3
32 53
Equual Contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

gigantic architecture spaces 772 46]. Despite the strong performance [57] 27 62 188, the searched architectures are often composed of highly complex (or even randomly wired) connections, leaving challenging to analyze theoretically.
Understanding the principles of deep architecture connectivity is of significant importance. Scien- tifically, this helps answer why composing complicated skip connection patterns has been such an effective "trick" in improving deep networks' empirical performance. Practically, this has direct guidance in designing more efficient and expressive architectures. To close the gap between our theoretical understandings and practical architectures, in this work we target two concrete questions:
Q1: Can we understand the precise roles of different connectivity patterns in deep networks?
Q2: Can we summarize principles how connectivity should be designed in deep networks?
One standard way study how operations and con- nections affect the network is to analyze the model's s convergence under gradient descent [19 2 [8). Here, we systematically study the relationship between the connectivity pattern of a neural network and the bound of its convergence rate. A deep architecture can be viewed a directed acyclic computational graph (DAG), where feature maps are represented as nodes and operations in different layers are directed edges linking features. Under this formulation, by analyzing the spectrum of the Neural Network Gaussian Process (NNGP) kernel, we show that the bound of the con- vergence rate of the DAG is jointly determined by the number of unique paths in a DAG and the number of parameterized operations on each path. Note that, 11 explored deep learning theorics to predict the promise of archi- tectures, their indicators were developed for the general deep network functions, not for fine-grained characterization for specific deep architecture topology patterns. Therefore, their correlations for selecting better architecture topologies are only empirically observed, but not theoretically justified. and also empirically verified.
R
ResNet
DenseNet
DARTS
Connectivity patterns of deep net- works are growingly more complex, including ResNet (25, DenseNet (28), and architectures sampled from the DARTS search space (4D) com-
Figure 1:
although several prior arts 44
10
monly used in neural architecture search (NAS).
In contrast, our fine-gres -eeiira conclusion is
Based on this conclusion, we present two intuitive and practical principles for designing deep architecture DAGs: the "effective depth" d and the "effective width" m. Experiments on diverse architecture benchmarks and datasets demonstrate that d and m can jointly distinguish promising connectivity patterns from unpromising ones. As a practical implication, our work also suggests a cheap pelug-and-play" method to accelcrate the neural architecture search by filtering out potentially unpromising architectures at almost zero cost, before any gradient-basee architecture evaluations. Our contributions are summarized below:
We first theoretically analyze the convergence of gradient descent of diverse neural network architectures, and find the connectivity patterns largely impact their bound of convergence rate.
From the theoretical analysis, we abstract two practical principles on designing the network's connectivity pattern: "effective depth" d and "effective width" m.
Both our convergence analysis and principles on effective depth/width are verified by experiments on diverse architectures and datasets. Our method can further significantly accelerate the neural architecture search without introducing any extra cost.
2
Related works
2.1 Global convergence of deep networks
Many works analyzed the convergence of networks trained with gradient descent 31
68
22
9
Convergence rates were originally explored for wide two-layer neural networks 60,
54
55
38
33 More recent works extended the analysis to deeper neural networks [2] 18
42
74
1
75
30
and showed that over-parameterizer networks can converge to the global minimum with random
initialization if the width (number of neurons) is polynomially large as the number of training samples. In comparison, we expand such analysis to bridge the gap between theoretical understandings of general neural networks and practical selections of better "fine-grain tine-grained" architectures.

---

2.2 Residual structures in deep networks
Architectures for computer vision have evolved from plain chain- like stacked layers 33
32
to elaborated connectivity patterns (ResNet (25), DenseNet [28], etc.). With the development of AutoML. algorithms, novel networks of complicated operations/conneciooss were discovered. Despite their strong performance [57] 27, 62 58), these architectures are often composed of highly complex connections and are hard to analyze. (52] defined the depth and width for complex connectivity patterns, and studied the impacts of network topologies in different cases. To better understand these residual patterns, people tried to unify the architectures with different formulations. One seminal way is represent network structures into graphs, then randomly sample different architectures from the graph distribution and empirically correlate their generalization with graph-related metrics [62] 677. Other possible ways include geometric topology analysis [6), network science [5), etc. For example, [5] proposed NN-Mass by analyzing the network's ' layer-wise dynamic isometry, and then empirically linked to the network's convergence. However, none of those works directly connect the convergence rate analysis to different residual structures.
2.3 Theory-guided design of neural architectures
Particularly related to our work is an emerging research direction, that tries to connect recent deep learning theories guide the design of novel network architectures. The main idea is to find theoretical indicators that have strong correlations with network's 's training or testing performance. 44 pioneered training-free NAS method, which empirically leveraged sample-wise activation patterns to rank architectures. [45 leveraged the network's ' NNGP features to approximate its predictions. Different training-free indicators were evaluated in (T] and the "synflow" measure [59] was leveraged as the main ranking metric. [IO] incorporated two theory-inspired metrics with supernet pruning as the search method. However, these works mainly adapted theoretical properties of the general deep neural network function: their correlations with the concrete network architecture topology are only empirically observed, but not theoretically justified.
3 Topology matters: convergence analysis with connectivity patterns
In this section, we study the convergence of gradient descent for deep networks, whose connectivity patterns can be formulated as small but representative direct acyclic graphs (DAGs). Our goal to compare the convergence rate bounds of different DAGs, and further establish links to their connectivity patterns, leading to abstracting design principles.
3.1 Problem setup and architectures notations
W
XOO
X
x OOtpptt)
We consider network's DAG as illustrated in Figure 2 (hh (h E [0, Hl] is the feature map (node) and W is the operation (edge). X (0) is the input node, (H) is the out- put node (H- 3 in this case), and (1) X (H-) are intermediate nodes. The DAG is allowed be fully con- nected: any two nodes could be connected by an operation. Feature maps from multiple edges coming to one vertex will be directly summed up. This DAG has many practical instances: for example, is used in NAS-Bench-2. a popular NAS benchmark. The forward process of the network Figure M can be formulated as:
(Input)
di- rect acyclic graph (DAG). x is the fea- ture map (node). W is the operation (edge). h [0, H. here H = 3. If we remove edges or set some W as skip-connections (i.e., identity mappings), how would the con- vergence of this DAG be affected?
Figure 2: A network represented
(17),
()) ((W) x())
x ((W)(0.2) (0)) + (1.)
( ((W().)) (()) (1.3) x(1) + ((W()33) x2))
u = (3)
Feature (x) E | where m is the absolute width of an edge (i.c. number of neurons), and
E (1, is the final layer and u is the network's 's output. We consider three candidate operations for each edge: linear transformation followed by a non-linear activation, skip-
3

---

connection (identity mapping), or broken edge (zero mapping):
zero skip-connection
0
zero skip-connection
W(.
maxm
p(x) =
NO, m linear transformation
Ea o (z),
linear transformation
s,t (1,2,3), N is the Gaussian distribution, and o is the activation function. Co (Eo [o(x)))) is scaling factor to normalize the input in the initialization phase.
Consider the Neural Network Gaussian Process (NNGP) the infinite-widite limit [34], we define our K(()) = (x(+) (*)) and NNGP mean as b.o) = E 1 1,j E L. N for
NNGP variance as ij
N training samples in total. Both Ki and b, are taken the expectation over the weight distributions.
3.2 Preliminary: bounding the network's linear convergence rate via NNGP spectrum
first give the linear convergence of our DAG networks (Theorem 3.1 and also show the guarantee of the full-rankness of Amin (K(#)) (Lemma 3.1 J. For a sufficiently wide neural network, its bound convergence rate to the global minimum be governed by the NNGP kernel. The linear convergence rate for deep neural network of a DAG-like connectivity pattern is shown as follows:
Before analyze different connectivity patterns (Section
Theorem 3.1 (Linear Convergence of DAG). Consider DAG of H nodes and Pи end-to-end paths. At k-th gradient descent step on N training samples, with MSE loss L(k) 1 b1ly u(b)
suppose the learning rate = A
20(H)
and the number of neurons per layer m
[NP
(NPx)* NPgH (NPH) log ux 2200))
max
Ain (K(H))
2 (K(H:
we have
(
- u(b) (1-
M7mii (MAmm)(((1)))
- 110-
(3)
2
where PH is number of end-to-end puths from (0) to (#).
Remark 3.2. In our work, we will fixed small learning rate n across different network architec- tures, to focus analysis the impact of Xmii (K()). This is motivated by the widely adopted setting in popular architecture benchmarks 48 17 that we will follow our experiments.
The above theorem shows that the convergence rate is bounded by the smallest eigenvalue of K K(H,, and also indicates that networks of larger least eigenvalues will more likely converge faster. This requires that the K(H) has full rankness, which is demonstrated by the following lemma:
Lemma 3.1 (Full Rankness K (H)), Suppose a-)) is analytic and not a polynomial function. If no parallel data points, then Amii (K(H)
3.3 How does NNGP propagate through DAG?
Now are ready to link the DAG's connectivity pattern the bound of its convergence rate. Although different DAGs are all of the linear convergence under gradient descent, they are very likely to have different bounds convergence rates. Finding the exact mapping from Amin ()) to Amin K (?) will lead us to fine- mne-grained comparison between different connectivity patterns.
First, for fully-connected operations, we can obtain the propagation of the NNGP variance and mean between two consecutive layers:

---

grise
XTI
X
X11
XC21
(Input)
(Output)
(Input)
(Output)
(Input)
(Oulpu))
Figure 3: Three example DAGs, Solid blue arrows parameterized operations (e.g. fully-connected layer). Dashed arrows are con-parameierized operations (e-g. skip-connections). Removed edges are in light grey. See
Section 3.3 their convergence analysis. Left: sequential connectivity (DAG#1), Middle: parallel connectivity
(DAG#2). 2). Right: mixed of sequential and parallel connectivity (DAG#3).
Lemma 3.2 (Propagation K). Define the propagation as K f(K(--)) and b()) g(b When the edge operation is a linear transformation, we have:
_ f(K
Dican (VK!--1
K. [(K))
DD, P22002 (VX(
|K ( + v (0(1))122)))
c K 19//v !h! K
6 g(b² ((! DD x2
(4)
where 2, 21 and 22 are independent standard Gaussian random variables. Besides, DD= 1 f d2e 2²² is the measure for normal distribution.
V2x
Remark 3.3. Since by is constant, will not affect our analysis and will omit it below.
Remark 3.4. With centered normalized inputs, K
Our last lemma prepare states that N x N by its 2 x principal submatrix case.
bound the smallest eigenvalue of the NNGP kernel of
Lemma 3.3. For positive definite symmetric matrix K NNNN the smallest eigenvalue is bounded by the smallest eigenvalue of its 2 x 2 principal sub-matrix.
KNa Kj
K
Amnin K) S min Amin (f)
(5)
K2J
Now we can analyze the smallest eigenvalue Amin (#) for different DAGs. Note that here we adopt ReLU activation for three reasons: 1) Analyzing ReLU with the initialization at the edge-
of-chaos 23 exhibits promising results; 2) Previous works also imply that the convergence rate of ReLU-based networks depends on Åo [9]: 3) ReLU is the most commonly used activation in practice. Specifically, we set Ca = 2 for ReLU [18 23 Figure we show three representative DAGs (Hf 3). For fair comparison, each DAG has three linear transformation layers, i.c., they have the same number of parameters and mainly differ in how nodes are connected. After these three case studies, we will show a more general rule for propagation of (0)
DAG#1 (sequential connections). In this case, (..1)) (1,22) (2.3) linear transformation, and (0.2) W (0,3) (11,)) = zero (broken edge). There is only one unique path connecting from x (0) to (3), with three parameterized operations on it.
(O) ((K
(² f(K(2)
K (3) (2K
(6)
By Lemma
3.3
we calculate the upper bound of the least eigenvalue of (3) denoted Aangi=
K
(3)
J(K
K (((K(")))
Amiu
ii
Amin
= Amin
KC
(3)
KLG 3)
f(K
K 33
[(F(K (
K
j3
jJ
33
(7)
KCO
[(f((K K
1 - (K (0)) = >dnglo
= Amin
((F(F((())
(0)
where we denote the function composition f
(K (0))
F(F(F(K
5

---

DAG#2 (parallel connections). In this case, W00,3, ( W linear transformation. W ((1,2) skip-connection. and W zero (broken edge). There are three unique paths connecting from x to x with one parameterized operation on each path.
K K(1) K (0)
(8)
K (3) [(K ( + ((K + ((K(2) (
where C' is constant matrix with all entries being the same. Therefore:
K
(3)
K
(3)
3 (0)
3 (0))
Amin
Amin
K
(3)
K 33)
3
(0)
3K
)j
(9)
KDD
(0)
f(K
3Amin
3(1 - (KK Adng2
f(K)
(0))
K
(0)
DAG#3 (mixture of sequential and parallel connections). this case, ((,).,, (7 W = linear transformation, (0.33), w(1.2, W(1,3 skip connection. There four unique paths connecting from X (3), with 0/1/2 parameterized operations on each path.
K (1)) ((K(0))
K (()) f(K(()) (0) K(3) (2) + K() +((0) (0) K()) +
(10)
+ + ((2f(K(
Then we have:
K-(3)
K
4K
[(K
Amin
(3 (3)
K
1/
(3)
Amin
[F(K())
(0)
4K
ij
(0)
= 4 F(((
Adng3,
(11)
where f(K)) (0)
k(O)
f( b/
(0))
((2
sj
Conclusion: by comparing Eq. 9 and TT we can show the rank of three upper bounds of least cigenvalues as: Adag1 < Adag2 < dagg3 Therefore, the bound the convergence rate of DAG#3 is better than DAG#2, and DAG#1 is the worst. See our Appendix Clin supplement for detailed analysis.
General rules of propagation from (0) to (
Diagonal elements of (H) is determined by the number of unique paths from x (H).
Off-diagonal elements of (H) is determined by the number of incoming edges X (HH) and the number of parameterized operations on each path.
Thus, could simplify rules
P P-
Amin (K (1)) S min
S p=1
(12)
where P is number end-to-end paths from (0) to (H), dp is the number of linear transformation operations on the p-th path, and fdp indicates dy-power composition of This summary is based on the propagation of the NNGP variance. With this rule, we can quickly link the relationship between the smallest eigenvalue (H) and k()))
4 Practical principle of connectivity: effective depth and effective width
Eq. 12 precisely characterizes the impact of network's topology on its convergence. Inspired by above results, we observe two factors that control the A (1) P. the "width" DAG: (2) (p [1, PI), the "depth" of DAG. However, directly comparing convergences via Eq. 12 non-trivial (see our Appendix C because: (1) the complicated form of the NNGP propagation "f" (Eq. 3.2 (2) "P" and "d,-" "s are not truly free variables, as they still coupled together in the discrete topology space of a fully connected DAG.
Motivated by these two challenges, we propose practical version of our principle. We simplify the analysis of Eq. 12 by reducing "P" and "d,'"s to only two intuitive variables highly related to the network's ' connectivity patterns: the effective depth and effective width.

---

Definition 4.1 (Effective Depth and Width), Consider the directed acyclic graph (DAG) of a network. Suppose there are unique paths connecting the starting and the ending vertex. Denote the number of parameterized operations on the y-th path as dp. P E [1, PJ. We define:
d= E dp P
m Ep=1 1(dp 0)
Effective Depth
Effective Width
(13)
d
where [d, 0) 1 d, > otherwise is O.
Remark 4.2. In our experiments below, we consider fully-connected or convolutional layers as parameterized operations, ignoring their detailed configurations (kernel sizes, dilations, groups, etc.). We consider skip-connections and pooling layers as non non-parameterized operations.
The effective depth considers the averaging effects of multiple parallel paths, and the effective width considers the amount of unique information flowing from the starting vertex to the end, normalized by the overall depth. We will demonstrate later in Section 5.2 that performances of networks from diverse architecture spaces show positive correlations with these two aspects. While d and m may be loose to predict the best architecture, in Section 5.3 we will show that they are very stable in distinguishing bad ones. Therefore, using these two principles, we can quickly determine if an architecture is potentially unpromising at almost zero cost, by only analyzing its connectivity without any forward or backward calculations.
MNIST
5 Experiments
Training Accuracy
5.1 Empirical convergence confirms our analysis
(0-
We first experimentally verify our convergence analysis in Section 3.3 In all cases we use ReLU nonlinearities with Kaiming normal initialization (24). We build the same three computational graphs of fully-connected layers in Figure Three networks have hidden layers a constant width of 1024. We train the network using SGD with mini-batch of size 128. The learning rate is fixed at 1 x 10 No augmentation, weight decay, learning rate decay, or momentum adopted.
60-
20-
DAGe2
DMG03
200
1001
GCD
500
1000
Epochs
CIFAR-10
Training Accuracy (%)
Based on our analysis, on both MNIST and CIFAR-10, the convergence rate of DAG#1 (Figure 3 left) is worse than DAG#2 (Figure 3 middle), and is further worse than DAG#3 (Figure right). The experimental observation is consistent with this analysis: the training accuracy of DAG#3 increases the fastest, and DAG#2 faster than DAG#1. Although on CIFAR-10 DAG#1 slightly outperforms DAG#2 in the end, DAG#2 still benefits from faster convergence in most early epochs. This result confirms that by our convergence analysis, we can effectively compare the convergence of different connectivity patterns.
DACe1
DAG#2
DAG.35
Epochs
Figure 4: Empirical convergence of three DAG cases (Figure can verify our theo- retical analysis in Section 3 Small standard deviations of three runs are shown in shadows.
5.2 Extreme d or m leads to bad performance architecture benchmarks
In this experiment, our goal is to verify the two principles we proposed in Section 4 Specifically, we will leverage large number of network architectures of random connectivities, calculate their d and m., and compare their performance. We consider popular architecture benchmarks that are widely studied in the community neural architecture search (NAS). Licenses are publicly available.
The NAS- MMS-Bench-201 [17 provides 15,625 architectures that are stacked by repeated DAGs of four nodes (exactly the same DAG we considered in Section and Figure 2 It contains architecture's performance on three datasets (CIFAR-10, CIFAR- 100, ImageNet- 6- 120 (15)) evaluated under a unified protocol (i.e. same learning rate, batch size, etc., for all architectures). The operation space contains zero, skip-connection, convl x 1, comv3 x 3 convolution, and average pooling 3 x 3.
Lcage-scale architecture spaces: NASNet 73 Amoeha 44), PNAS (39], ENAS 46, DARTS 40)
These spaces have more operation types and more complicated rules allowed DAG connectivity
7

---

NAS vell on CIRMR 10
NAS. Blac 208 CIFAR 100
NSSBock XL Iwpllto 30
NSS UPESS PNAS
Eldt Rech
Widd
Effeci With
33
Deyth
Chocclo Depth
Deah.
[faccin Depth
Figure 5: In complete architecture space, heing extremely large small either the effective depth (d) or the effective width (m7) leads a connectivity pattern to bad performance (black) and large variance (large circle size). Each dot represents a subset of architectures of the same d and ris, The left three plots are results on CIFAR-IU 10,
CIFAR-100 1000 and ImageNet- 16- 16-120 from the NAS- Bench-201 17.. The rightmost plot is CIFAR- 10 from a
union of multiple large-scale spaces: NASNet [73 Amoeba 49) PNAS (9) ENAS [46). DARTS 40
Blue
areas indicate invalid DAG regions: DAG cannot be both deep and wide at the same time.
patterns, see Figure I bottom as an example. We refer to their papers for details. A benchmark is further proposed in [48] about 5000 architectures are randomly selected from each space above. and in total we have 24827 architectures pretrained on CIFAR-1O. We will use this prepared data
We show our results in 5 From all four plot (across different architecture spaces and datasets), it can be observed that, architectures of extreme depths or widths suffer from bad performance. We also calculate the multi-correlatior]] (Rt between the accuracy and the joint of both d and m,, and show legends in Figure 5 All four plots show positive correlations. It is worth noting that here each dot represents a subset of architectures that share the same d and m,, with possible different fine-grained topology layer types, indicating the generalizability of our proposed principles. The variance of performance in each subset is represented by the radius of the dot.
Remark 5.1. Our notion of "extreme d or m" targets complete space of DAGS: given the total number of nodes, any two nodes in the graph can be connected, and there are no topological restrictions or disabled edges (i.e., one cannot introduce any prior to the distribution of graph topologies).
5.3 A "elug-and-Play" method for accelerating NAS: bypassing extreme d and m
Inspired by the bad performance from extreme d or m discussed in Section 5.2 we are motivated to further contribute a pplug-and-play tool to accelerate practical NAS applications.
Method. In NAS, the bottleneck of search efficiency is the evaluation cost during the search. Our core idea is to use and m to pre-select architectures that are very likely to be unpromising before spend extra cost to evaluate them. Training- based NAS is slow: one has to perform gradient descent on each sampled architecture and use the loss or accuracy to rank different networks. We instead choose to improve two recent training-free NAS methods: NAS-WOT [44] and TE-NAS (1O] This is because our goal here is to accelerate NAS, and these two are state-of-the-art NAS works of extremely low search time cost. We plan to show that our method two training- free NAS works. The rationale is that, our d and m. are even much cheaper: we only do a simple calculation on a network's DAG structure, but NAS-WOT and TE-NAS still have to perform forward or backward on a mini-batch of real data. Although our d and m are only inspired from the optimization perspective, not the complexity or generalization, our method mainly filters out bad architectures at coarse level, but does not promote elites in fine-grained way.
even further accelerate these
NAS- WOT proposed to rank architectures by their local linear maps. Given a mini-batch of data, each point can be identified by its activation pattern through the network, and a network that can assign more unique activation patterns will be considered promising. NAS-WOT uses random sampling to search the architectures and rank them based on this training-free score. Our version: We will skip potentially unpromising architecture before leaving them for NAS-WOT to calculate their scores.
TE-NAS proposed to rank architectures by combining both the trainability (condition number of NTK) and expressivity (number of linear regions). TE-NAS progressively pruned a super network to single-path network, by removing unpromising edges of low scores.
2 Data is publicly available at
http://hwwb....eeccccooeeeeeeeee cdd only test accuracy available. Too fairly compare different connectivity patterns, we fix total number of convolutional layers per model as (out of 6 edges) on
and (out of 10 edges) on the union of large-scale architecture spaces. "See Appendix D for its definition.
8

---

Table 1: NAS Search Performance in DARTS space ImageNet. Our standard deviations over three random runs are included in parentheses.
Test Error( %)
Architecture
Params,
Search Cost (GPU days)
Search Method
top-1
top-5
NASNd-AA 7
26.0
8.4
5.3
2000
RL
AmtelaNNe-CC
60
24.3
7.6
6.4
3150
evolution
PNAS
25.8
8.1
5.1
225
SMBO
MnasNet-92
60
25.2
8.0
4.4
288 (TPU)
DARTS (2nd)
10
26.7
8.7
4.7
4.0
gradicat
SNAS (mildd
[5
27.3
9.2
4.3
1.5
gradicnt
GDAS [6]
8.5
5.3
0.21
gradient
Baye:NAS 70
26.5
8.9
3.9
0,2
gradient
P-DARTS
7.4
0.3
gradicut
PC-DARTS 64
25.1
7.8
5.3
0.1
gradient
PC-DARTS (ImageNot)
24.2
7.3
5.3
3,8
gradicut
ProxylessNAS (GPU) 0
24,9
7.5
7.1
8.3
gradient
SGAS (Cri avg) R5
24.42 (0.16)
7,29 (0.09)
5.3
0.25
gradicut
DrNAS 02
23.7
7.1
5.7
4.6
gradient
NAS-WOT 44
26.2
8.2
4.4
0.0036
training- frree
NAS-WOT DAG (ours)
25.9 (0:4)
8.2
4.4
0.003
training-fre -frce
TE-NAS
24.5
7.5
5.4
0.17
training- free
TE.NAS DAG (ours)
24.2 (0.3)
7.4
6.1
0.1
training free
Architectures searched ImageNet. Other methods searched CIFAR-10 and then transfered the ImageNet. Our repradazee result, the original work did not provide results on the ImageNet.
Recorded on single GTX 10800s GPU,
Table 2: Search Performance from
"optimal" indicates the best test accuracy achievable in the space. Our standard deviations over three random runs are included in parentheses.
Search Cost
Search
Architecture
CIFAR-10
CIEAR-100
ImageNNet16--100
(GPU
Method
ResNei 25
93.97
70.86
43.63
RSPS 37
87.60 57.66(1.69)
4..33(4.31)
31.14(3.88)
8007.13
random
ENAS 40
51.30j0.00
(5.61(0.00)
16.32(0.00)
13314.51
RL
DARTS (1s)
400
54.30/0.00
15.61(0.00)
16.32(0.00)
10889.87
gradient
DARTS (2nd)
40
54.30(0.00)
15.61(0.00)
16.32(0.00)
29901.67
gradient
GDAS
93.61(0.09;
70:70(0.30)
41.84(0.90)
28925.91
gradient
WOT [4
92.81 (0.99)
69.48 (1.70)
(3.16)
30,01
training-fre free
WOT DAG (ours)
92.98 (0.78)
69.86 (1.24)
43.44 (2.64)
17.95 (-40.2%)
training-froe
TE-NAS 10
93.9 (0.47)
71.24 (0.56)
42.38 (0.46)
1558
training-free
TE-NAS + DAG (ours)
(0.37)
71.26 (0.77)
44.38 (0.76)
1077 (-30.9%)
training-froe
FP FP-NAS [S
77.4
64.7 (5.3)
26.7 (10.4)
4837
gradient
FP-NAS DAG (ours)
93.3 (0.3)
70.8 (0.4)
44.5 (1.4)
2612 (-46.0%))
gradient
Optimal
94.37
73.51
47.31
Our version: We will skip potentially unpromising architecture before leaving them for TE-NAS to prune.
We provide a pseudocode algorithm in Appendix A to demonstrate the usage of our method.
How to choose d and m? Although d and m are hyperparameters, it is worth noting that they can be determined in highly principled way. In practice, given a search space, we only calculate the center
(d' m²) ( (dmaset -dmin mmax Memin) ) and the radius (ra.- fm) (dmax-dae
Mimax fimim
We by
default only keep architectures within half of the radius from the center for evaluation: |d d=1 < rra and Im - m² S 2 rm- This principle leads to (d*, m = (1.5, 10.5) with 1 (ra. rm) (0.7, 4.8) on DARTS, and (d", m²) = (1.6, 2.2) with 2 ( rma) = (0.7, on NAS- MAS--ennhh221.
Implementation settings. We train searched architectures for 250 epochs using SGD, with learning rate as 0.5, a cosine scheduler, momentum as 0.9, weight decay as 3 x 10 and a batch size 768. This setting follows previous works 44 69
41 66 26
12 [0].
DARTS space on ImageNet. As shown in Table I for both two training free NAS methods, by adopting our pre-filtrast pre-filtation strategy, can further reduce the search time cost and achieve better search results. For NAS-WOT, we can save 16.7% search time cost and reduce 0.3% top-1 error. For TE-NAS, we can significantly save 41.2% search time cost, and still improve the top-1 error by 0.4%. FL.PPs of our search architectures are 0.68G (TE-NAS + DAG) and 0.56G (WOT- + DAG).

---

NAS-Bench-201 Space. As shown in Table for both NAS-WOT and TE-NAS, we reduce over 30% search time cost with strong accuracy. We also in- clude a training-based method FP-NAS [5], where we even achieve 46% seach cost reduction with better performance. Moreover, we show that our method is robust to the choices of d and m. In the ablation study in 3 by changing different ranges of d and m, method remains strong over the WOT baseline.
Tahle 3: Our method is robust to choices of and m
(WOT 44 on NAS- (AAS-Bench-20),
Ranges accepted and
CIFAR-100
a d s ra ( = (buseline)
69 (1.70)
j 2-1 s fra. Im =mm fra
69.51 (1.70)
Id d*1 gra. mm1 s3rm mm
69.80 (1.24)
Id d=l S tra. (m -m=1 $ Am
69.97 (1.19)
Conclusion
In this work, show that it is possible conduct fine-grained convergence analysis on networks of complex connectivity patterns. By analyzing how an NNGP kernel propagates through the networks, we can fairly compare different networks' bounds of convergence rates. This theoretical analysis and comparison are empirically verified on MNIST and CIFAR-10. To make our convergence analysis more practical and general, we propose two intuitive principles on how to design network's s connectivity patterns: the effective depth and the effective width. Experiments on diverse architecture benchmarks and datasets demonstrate that networks with an extreme depth or width show bad performance, indicating that both the depth and width are important. Finally, we apply our principles to the large-scale neural architecture search application, and our method can largely accelerate the search cost of two training-fie free efficient NAS works with faster and better search performance. Our work bridge the gap between the Deep Learning theory and the application part, making the theoretical analysis more practical in architecture designs.
Acknowledgement
B. Hanin and Z. Wang are supported by NSF Scale-MoDL. (award numbers: 2133806, 2133861).
References
[1] Mohamed Abdelfattah, Abhinav Mehrotra, Lukasz Dudziak, and Donald Nicholas Lane. Zero-cost proxies for lightweight nas. In International Conference on Learning Representations, 2021.
[2] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. In International Conference Machine Learning, pages 242-252. PMLR, 2019.
[3] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[4] David Balduzzi, Marcus Frean, Lennox Leary, JP Lewis, Kurt Wan-Duo Ma. and Brian McWilliams. The shattered gradients problem: If resnets are the answer, then what the question? In International Conference on Machine Learning, pages 342-350. PMLR, 2017.
[5] Kartikeya Bhardwaj, Guihong Li, and Radu Marculescu. How does topology influence gradient propagation and model performance of deep networks with censenet-type skip connections? In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 13498-13507) 2021.
[6] Kaifeng Bu, Yaoba Zhang, and Qingxian Luo. Depth-width trade-offs for neural networks via topological entropy. arXiv preprint arXiv:2010.07587 2020.
[7] Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search on target task and hardware. arXiv preprint 1eI.vv1812.00 00332, 2018.
[8] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, 32:10836 10836-1-0884, 2019.
[9] Xiangyu Chang, Yingcong Li, Samet Oymak, and Christos Thrampoulidis. Provable benefits of overpa- rameterization in model compression: From double descent to pruning neural networks. arXiv preprint arXiv:2012.087. 08749, 2020.
10

---

[10] Wuyang Chen, Xinyu Gong, and Zhangyang Wang. Neural architecture search on imagenet in four gpu hours: A theoretically inspired perspective. In International Conference on Learning Representations, 2021.
[11] Wuyang Chen, Wei Huang, Xianzhi Du Xiaodan Song, Zhangyang Wang, and Denny Zhou. Auto scaling vision transformers without training. International Conference on Learning Representations, 2022.
[12] Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsich. Drna: Dirichlet neural architecture search. arXiv preprint arXiv:2006. 10355, 2020.
[13] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Conference on Computer Vision, pages 1294-1303 2019.
[14] Zixiang Chen, Yuan Cao, Difan Zou, and Quanquan Gu. How much over-paramstteriiztionn is sufficient to Iearn deep relu networks? arXiv preprint arXiv: 1911,1200,, 2019.
[15] Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. A downsampled variant of imagenet alternative to the cifar datasets, 2017.
[16] Xuanyi Dong and Yi Yang. Searching for a robust neural architecture in four gpu hours. Proceedings of the IEEE Conference on computer vision and pattern recognition, pages 1761-1770, 2019.
[17] Xuanyi Dong and Yi Yang. Nas-bench-102 102: Extending the scope of reproducible neural architecture search. arXiv preprint 2xXi:2001.003300 2020.
[18] Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pages 1675-1685. PMLR, 2019.
[19] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.000 1810.02054, 2018.
[20] Stanislav Fort and Stanislaw Jastrzebski. Large scale structure of neural network loss landscapes. Advances in Neural Information Processing Systems, 32:6709-6711,, 2019.
[21] Boris Hanin, Ryan Jeong, and David Rolnick. Deep relu networks preserve expected length. arXiv preprint arXiv:2 10492, 2021.
[22] Boris Hanin and Mihai Nica, Finite depth and width corrections to the neural tangent kerel.. arXiv preprint wwXiv:190900599, 2019.
[23] Soufiane Hayou, Arnaud Doucet, and Judith Rousseau. On the impact of the activation function on deep 2019.
neural networks training. arXiv preprint
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing huvan-level performance imagenet classification. In Proceedings the IEEE international conference on computer vision, pages 1026 1034, 2015.
[25] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pottern recognition, pages 770-778, 2016.
[26] Pengfei Hou, Ying Jin, and Yukang Chen. Single-darts: Towards stable architecture search. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 373-382, 2021.
[27] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh 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, pages 1314-1324, 2019.
[28] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger. Densely connected convolutional networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700-4708, 2017.
[29] Kaixuan Huang, Yuqing Wang. Molei Tao, and Tuo Zhao. Why do deep residual networks generalize better than deep feedforward networks?-a neural tangent kernel perspective. arXiv preprint arXiv:2002.06200 2020.
[30] Wei Huang, Weitao Du and Richard Yi Da Xu. On the neural tangent kernel of deep networks with orthogonal initialization. arXiv preprint arXiv:2004.05867, 2020.

---

[31] Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in nearal information processing systems, pages 8571-8580, 2018.
[32] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, pages 1097-1105, 2012.
[33] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(1 1):2278-2324, 1998.
[34] Jaehoon Lee. Yasaman Bahri, Roman Novak, Samuel S Schoenholz. Jeffrey Pennington, and Jascha Sohl-Dickstein Deep neural networks gaussian processes. arXiv preprint arXiv:171 2017.
[35] Guohao Li, Guocheng Qian, Itzel C Delgadillo, Matthias Muller, Ali Thabet, and Bemard Ghanem. Sgas: Sequential greedy architecture search. Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition, pages 1620-1630, 2020.
[36] Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. arXiv preprint arXiv:1712.09913, 2017.
[37] Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty Artificial Intelligence, pages 367-377. PMLR, 2020.
[38] Yuanzhi Li and Yingyu Liang. Learning overparameterizee neural networks via stochastic gradient descent on structured data. arXiv preprint 1 2018.
[39] Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceedings of the European Conference on Computer Vision (ECCV), pages 19-34, 2018.
[40] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: 100.. 09055, 2018.
[41] Vasco Lopes, Miguel Santos, Bruno Degardin, and Lufs A Alexandre. Guided evolution for neural architecture search. arXiv preprint arXiv:2110. 153.22 2021.
[42] Yiping Lu. Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean field analysis of deep resnet and beyond: Towards provably optimization via overparameterizztion from depth. In International Conference on Machine Learning, pages 6426-6436. PMLR, 2020.
[43] Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Mean-field theory two-layers neural networks: dimension-free bounds and kernel limit. In Conference on Learning Theory, pages 2388-2464. PMLR, 2019.
[44] Joe Mellor, Jack Turner, Amos Storkey, and Flliot J Crowley. Neural architecture search without training. In International Conference on Machine Learning, pages 7588-7598. PMLR, 2021.
[45] Daniel Park, Jachoon Lee, Daiyi Peng, Yuan Cao, and Jascha Sohl Sohl-Dickstein. Towards nngp-guided neural architecture search. arXiv preprint arXiv:2011.06000 2020.
[46] Hieu Pham, Melody Y Guan, Barret Zoph. Quoe V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint 10..::1802.032200 2018.
[47] Ben Poole, Subhaneil Lahiri, Maithra Raghu, Jascha Sohl-Dickstein and Surya Ganguli. Exponential expressivity in deep neural networks through transient chaos. In Advances in neural information processing systems, pages 3360-3368. 2016.
[48] Ilija Radosavovic, Justin Johnson, Saining Xie, Wan-Yen Lo, and Piotr Dollár. On network design spaces for visual recognition. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1882-1890, 2019.
[49] Estehan Real, Alok Aggarwal, Yanping Huang, and Quoe V Le. Regularized evolution for image classifier architccture search. Proceedings of the aaai conference on artificial intelligence, volume 33, pages 4780-4789, 2019.
[50] Bastian Rieck, Matteo Togninalli, Christian Bock, Michael Moor, Max Horn, Thomas Gumbsch, and Karsten Borgwardt. Neural persistence: A complexity measure for deep neural networks using algebraic topology. arXiv preprint 1rxiv:1812.09764, 2018
12

---

[51] Alexander Shevchenko and Marco Mondelli. Landscape connectivity and dropout stability of sgd solutions for over--arannn vet-parameterized neural networks. In International Conference on Machine Learning, pages 8773- 8784. PMLR, 2020.
[52] Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference on Learning Representations, 2019.
[53] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogni- tion. arXiv preprint arXiv: 1409::440.11550 1556, 2014.
[54] Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee. Theoretical insights into the optimization landscape of over- vee-parameterized shallow neural networks. IEEE Transactions on Information Theory, 65(2):742-769, 2018.
[55] Mci Song, Andrea Montanari, and P Nguyen. A mean field view of the landscape of two-layers neural networks. Proceedings of the National Academy of Sciences, 115:E7665- E7671,, 2018.
[56] Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc Le. Mnasnet: Platform-awe aware neural architecture search for mobile. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2820-2822 2019.
[57] Mingxing Tan and Quoe V Le. Efficientnet: Rethinking model scaling for convolutional neural networks. arXiv preprint arXiv: /194, 2019.
[58] Mingxing Tan and Quoc V Le. Efficientnetv2: Smaller models and faster training. arXiv preprint arXiv:2104.0023 2021.
[59] Hidenori Tanaka, Daniel Kunin, Daniel LK Yamins, and Surya Ganguli. Pruning neural networks without any data by iteratively conserving synaptic flow. arXiv preprint WXXv:2006.05467, 2020.
[60] Luca Venturi, Afonso S Bandeira, and Joan Bruna. Spurious valleys two-layer neural network optimiza- tion landscapes. arXiv preprint arXiv:1802. 06384, 2018.
[61] Lechao Xiao, Jeffrey Pennington, and Samuel S Schoenholz. Disentangling trainability and generalization in deep learning. arXiv preprint arXiv:1912.13053, 2019.
[62] 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, pages 1284-1293, 2019.
[63] Sirui Xie, Hehui Zheng. Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint
2018.
[64] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong, Pc-darts: Partial channel connections for memory-efficient architecture search. In International Conference on Learning Representations. 2019.
[65] Zhicheng Yan, Xiaoliang Dai, Peizhao Zhang, Yuandong Tian, Bichen Wu, and Matt Feiszli. Fp-nas: Fast probabilistic neural architecture search. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15139-15148, 2021.
[66] Peng Ye, Baopu Li, Yikang Li, Tao Chen, Jiayuan Fan, and Wanli Ouyang. B-darts: Beta-decay regulariza- tion for differentiable architecture search, arXiv preprint arXiv:2203.01666 2022.
[67] Jiaxuan You, Jure Leskovee, Kaiming He, and Saining Xie. Graph structure of neural networks. arXiv preprint arXin:2007.065555 2020.
[68] Xiao Zhang, Yaodong Yu, Lingxiao Wang, and Quanquan Gu. Learning one- hiddehddddna layer relu networks via gradient descent. In The 22nd international conference artificial intelligence and statistics, pages 1524-1534. PMIR, 2019.
[69] Xuanyang Zhang, Pengfei Hou. Xiangyu Zhang, and Jian Sun. Neural architecture search with random labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10907-1091 10916, 2021.
[70] Hongpeng Zhou, Minghao Yang, Jun Wang, and Wei Pan. Bayesnas: A bayesian approach for neural architecture search. arXiv preprint 10Xhv:1905.04919, 2019.
[71] Pan Zhou, Caiming Xiong, Richard Socher, and Steven CH Hoi. Theory-inspired path-regularized differential network architecture search. arXiv preprint arXiv:2006.100 16537, 2020.
13

---

[72] Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. arXiv preprint urXiv:161.00157. 2016.
[73] Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8697-8710, 2018.
[74] Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-parameterized deep relu networks. Machine Learning, 109(3)467-492, 2020.
[75] Difan Zou, Philip M Long, and Quanquan Gu. On the global convergence of training deep linear resnets. arXiv preprint arXiv:2003.0109, 2020. 2020.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You are strongly encouraged to include a justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] In Remark 5.1
claim
"Extreme or m leads to bad performance" requires architectures from a complete space of DAGs, without introducing any prior the DAG topology.
(c) Did you discuss any potential negative societal impacts your work? [No] Our work does not have negative societal impacts
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] We include our proofs in supplement.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes) We include our
code and Readme of instructions in supplement. Data is publicly available online.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 5.3
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] We run experiments for three random seeds.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Table
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
14

---

(b) Did you mention the license of the assets? [Yes] Licenses are publicly available
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "gVGp7pN9uj", "reviewer": "Reviewer_6D9f", "summary": "This paper studied how a wide network’s NNGP kernel can depict the optimization dynamics of a particular DNN topology, by propagating the NNGP kernel spectrum and showing the topology to affect the bound of convergence rate. Based on this observation, the authors created two notions of “efficient depth” and “effective width”, that can be plugged-in existing NAS methods to filter out “unpromising” connectivity patterns for speedup. ", "questions": "See above", "limitations": "No particular negative impact. Limitation was discussed by authors.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\nThis is an important new piece of work towards connecting deep learning theory and NAS. Prior arts already adapted theoretical properties of general DNNs, but never established their correlations with the concrete NN architecture topology, except some empirical correlation observations. This paper is the first to theoretically justify the optimization implication of general DNN topology, which is likely to become a milestone for future work in this frontier.\nThroughout the paper, the theory and application aspects are tightly coupled, and the story is coherent. Their claim is theoretically sound (a non-surprising, yet nice adaptation of NNGP proofs). In the experiments, multiple benchmarks are reported, with error bars. \n\nSection 5.3 is very helpful in understanding how the effective width/depth principles are used to improve NAS in a plug-in fashion. I especially like how the authors can choose d and m in a principled justified way, not ad-hoc.\n\nOverall the writing is very good, clear and easy to follow. It’s a mature paper.\n\nWeakness: \nNNGP is a rough characterization of optimization dynamics, hence its preciseness in comparing architectures is limited. More importantly, as mentioned on lines 280, “Although our d and m are only inspired from the optimization perspective, not the complexity or generalization, our method mainly filters out bad architectures at a coarse level, but does not promote elites in a fine-grained way.” I was not sure whether this optimization-only selection bias will lead us to missing architectures that are excellent in complexity/generalization (hence offsetting their perhaps mediocre optimization behavior). \nThe authors applied their principles to accelerating TE-NAS and NAS-WOT. Those are two earliest training-free NAS approaches. Could the authors also try more recent ones and see improvements, e.g., Zen-NAS or zero-cost proxy NAS? Moreover, how about non-training-free NAS methods, can they be accelerated by such pre-filtering too?\n\nIn Tables 1 and 2, the FLOPS of searched architectures could be included too.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WCawzWJWC9p", "reviewer": "Reviewer_D7qw", "summary": "The authors proposed a formal analysis framework to estimate the the upper bound of training loss convergence for DAGs with variety of network topologies. Based on that, they proposed a plug-and-play method to speech up previously reported NAS methods by apply a filtration. The results demonstrate the proposed method to search better networks and faster. ", "questions": "See above.", "limitations": "Current discussion is sufficient. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ To my best knowledge, this is perhaps the first theoretical study directly focusing on the fine-grained NN topological connectivity rather than a general NN function, despite some prior works exploring part of that, e.g., [50] for NN width/depth, [69] for skip connection. It is an important yet understudied direction, and this work appears to lay a good foundation. \n\n+ I have gone over the details of the derivation for the convergence analysis of DNN regarding the connectivity patterns, and it seems sound. For the bound estimation, the authors chose a simplified theoretical model of DAGs + MSE loss, using NNGP kernel. The key step is to estimate the flow of NNGP variance and mean through unidirectional information paths in the specific topology. The theoretical results are examined by a series of simulations in Sec 5.1 and Sec 5.2.\n\n+ The notions of ‘effective depth’ and ‘effective width’ are clearly defined, and the authors also gave clear guidelines how to use them in NAS. It is shown to accelerate two latest NAS methods and outperform more, across multiple benchmarks. The experiments validate the effectiveness of the proposed method. \n\nIn general, I think this is a cool and well-polished paper. One question is the authors demonstrated their down-selection technique to two training-free NAS approaches (NAS-WOT and TE-NAS), which are already very fast and therefore show only non-significant reduction of search time. I wonder why not trying the proposed approach on more costly and accurate search methods, and see if the accuracy-search efficiency gain is still favorable.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7Dzu6DbY6iR", "reviewer": "Reviewer_rAbP", "summary": "The paper theoretically and empirically analyzes the link between connectivity patterns of deep networks and their convergence. Based on this analysis, the authors propose a couple of training-free metrics (effective width and effective depth) and use them to do training-free NAS. The paper presents a thorough link between gradient descent convergence and structural properties of deep networks by proving a link between number of unique paths, number of incoming paths at certain nodes in the network and the least eigenvalue of a Neural Network Gaussian Process (NNGP) variance. Essentially, the authors look at how the NNGP variance changes as the data propagates through the model and relate it to how many unique paths it goes through and how many incoming edges land at the last layer (in the DAG topology used to formulate this problem). These principles are then baked into their “effective depth” and “effective width” metrics that do not require any training or forward/backward passes to compute. Some empirical results are shown for this convergence. The remaining paper looks at training-free NAS by cutting down the search space. Results are shown on CIFAR-10/100, ImageNet-16-120, and ImageNet.", "questions": "Please see the weaknesses section above (particularly points 2 and 3).", "limitations": "Authors could comment on role of kernel sizes, etc., and how the connectivity alone does not take this into account in the present study.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has following strengths:\n\n1. This is a principled approach to study an important problem, i.e., understanding how deep network architecture topologies and connectivity patterns relate to training convergence. Knowing this is obviously very valuable because (a) we can design better models directly without a long, time-consuming search, (b) in future, better understanding of how architectures impact accuracy can enable us to create even more novel models. Indeed, it is a hard problem, so coming up with an intuitive method for this problem is very hard.\n\n2. The proof seems very intuitive and the resulting metrics (effective depth and effective width) are very simple to compute and do not require any training or even forward/backward passes. One can just look at the architecture connectivity and tell with reasonable confidence if it is a good or bad architecture.\n\n3. Empirical results for training convergence and NAS-bench architectures, etc., present some interesting insights (although, they also bring up some questions, see below).\n\n4. Authors have shown experiments all the way to ImageNet which is nice.\n\nDespite the strengths, there are some weaknesses and questions. Addressing these would likely make the paper much stronger:\n\n1. The empirical validation of the theory (section 5.1) is done using only three architecture topologies. This is not that expensive (particularly for MNIST and CIFAR-10). Can the authors look at many different deep nets with different connectivity patterns and somehow present more data on convergence?\n\n2. Experiments section could in general be stronger. For instance, the ImageNet result on TE-NAS is not good enough. We see some accuracy improvement, but we also see model size increase compared to vanilla TE-NAS. Moreover, since the training-free NAS itself is very cheap, further improvements in search time do not make a significant difference. In Figure 5, each point represents a subset of models that achieved a similar accuracy. Were there any interesting patterns in terms of their number of parameters/MACs? Example: did the white/black circles contain models of a certain size in terms of parameter counts? Were the models deeper but narrower within a circle? Or shallower but wider?\n\n3. The very first paper that pioneered the creation of such connectivity-based metrics was reference [R1] cited by the authors. This paper needs to be discussed in much more detail in Section 2.2/2.3 as there are many interesting synergies. For instance, [R1] showed the link between connectivity patterns and training convergence too. [R1] showed very concrete training convergence curves and showed that their proposed metric correlated very well with convergence. The metric proposed by [R1] is also training-free. Indeed, the present study is much more fine-grained, more theoretical, and is more generally applicable than [R1]. \n\n4. Other weaknesses involve things like there is no characterization of differences in kernel sizes, etc., but this is not critical and can be a good future work.\n\n5. Proof for equation (14) in appendix B has a typo? K_{ii}^{l} should have a square on \\sigma (right below “Proof of Lemma 3.2”)? Honestly, this paper could be much stronger if there was a bit more focus on empirical results for justifying the theory (e.g., if section 5.1 was much stronger).\n\n[R1] Bhardwaj, Kartikeya, Guihong Li, and Radu Marculescu. \"How does topology influence gradient propagation and model performance of deep networks with DenseNet-type skip connections?.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2021.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept