Title: TOWARDS UNIFYING NEURAL ARCHITECTURE SPACE EXPLORATION AND GENERALIZATION

Abstract: In this paper, we address a fundamental research question of significant practical interest: Can certain theoretical characteristics of CNN architectures indicate a priori (i.e., without training) which models with highly different number of parameters and layers achieve a similar generalization performance? To answer this question, we model CNNs from a network science perspective and introduce a new, theoretically-grounded, architecture-level metric called NN-Mass. We also integrate, for the first time, the PAC-Bayes theory of generalization with smallworld networks to discover new synergies among our proposed NN-Mass metric, architecture characteristics, and model generalization. With experiments on real datasets such as CIFAR-10/100, we provide extensive empirical evidence for our theoretical findings. Finally, we exploit these new insights for model compression and achieve up to 3× fewer parameters and FLOPS, while losing minimal accuracy (e.g., 96.82% vs. 97%) over large CNNs on the CIFAR-10 dataset.

1. INTRODUCTION:

Are there any theoretical characteristics of CNN architectures that can indicate a priori (i.e., without training) which models achieve a similar test accuracy, despite having a vastly different number of parameters and layers? Even though there has been significant progress in architecture design practices (both manual [He et al. (2016) ; Huang et al. (2017) ; Howard et al. (2017) ] as well as automated via Neural Architecture Search (NAS) [Zoph et al. (2018) ; Liu et al. (2018) ; Real et al. (2017) ]), the above question remains unanswered, thereby making it one of the most fundamental problems in modern deep learning research. Clearly, answering this question can help us directly design efficient CNN architectures with predictable performance figures. More precisely, the above question is related to three important areas of research:

Neural Architecture Search (NAS) techniques automatically search for highly accurate and efficient models [Zoph et al. (2018) ; Liu et al. (2018) ; Real et al. (2017) ]. The models designed by NAS algorithms usually surpass the manually designed architectures [Howard et al. (2017) ].

Model Compression methods reduce the computational costs of existing deep networks without losing significant test accuracy. The existing model compression techniques mainly focus on pruning, quantization, and knowledge distillation [Li et al. (2016) ; Yang et al. (2016) ; Hubara et al. (2017) ; Lai et al. (2017) ; Hinton et al. (2015) ].

Generalization of deep networks aims to theoretically understand why deep networks work well in practice by exploring properties of weight-norms/initializations, stability of deep networks to noise, optimization characteristics such as sharpness of the minima, etc. [Zhang et al. (2016) ; Arora et al. (2018) ; Neyshabur et al. (2015; 2017b; a) ]. Deep networks achieve low generalization error despite having a large number of parameters. In contrast, traditional wisdom suggests that models should overfit when the number of parameters is much larger than the dataset size (which is true in practice).

Although there has been extensive research in the above three areas separately, to the best of our knowledge, there is no research at the intersection of all three directions. Specifically, while NAS can generate efficient architectures for mobile applications [Tan et al. (2019) ; Cai et al. (2018) ; Wu et al. (2019) ], existing NAS research does not theoretically explain why the newly discovered architectures perform better than other models containing a similar number of parameters. Conversely, NAS also does not theoretically explain why can architectures with significantly different number of parameters and layers sometimes achieve similar accuracy. Moreover, a few generalization studies (e.g., Arora et al. (2018) ) use compression to prove generalization error bounds. However, the generalization studies do not provide any theory that can explicitly guide efficient architecture design. In view of the above, in this paper, we explicitly unify the architecture space exploration and generalization. Towards this, we first model CNNs as complex networks [Newman et al. (2011) ] since CNNs essentially consist of channels connected via filters at each convolutional layer (see Fig. 1(a) ).

Then, we define a new NN-Density metric to quantify how densely the channels of a CNN are connected to each other. We next use NN-Density to define a new, theoretically-grounded, architecturelevel metric called NN-Mass which establishes a link between the structure of CNN architectures and their generalization error. Our objective is to use these architectural metrics for Neural Architecture Space Exploration (NASE); throughout this paper, NASE refers to the process of studying the design space of deep networks via theoretically-grounded metrics such as NN-Mass.

To this end, we combine for the very first time, the Probably Approximately Correct (PAC)-Bayes theory of generalization [McAllester (1999a; b) ] with network science [Newman & Watts (1999) ; Monasson (1999) ; Watts & Strogatz (1998a) ] to theoretically prove that: (i) Architectures with higher NN-Mass achieve lower generalization error, and (ii) Models with similar NN-Mass lead to similar test accuracy, despite having different numbers of parameters and layers (see Fig. 1(b) ).

Then, we provide extensive empirical evidence to support our theory. Finally, given a large, highly accurate CNN, we show how NN-Mass can be used to directly design efficient models without compromising their accuracy. Of note, our proposed NN-Mass metric has a closed-form equation in terms of structure of the CNN architecture. Hence, it can be used to directly discover new, efficient models without training individual models (see Fig. 1(c )). Our approach is illustrated in Fig. 1 .

Overall, we make the following key contributions to both theory and practice:

1. To the best of our knowledge, we are the first to exploit network science to theoretically study the generalization properties of CNN architectures. Towards this, we propose a new, architecture-level metric called NN-Mass which can indicate the generalization capabilities of CNNs with long-range links; we call concatenation-type skip connections (see Densenet [Huang et al. (2017) ]) as long-range links or shortcut connections in this paper. 2. We are also the first to integrate the PAC-Bayes theory with network science to offer a new, principled method for studying properties of large deep networks. We discover a theoretical link between NN-Mass, a property of the CNN architectures, and generalization. We also show that models with similar NN-Mass achieve similar generalization errors. 3. To validate our new findings, we conduct extensive experiments with CNNs of different depths, parameters, and long-range links for CIFAR-10/100 datasets. We quantify the relationship between NN-Mass and generalization by demonstrating that the goodness-of-fit parameter (R 2 ) for a linear fit achieves high values (e.g., between 0.74-0.90). We also show that NN-Mass can be used to predict the test accuracy of unknown architectures. 4. Finally, we demonstrate practical implications of our work by exploiting NN-Mass for model compression. Specifically, given a large, highly accurate CNN (e.g., ∼ 97% on CIFAR-10), we directly use our proposed NN-Mass metric to design new architectures that achieve accuracy close to that of the large model (e.g., 96.82% on CIFAR-10 test set), while reducing the total parameters and FLOPS by more than 3×.

The rest of the paper is organized as follows: Section 2 covers related work on NAS and generalization, while Section 3 describes our proposed approach and the theoretical relationship between CNN architectures and their generalization. Next, Section 4 presents extensive experiments to support our theoretical results. Section 5 concludes the paper with final remarks on future work.

2. RELATED WORK:

We now discuss related work on NAS, model compression and generalization. Prior art on longrange links for CNNs and network science is discussed in Appendix A.

Network Science-based NAS and Model Compression. Recently, standard network-generation techniques such as Barabasi-Albert (BA) [Barabási & Albert (1999) ] or Watts-Strogatz (WS) [Watts & Strogatz (1998a) In contrast, our objective is twofold: (i) Theoretically understand architectural aspects of generalization, and (ii) Practically design new, efficient architectures without searching for them (e.g., by directly exploiting our proposed metrics). Moreover, by integrating the PAC-Bayes theory with small-world networks, we present an effective way of modeling generalization of CNN architectures containing long-range links. We next describe our proposed approach that unifies these areas.

3. PROPOSED APPROACH:

We first explain how CNNs can be modeled via network science. Next, we mathematically derive the proposed NN-Density and NN-Mass metrics that are needed for NASE. We then demonstrate the theoretical relationship between NN-Mass and generalization.

3.1. MODELING CNNS VIA NETWORK SCIENCE:

We assume a generic CNN consisting of multiple cells, each containing a fixed number of convolutional layers, similar to existing works such as Densenets [Huang et al. (2017) ], Resnets [He et al. (2016) ], etc. As shown in Fig. 2 (a), each cell can have a different width, i.e., number of channels per layer. Following the standard practice [Simonyan & Zisserman (2014) ], the width is increased by a factor of two at each cell as the feature map is reduced by half (see Fig. 2(a) ).

We now illustrate a single convolution layer in Fig. 2 (b) for our setup. In a standard CNN, a convolutional layer with n input channels and m output channels consists of m filters, each with

[k × k × n] dimensions.

That is, the red kernel in Fig. 2 (b) convolves with red input channel, green kernel convolves with green input channel, and so on. The outputs of all such channel-wise convolutions are added together to obtain a single output channel (violet output channel in Fig. 2(b) ). In our setup, we explicitly assign different contributions from each input channel i to each output channel j as probabilities α ij , which are fixed to random values1 . These α ij probabilities are directly used to define an adjacency matrix of any cell c:

A c ij = α ij , where i, j ∈ {0, 1, 2, . . . , w c • d c -1}.

Next, we define the structure of our cells. Fig. 2 (c) shows a cell with d c convolution layers, and w c channels per layer. Output channels at each layer i receive contributions from all output channels of layer i -1; we call these contributions short-range links since they connect consecutive layers (see red links in Fig. 2(c ))2 . In addition to short-range links, the output channels at layer i can also receive long-range contributions from maximum t c channels present at layers l ∈ {0, 1, . . . , i-2} within the given cell (see purple links in Fig. 2(c )). That is, t c determines maximum number of channels that can supply long-range links. By definition, a link is long-range if it connects channels across two or more layers. Hence, each layer receives long-range contributions from min{w c (i-1), t c } channels3 . In practice, to create long-range links, the feature maps from previous layers are concatenated at the current convolution layer (like in Densenets [Huang et al. (2017) ]). Of note, in our current setup, long-range links are confined only within the cell and do not extend across multiple cells.

To create long-range links at each layer i, we randomly select min{w c (i -1), t c } previous channels (out of all channels until layer i -2). Similar to recent NAS research [Li & Talwalkar (2019) ], our rationale behind selecting random links (and random probabilities α ij 's) is that random architectures are often as competitive as the carefully designed/searched models. Hence, throughout the paper, we look only at architectures with randomly chosen long-range links (after fixing the random seed).

3.2. PROPOSED METRICS FOR NEURAL ARCHITECTURE SPACE EXPLORATION:

The above network formulation can be used to systematically study the architecture space for deep networks. Specifically, our problem has following objectives: (i) Theoretically quantify the architectural aspects of the generalization problem, and (ii) Exploit the above theory to directly design efficient CNN architectures in practice. To address the above goals, we propose two new network science-based metrics called NN-Mass and NN-Density, as defined below.

Definition 1 (Cell-Density). Given a CNN, density of a cell quantifies how densely its channels are connected via long-range links. Formally, for a given cell c, cell-density ρ c is expressed as:

ρ c = #long-range links within cell c Total possible #long-range links within cell c = 2 dc-1 i=2 min{w c (i -1), t c } w c (d c -1)(d c -2) (1)

For complete derivation, please refer to Appendix C. Next, we define NN-Density as the average density across all cells in a CNN. If a CNN has N c cells, then the NN-Density ρ avg is expressed as:

ρ avg = 1 N c Nc c=1 ρ c = 1 N c Nc c=1 2 dc-1 i=2 min{w c (i -1), t c } w c (d c -1)(d c -2) (2)

Definition 2 (Mass of Deep Networks). We define NN-Mass to quantify the generalization capability of a CNN. Intuitively, for a given width (w c ), models with similar NN-Mass but different depth (d c ), long-range links (t c ), and number of parameters should achieve a similar test accuracy.

Note that, density is basically mass divided by volume. Let volume be the total number of channels in a cell. Then, we can analogously derive the NN-Mass metric by multiplying the cell-density with total number of channels in each cell. Hence, the NN-Mass (m) is given as:

m = Nc c=1 w c d c ρ c = Nc c=1 w c d c 2 dc-1 i=2 min{w c (i -1), t c } w c (d c -1)(d c -2) = Nc c=1 2d c dc-1 i=2 min{w c (i -1), t c } (d c -1)(d c -2)

(3) Below, we explain the use of above metrics for Neural Architecture Space Exploration.

Neural Architecture Space Exploration (NASE). We define NASE as the process of studying the design space of CNNs via theoretically-grounded metrics such as NN-Mass. Note that, both NN-Density and NN-Mass relate network width, depth, and number of longrange links. For a fixed number of cells, a CNN architecture can be completely specified by {depth per cell, width per cell, maximum long-range link candidates per cell} = {d c , w c , t c }. Hence, to perform NASE, we vary {d c , w c , t c } to obtain random architectures with varying NN-Density and NN-Mass values. Appendix D illustrates NN-Mass calculation for a given architecture using a concrete example. We next show the theoretical link between NN-Mass and generalization.

3.3. PROVABLE RELATIONSHIP BETWEEN NN-MASS AND GENERALIZATION:

In this section, we theoretically prove the relationship between generalization and our proposed NN-Mass metric, a property of CNN architectures. We further show that models with similar NN-Mass values achieve similar test accuracy. To this end, we start with the PAC-Bayes theory which is used to bound the generalization error of a given (not necessarily a neural network-based) classifier. We also integrate the network theory with PAC-Bayes theory to derive our results. Theorem 1 (McAllester Bound for Generalization Error (McAllester (1999a; b) ; Laviolette)). Given any data generating distribution D, any hypothesis class of predictors H, any prior distribution P over the predictors, and any δ ∈ (0, 1], with probability at least 1 -δ and for all distributions Q over H for a randomly drawn training set S of N examples, the generalization bound is given by:

E D (L(f Q )) ≤ E S ( L(f Q )) + KL(Q||P ) + log 2 √ N δ 2N , where, f Q is a classifier drawn from Q, E D (L(f Q )) denotes the expected error, E S ( L(f Q ))

is the empirical error over the training set S, and KL(Q||P ) denotes the Kullback-Leibler (KL) divergence between the distributions P and Q.

The above PAC-Bayes theorem bounds the generalization error of any classifier. Next, we prove generalization bounds for CNN architectures with long-range links in terms of NN-Mass. Without loss of generality, we assume in this section that the CNN architecture consists of a single cell containing d c convolutional layers, each containing w c channels per layer (i.e., the width is w c ).

Theorem 2 (Generalization Bound for CNN Architectures in terms of NN-Mass). Consider singlecell CNN models with d c layers and w c channels per layer. Also, let t c be the number of channels contributing long-range links. If Q denotes a probability distribution over CNNs with long-range links and an architecture f Q ∼ Q has a NN-Mass of m, then, with probability at least 1 -δ the generalization error for this architecture is bounded as follows:

E D (L(f Q )) ≤ E S ( L(f Q )) + 1 2σ ( 1 6m -1 2 log(πem)) + log 2 √ N δ 2N ,

where, σ is the maximum number of connections a channel can have in a given CNN architecture.

To prove the above theorem, we integrate, for the very first time, the PAC-Bayes theory of generalization [McAllester (1999a; b) ] with the small-world theory from network science [Newman & Watts (1999) ; Monasson (1999) ]. Essentially, we express the KL-divergence term in Theorem 1 as a function of NN-Mass. For complete proof, please refer to Appendix E.

Remark 1. The KL-divergence term (equation 14 in Appendix E) is a decreasing function of m.

Hence, for a family of models with depth d c and width w c , Theorem 2 guarantees that the test error should reduce as NN-Mass increases. We show extensive empirical results for this observation.

As a natural consequence of Theorem 2, we next show that for two CNNs with a given width but different depths, models with similar NN-Mass values are expected to achieve similar generalization performance, even if the two models have vastly different number of parameters and layers! Corollary 1 (Models with Similar Mass Achieve Similar Generalization Performance). Given two models of same width w c , let f L Q be a deeper model with NN-Mass m L , and let f S Q be a shallower model with NN-Mass m S such that m L ≤ m S . Then, the difference in expected test error of the two models is bounded with probability at least 1 -δ as follows:

E D (L(f L Q )) -E D (L(f S Q )) ≤ E S ( L(f L Q )) -E S ( L(f S Q )) + 1 2σ m S -m L 6m L m S -1 2 log m L m S + log 4N δ 2

2N:

In other words, irrespective of number of parameters and layers, as the NN-Mass for the two models becomes similar, their test error is also expected to become similar.

The corollary follows directly from the KL-divergence term in Theorem 2 (see equation 14 in Appendix). See Appendix F for the complete proof of the closed-form bound above.

Remark 2. For the same width, a shallower and a deeper model with same NN-Mass intuitively implies that the shallower model is more densely connected than the deeper model (see equation 3). Hence, this might suggest that NN-Density can also help us identify models that achieve similar test accuracy. However, as we shall show empirically, NN-Density alone cannot be used to identify such models since the CNNs with different depths achieve similar test accuracy for different NN-Density values. In contrast, NN-Mass can identify CNNs that yield similar generalization performance a priori (i.e., without training) since it has a closed-form equation 3 in terms of {d c , w c , t c }.

Intuition behind why NN-Mass indicates generalization performance of CNN architectures.:

While proving Theorem 2, we show that a CNN with long-range links can be seen as a superposition of a lattice network and a random network (see Fig. 9 in Appendix E). Also, for d c >> 2 (true for deep CNNs), the average degree (i.e., the average number of connections for nodes) of the random network kR|G = m/2 (see equation 9 in Appendix E), and that of the lattice network is just w c . Hence, the average degree of the overall CNN is w c + m/2, which is independent of the depth d c . Since average degree indicates how well-connected the network is, it controls how effectively the information can flow through a given topology. Therefore, for a given width and NN-Mass, the average amount of information that can flow through various architectures (with different #parameters/layers) should be similar (due to the same average degree). As a result, we hypothesize that these topological properties might constrain the amount of information being learned by CNNs.

Next, we present detailed experimental evidence to support our theoretical findings.

4. EXPERIMENTAL SETUP AND RESULTS:



4.1. EXPERIMENTAL SETUP:

Our objective is to perform NASE by varying {d c , w c , t c } that generates random architectures with different NN-Mass and NN-Density values. Similar to prior art like Huang et al. (2017) , we keep the total number of cells = 3 for all experiments. Overall, we conduct the following types of experiments for NASE on CIFAR-10 and CIFAR-100 datasets: (i) We show the impact of varying NN-Density (Remark 2). (ii) By providing extensive empirical evidence towards Theorem 2 and Corollary 1, we next show that NN-Mass can identify models that achieve similar test accuracy. (iii) We further show that our findings hold across models with different widths. (iv) We then demonstrate that NN-Mass is better for predicting generalization performance than parameter counting, a baseline used to indicate model generalization. (v) We predict test accuracy of completely unknown architectures. (vi) We also show that our findings hold for CIFAR-100 which is significantly more complex than CIFAR-10. All experiments are repeated three times with different random seeds.

Finally, to demonstrate the practical implications of our work, we exploit NN-Mass to directly design efficient CNNs which achieve accuracy comparable to larger networks with similar NN-Mass. More details for the experimental setup (e.g., architecture details, learning rates, data augmentation, etc.) can be found in Appendix G (see Table 2 ). Next, we describe the results for the above experiments. 

4.2. RESULTS:

Unless stated otherwise, the results are for CIFAR-10 (CIFAR-100 is presented towards the end).

4.2.1. NASE: NN-MASS AS AN INDICATOR OF GENERALIZATION OF CNN ARCHITECTURES:

Impact of Varying NN-Density. We train different deep networks with varying NN-Density (see To explain this, we show test accuracy vs. NN-Mass in Fig. 3(c ). Two observations are worth noting:

1. The higher the NN-Mass, the higher the test accuracy. This observation reinforces Remark 1 and Theorem 2 that higher NN-Mass should result in lower generalization error.

2. Irrespective of number of parameters/layers, models with similar NN-Mass achieve similar accuracy (Corollary 1). All models within box W (models A-E in Fig. 3(b )) cluster into bucket Z (models A'-E' in Fig. 3(c) ). Same holds for models within X and Y.

These observations emphasize that the NN-Mass is an important indicator of generalization performance, and is able to identify a family of models that obtains similar test accuracy.

The above results are for width multiplier, wm = 2, and vary NN-Mass indirectly due to changing NN-Densities. Since it is clear that NN-Mass is highly correlated with generalization, we now directly vary NN-Mass for models with wm ∈ {1, 3} to ensure that the above observations hold true for CNNs with different widths. More specifically, in Fig. 4 (a), we observe that for wm = 1, models in boxes U and V have significantly different number of parameters and, yet, they achieve a similar test accuracy. Again, when plotted against NN-Mass (see Fig. 4 (b)), models within the boxes U and V in Fig. 4 (a) concentrate into buckets W and Z, respectively (see also other buckets). As width increases, capacity of small (shallower) models increases and, therefore, the accuracy-gap between models of different depths reduces. Hence, the R 2 for linear fit increases as width increases.

Note that, for wm = 1, the 31-layer models do not fall within the buckets (see blue line in Fig. 4(b) ). We hypothesize that this could be because of the following tradeoff. Specifically, since Corollary 1 states that the difference in test errors is bounded by the sum of (i) difference in training errors, and (ii) difference between NN-Mass values, the former term might dominate for low-capacity models (and, thus, the difference in test errors would increase). For instance, the training accuracy of 31layer models is found to be much lower (e.g., 0.66%-0.9%) than that of 64-layer models. In contrast, 40-layer models have only 0.27%-0.4% lower training error than the 64-layer CNNs. Hence, this suggests that a tradeoff between training accuracy difference and NN-Mass values should affect the difference in test accuracies of various architectures. We next show that as the width multiplier increases further, the shallower models perform much more similar to deeper models. Fig. 4(c) shows the results for wm = 3. As evident, models with 6M-7M parameters achieve comparable test accuracy as models with up to 16M parameters (e.g., bucket Y in Fig. 4(d ) contains models ranging from {31 layers, 6.7M parameters}, all the way to {64 layers, 16.7M parameters}). In general, we observe that as the width increases, the capacity of the CNNs increases and, hence, the curves on Accuracy vs. NN-Mass plot come closer to each other. We next quantify the above observation by fitting a linear model to predict Accuracy using log(NN-Mass). As evident from Fig. 5 , the goodness-of-fit (R 2 ) increases from 0.74 to 0.84 to 0.90, as the width increases. This demonstrates that as the width of the CNN increases, NN-Mass becomes a better indicator of generalization.

Comparison between NN-Mass and Parameter Counting. Direct parameter counting is often used as a baseline for comparison in many generalization studies. In Appendix H.1 (Fig 10 ), we show that NN-Mass significantly outperforms parameter counting as an indicator of generalization for CNNs. Specifically, for low-width models (wm = 2), a linear model between test accuracy and log(#parameters) yields an R 2 = 0.76 (compared to R 2 = 0.84 for NN-Mass, see Fig. 10(a, b )); this indicates that parameter counting is a decent predictor of generalization for low-width models. However, for high-width models (wm = 3), parameter counting cannot predict generalization performance at all. More precisely, the parameter count achieves an R 2 = 0.14 for wm = 3 (Fig. 10(c) ). On the other hand, NN-Mass achieves a significantly higher R 2 = 0.90 (see Fig. 10(d) ).

We note that our work cannot be compared against generalization indicators presented in Arora et al. (2018); Neyshabur et al. (2015; 2017b; a) ; Bartlett et al. (2017) , because these works do not consider architectural aspects of the generalization problem and do not deal explicitly with CNN architectures with long-range links. The objective of this prior art is to understand how optimization properties Results for CIFAR-100 Dataset. We now corroborate our main findings on CIFAR-100 dataset which is significantly more complex than CIFAR-10. To this end, we train the models shown in Table 2 (Appendix G) from scratch on CIFAR-100. Fig. 6 (a) shows the test accuracy of various models as a function of number of parameters. As evident, several models achieve similar accuracy despite having highly different number of parameters (e.g., see models within box W in Fig. 6(a) ). Again, these models get clustered together when plotted against NN-Mass. Specifically, models within box W in Fig. 6 (a) fall into buckets Y and Z in Fig. 6(b) . Hence, models that got clustered together for CIFAR-10 dataset, also get clustered for CIFAR-100. To quantify the above results, we fit a linear model between test accuracy and log(NN-Mass) and, again, obtain a high R 2 = 0.84 (see Fig. 6(c) ). Therefore, our observations hold true across multiple image classification datasets.

To summarize, we show that (i) As NN-Mass increases, the test error of CNNs reduces, and (ii) NN-Mass can identify models that yield similar test accuracy, despite having very different #parameters/layers. We next use the latter observation to directly design efficient architectures.

4.2.2. CASE STUDY: DIRECTLY DESIGNING COMPRESSED MODELS WITH NN-MASS:

We now directly exploit the NN-Mass for model compression. Appendix H.3 explains how compressed models can be designed via NN-Mass. Following the setup in recent NAS works like DARTS [Liu et al. (2018) ], we train our models for 600 epochs and report their test accuracy.

Table 1 summarizes the number of parameters, FLOPS, and test accuracy of various CNNs. We first train two large CNN models of about 8M and 12M parameters with NN-Mass of 622 and 1126, respectively; both of these models achieve around 97% accuracy. Next, we train three compressed models: (i) A 5M parameter model with 40 layers and a NN-Mass of 755, (ii) A 4.6M parameter model with 37 layers and a NN-Mass of 813, and (iii) A 31-layer, 3.82M parameter model with a NN-Mass of 856. We set the NN-Mass of our compressed models between 750-850 (i.e., within the 600-1100 range of the manually-designed CNNs). Interestingly, we do not need to train any intermediate architectures to arrive at the above compressed CNNs. Indeed, NAS involves an initial "search-phase" over a space of operations to find the architectures [Zoph et al. (2018) ]. Similarly, model compression techniques like pruning [Li et al. (2016) ] and quantization [Hubara et al. (2017) ] also involve some kind of finetuning. In contrast, our models can be directly found using the closed Finally, Table 1 shows CIFAR-10 results for DARTS [Liu et al. (2018) ], a competitive NAS baseline.

As shown, with slightly lower 3.3M parameters, the first order DARTS achieves comparable accuracy to our proposed NN-Mass-based compressed models. Moreover, DARTS second order achieves a slightly higher accuracy (∼ 0.2% higher). However, it should be noted that the search space of DARTS (like all other NAS techniques) is very specialized and utilizes many state-of-the-art innovations such as depth-wise separable convolutions [Howard et al. (2017) ], dialated convolutions [Yu & Koltun (2015) ], etc. In contrast, we use the regular convolutions with only concatenation-type long-range links in our work and present a theoretically-grounded approach. We show that it is not just the specialized convolutions that result in models that attain high accuracy with less parameters, but also certain CNN architectures are inherently more accurate. Therefore, NN-Mass can be used to design efficient architectures even when the search space is limited to regular convolutions.

5. CONCLUSION AND FUTURE WORK:

In this paper, we have proposed a new, theoretically-grounded, architecture-level metric called NN-Mass that can indicate the generalization properties of CNN architectures a priori (i.e., without training). By integrating PAC-Bayes and small-world network science for the very first time, we have also theoretically proved two key properties of NN-Mass: (i) For a given depth and width, the higher the NN-Mass, the lower the generalization error, and (ii) Irrespective of total number of parameters, models with similar NN-Mass yield similar test accuracy. We have further presented extensive empirical evidence for the above theoretical findings by conducting experiments on real datasets such as CIFAR-10/100. Finally, we have used these new insights to directly design compressed models which reduce parameters/FLOPS by up to 3×, while losing minimal accuracy compared to the large CNN (e.g., 96.82% test accuracy vs. ∼ 97% for large CNN on CIFAR-10 dataset).

The present work opens several new directions in deep network generalization with implications for architecture search and model compression. As a future work, we plan to extend, both in theory and practice, NN-Mass for networks with branches and depth-wise separable convolutions. We further plan to bridge the theory between architectural aspects of generalization presented in this work vs. the generalization ideas discussed in prior art (e.g., weight-norms, etc.). 

A LONG-RANGE LINKS IN CNNS AND NETWORK SCIENCE:

Many recent innovations in deep learning architecture design have resulted in state-of-the-art deep networks that achieve excellent classification accuracy on complex vision and natural language applications. One of the most important innovations is the concept of shortcut connections in deep networks which enable complex architectures and have pushed the accuracy far beyond the traditional CNNs. For instance, Resnets [He et al. (2016) ] introduced residual blocks which add feature maps at alternate convolution layers. Similarly Densenets [Huang et al. (2017) ] have dense blocks that contain all-to-all connections. In contrast to Resnets, Densenets do not add feature maps but instead concatenate them together. The core idea in both of these models is to improve the information flow through the deep networks with the help of such shortcut connections between various layers.

Indeed, shortcut connections have long been a subject of study in the field of network science, e.g., small world networks [Watts & Strogatz (1998b) ] that specifically deal with networks with long-range and short-range links (e.g., in social, biological, transportation networks [Newman et al. (2011) ], and even multicore networks [Ogras & Marculescu (2006) ]). In this paper, we view the shortcut connections in deep networks as being analogous to the long-range links in generic networks such as social and transportation networks. Hence, network science can be a good choice for studying the dynamics of long-range links in deep networks. Since Densenets [Huang et al. (2017) ] have been shown to achieve higher accuracy than Resnets, we focus on concatenation-type long-range links.

B COMPUTING NETWORK WEIGHTS FOR CNN CHANNEL CONNECTIONS:

Note that, in a standard CNN, a convolutional layer with n input channels and m output channel consists of m filters, each with [k × k × n] dimensions. That is, as shown in Fig. 2 (b), red kernel in the filter convolves with red input channel, green kernel convolves with green input channel, and so on. The output of all such channel-wise convolutions are added together to obtain a single output channel (e.g., violet output channel in Fig. 2(b) ). However, this implicitly assumes that all input channels contribute equally to all output channels. Clearly, this assumption is counter-intuitive since our overall objective in an image classification problem is to separate out the identifying features of various classes at the final convolution layer (i.e., output channels at the final layer must activate for different features). Therefore, adding the outputs of channel-wise convolutions at each intermediate layer can make the training process of CNN inherently hard.

To alleviate the above problem, we explicitly assign different contributions from each input channel i to each output channel j as probabilities α ij . Specifically, for each output channel, we create a vector q j = {q 1j , q 2j , . . . , q nj } with Kaiming-normal initialization [He et al. (2015) ], where each element q ij of this vector denotes an unnormalized contribution from an input channel i to the given output channel j. Then, to generate the probabilities α ij , we simply compute the softmax of q j . The probabilities thus obtained are used as contributions from input channels to this output channel (e.g., {α R , α G , α B } in Fig. 2(b) ). We call the unnormalized weight vector q j as contribution weights, and the probabilities α ij 's as contribution probabilities throughout this paper. Hence, in contrast to a standard convolution where individual channel-wise convolutions are directly added to obtain one output channel (i.e., in a traditional CNN, α ij = 1 for all connections), the final convolution in our proposed model is computed as a weighted sum of channel-wise convolutions (where, weights are given by α ij ). Of note, throughout the training as well as inference, we keep these probabilities fixed.

Note that, all channel contributions (both long-range and short-range) are quantified by probabilities α ij 's. Specifically, instead of defining the contribution weight vectors (q i ) for each output channel, we can directly initialize a contribution weight matrix Q = [q T 1 , q T 2 , . . . , q T n ] for all channels in a cell. Then, the contribution probabilities α ij 's are obtained by taking column-wise softmax of Q. Next, we show that fixing random probabilities, in fact, leads to better test accuracy than fixing constant contributions from input to output channels.

B.1 IMPACT OF INPUT-TO-OUTPUT CONTRIBUTIONS:

To evaluate the impact of various α ij 's on CNN generalization, we train three separate models: (a) For the first model, we initialize the contribution weights for each layer to zeros and then take the softmax. Therefore, in this case, all contribution probabilities (α ij 's) are constant (1/N, N being the number of input channels per layer). (b) In the next model, we directly initialize α ij 's to all ones, which is the traditional CNN case where all channel-wise convolutions are directly added to obtain each output channel. The above two cases are equal-contribution cases. (c) Finally, to account for the proposed unequal-contribution case, we follow the process described in Appendix B above by fixing the contribution weights to Kaiming initialization [He et al. (2015) ] and then take the softmax. Table 2 shows the architecture of CNNs used in this section: all models have 46-layers, t c = 200, and width-multiplier of 2, which amounts to about 8M parameters. The models are trained for 350 epochs using stochastic gradient descent algorithm. Fig. 7 demonstrates the training and test accuracy for the three models. As shown, the model with proposed unequal contributions (via random probabilities) achieves about 96.6% accuracy, which is about 1% higher than the corresponding equal-contributions cases. This is a significant result because achieving accuracy beyond 96% is very hard for CIFAR-10 dataset [Zoph & Le (2016) ; Huang et al. (2017) ; Zagoruyko & Komodakis (2016); Liu et al. (2018) ]. Hence, this clearly demonstrates that not all input channels contribute equally to all output channels, and that even fixing the contributions to random probabilities significantly improves the generalization and convergence of the model. Note that, the α ij contributions do not come at any additional cost in terms of number of parameters since these values are fixed and can be directly incorporated into convolution weights by element-wise multiplication. Therefore, this simple observation can be used to improve the accuracy of CNNs without any overhead in terms of number of parameters.

C DERIVATION OF DENSITY OF A CELL:

Note that, the maximum number of channels contributing long-range links at each layer in cell c is given by t c . Also, for a layer i, possible candidates for long-range links = all channels up to layer (i -2) = w c (i -1) (see Fig. 2(c) ). Indeed, if t c is sufficiently large, initial few layers may not have t c channels that can supply long-range links. For these layers, we use all available channels for 

E PROOF OF THEOREM 2:

Theorem 2 (Generalization Bound for CNN Architectures in terms of NN-Mass). Consider singlecell CNN models with d c layers and w c channels per layer. Also, let t c be the number of channels contributing long-range links. If Q denotes a probability distribution over CNNs with long-range links and an architecture f Q ∼ Q has a NN-Mass of m, then, with probability at least 1 -δ the generalization error for this architecture is bounded as follows:

E D (L(f Q )) ≤ E S ( L(f Q )) + 1 2σ ( 1 6m -1 2 log(πem)) + log 2 √ N δ 2N ,

where, σ is the maximum number of connections a channel can have in a given CNN architecture.

Proof. To prove Theorem 2, it only suffices to express the KL-divergence term in Theorem 1 as a function of m. As a result, we must model the distributions Q and P for various CNNs. Since we are dealing with the hypothesis class of CNN architectures, network science can be used to explicitly model the distributions of the CNN topology. Hence, in order to study the distributions over CNN architectural topology (i.e., how various channels are connected together), network science concepts such as random networks, small-world networks, etc., can provide valuable insights. Towards this, the problem of computing distributions over CNN architectures can be equivalently seen as the problem of modeling connectivity in various network topologies. Now, it has been established in network science literature [Newman et al. (2011) ] that the connectivity of a network can be quantified using its degree distribution (recall that degree of a node in a network is given by total number of links connected to it). Hence, degree distribution can be used for modeling the distributions over various topologies of CNN architectures. Starting from the above ideas, we assume a priori that our CNN architecture does not have any longrange links. In other words, our prior distribution P for CNN architectures consists only of models with short-range links and no shortcut connections5 . Therefore, any architecture drawn from prior distribution P will look like a lattice network G with w c × d c total channels, and each channel at layer i is connected to w c channels from the previous layer. Let this prior distribution P be given by a distribution P (G) over lattice networks G.

Next, we model the distribution Q for the proposed CNN architectures with long-range links. Note that, the CNNs considered in our work have both short-range and long-range links (see Fig. 2(c ) and Fig. 8(inset) ). This kind of topology typically falls into the category of small-world networks which can be represented as a lattice network G (containing short-range links) superimposed with a random network R (to account for long-range links) [Monasson (1999) ; Newman & Watts (1999) ]. This is illustrated in Fig. 9 . Hence, the distribution over connectivities c in the small-world network can be written as:

EQUATION

Since P (R|G) represents the random long-range links created on top of the lattice network G, the connectivity of long-range links due to R|G follows a Poisson Distribution. This is because the degree distribution of random networks has been shown to be Poisson Distribution [ Barabasi (2016) ].

The λ parameter (i.e., the mean) of this Poisson Distribution is given by the average degree of the random network. Therefore, the average degree for R superimposed on G is given by: Then, the probability Q(c) = P (G) • P (R|G)) of observing connectivity c in the small-world network can be written as follows:

λ = kR|G =

EQUATION

where, c ≥ kG , the average degree of the lattice network G. Since average degree is given by total number of links divided by number of nodes, kG = (w 2 c (d c -1))/(w c d c ) = (w c (d c -1))/d c ≈ w c when d c >> 2 (and implicitly d c >> 1, which is true for deep CNNs). Now, let σ be the upper bound on the connectivity c. Also, we assume that the prior distribution P of drawing a lattice network is a uniform distribution for support c ∈ { kG -σ + 1, kG -σ + 2, . . . , kG + σ}. Then, the probability of observing a lattice network G with connectivity c is given by:

P (G) = 1 2σ if c ∈ { kG -σ + 1, kG -σ + 2, . . . , kG + σ} 0 otherwise (11)

Note that, since our proposed CNN architecture (drawn from distribution Q) is also based on a lattice network, the probability of drawing a lattice P (G) is same between P (i.e., the prior) and Q (i.e., our hypothesis).

We next use the above equations to simplify the KL-divergence term in Theorem 1. For deep CNNs with d c >> 2, we have 

KL(Q||P ) = - σ c= kG Q(c) log P (c) Q(c) = -

where, H Poisson( kR|G ) is the Entropy of R|G which follows a Poisson Distribution (equation 10). For a large λ, the Entropy of a Poisson Distribution can be approximated as [Evans & Boersma (1988) ]:

EQUATION

)

From equation 9, equation 13, and equation 12 and by ignoring the higher order terms of λ (since it is large), we get the following expression:

EQUATION

Putting the above expression into the bound in Theorem 1, we immediately get the generalization bound in terms of NN-Mass as shown in Theorem 2.

F PROOF OF COROLLARY 1:

Corollary 1 (Models with Similar Mass Achieve Similar Generalization Performance). Given two models of same width w c , let f L Q be a deeper model with NN-Mass m L , and let f S Q be a shallower model with NN-Mass m S such that m L ≤ m S . Then, the difference in expected test error of the two models is bounded with probability at least 1 -δ as follows:

E D (L(f L Q )) -E D (L(f S Q )) ≤ E S ( L(f L Q )) -E S ( L(f S Q )) + 1 2σ m S -m L 6m L m S -1 2 log m L m S + log 4N δ 2

In other words, irrespective of number of parameters and layers, as the NN-Mass for the two models becomes similar, their test error is also expected to become similar.

Proof. We first compute the difference between the expected test errors for the deeper model f L Q and the shallower model f S Q . Then, according to Theorem 1, we have:

E D (L(f L Q )) -E D (L(f S Q )) ≤ E S ( L(f L Q )) -E S ( L(f S Q )) + KL(Q L ||P ) + log 2 √ N δ 2N - KL(Q S ||P ) + log 2 √ N δ

(15) To simplify the difference of square roots, we use the following lemma. Lemma 1 (Two Related Triangles (Hoggatt et al. (1960) )). If three non-negative numbers a, b, and c satisfy the triangle inequality (i.e., a + b ≥ c, b + c ≥ a, and a + c ≥ b), then the following also holds:

| √ b - √ c| ≤ √ a ≤ √ b + √ c

Proof for this lemma is given in Hoggatt et al. (1960) .

Let b = KL(Q L ||P )+log 2 √ N δ

, and let c =

KL(Q S ||P )+log 2 √ N δ

. Then, all we need to do is to find a such that the triangle inequality between a, b, and c is satisfied. Once we find such an a, the difference of square roots in equation 15 can be bounded by √ a. Towards this, we begin by finding a lower bound for b + c:

EQUATION

where, the first inequality follows from the fact that the sum of two non-negative real numbers will always be greater than or equal to the absolute value of their difference. The second equality follows from equation 14. Specifically, since KL-divergence is a decreasing function of NN-Mass, and since

m L ≤ m S , it follows that KL(Q L ||P ) ≥ KL(Q S ||P ).

Now that we have a lower bound on b + c, we use this value as a. In order to use Lemma 1, we only need to make sure that the chosen values for a, b, and c satisfy the triangle inequality. Note that, by construction, b + c ≥ a. So, we only need to prove that a + c ≥ b and a + b ≥ c. For the former, it is easy to see that a

+ c = b + 1 2N log 4N δ 2 =⇒ a + c ≥ b (since 1 2N log 4N

δ 2 is non-negative as the size of training set N is a large number and δ ∈ (0, 1]). For the latter, we have:

EQUATION

Hence, a, b, and c satisfy the triangle inequality. Therefore, we can use Lemma 1 to bound the difference of square roots in equation 15. Putting KL-divergence from equation 14 into a in equation 16, we get:

EQUATION

Finally, using Lemma 1 on equation 15 with the above a, we get the corollary statement. Clearly, the difference in expected error for the two models reduces as their NN-Mass values become similar. Therefore, irrespective of the number of parameters, if two models have similar NN-Mass, they are expected to yield similar test accuracies. We will present extensive empirical evidence to verify this corollary.

G COMPLETE DETAILS OF EXPERIMENTAL SETUP:

We first analyze the impact of non-uniform contributions from input channels to output channels at all layers (Appendix B). Then, we perform the Neural Architecture Space Exploration with NN-Mass and NN-Density. Specifically, we run many experiments with CIFAR-10 and CIFAR-100 datasets for CNNs containing different number of layers, parameters, NN-Mass and NN-Density:

1. Impact of Input-to-Output Contributions: We train three separate models to evaluate the impact of various α ij 's on CNN generalization: Two models for constant contribution from all inputs to all outputs at each layer, and one model for the proposed unequal contributions via random probabilities. As shown in Table 2 , for these experiments, we create a 46layer model with width-multiplier6 of 2, and a single cell (i.e., any channel from any layer can contribute to any other channel7 ). Also, t c = 200 long-range link candidates are selected randomly at each layer. We have already explained the results of this experiment in Appendix B.

2. Neural Architecture Space Exploration and Correlation of NN-Mass with Generalization: Next, we explore the architecture design space using our proposed NN-Mass and NN-Density metrics. We further demonstrate that NN-Mass is indeed correlated with generalization (Theorem 2) and can be used to identify models with similar accuracy despite having different number of parameters (Corollary 1). All models in this category are trained for 200 epochs. We conduct the following classes of experiments:

• Impact of Varying NN-Density. We first systematically analyze how the test accuracy changes when average density (as defined in equation 2) is varied for CNNs of different depths. Specifically, we fix the width of all models and vary the depth (total depth of the CNN with three cells = 3d c + 4) and the maximum number of longrange link candidates (t c ). We choose t c for different cells such that the density for all networks varies as: {0. Fig. 10 (a), we fit a linear model between test accuracy and log(#parameters) and found that the R 2 for this model is 0.76 which is slightly lower than that obtained for NN-Mass (R 2 = 0.84, see Fig. 10(b) ). When the width multiplier of CNNs increases to three, parameter counting completely fails to fit the test accuracies of the models (R 2 = 0.14). In contrast, NN-Mass significantly outperforms parameter counting for wm = 3 as it achieves an R 2 = 0.90. This demonstrates that NN-Mass is indeed a significantly stronger indicator of generalization than parameter counting for models with long-range links.

H.2 NN-MASS TO PREDICT TEST ACCURACY OF UNKNOWN ARCHITECTURES:

We now demonstrate that NN-Mass can be used to predict the test accuracy of unknown architectures that have not been trained before. Towards this, we create a testing set of new architectures by training 20 previously unknown architectures with wm = 2, and {28, 43, 52, 58} layers. For these models, we vary the NN-Density between {0.125, 0.175, 0.225, 0.275, 0.325} which is different from the initial architecture space exploration setting in 

H.3 NN-MASS FOR DIRECTLY DESIGNING COMPRESSED ARCHITECTURES:

Our theoretical and empirical evidence shows that NN-Mass is a reliable indicator for models which achieve similar accuracy despite having different number of layers and parameters. Therefore, this observation can be used for model compression as follows:

• First, train a reference big CNN (with a large number of parameters and layers) which achieves very high accuracy on the target dataset. Calculate its NN-Mass (denoted m L ).

• Next, create a completely new and significantly compressed model using far fewer parameters and layers, but with a NN-Mass comparable to or higher than the large CNN. This process is very fast as the new model is created without any a priori training. For instance, to design a compressed CNN of width w c and depth per cell d c and NN-Mass m S ≈ m L , we only need to find how many long-range links to add in each cell. Since, NN-Mass has a closed form equation (i.e., equation 3), a simple search over the number of long-range links can directly determine NN-Mass of various architectures. Then, we select the architecture with the NN-Mass close to that of the reference CNN. Unlike current manual or NAS-based methods, our approach does not require training of individual architectures during the search.

• Since NN-Mass of the compressed model is similar to that of the reference CNN, Corollary 1 suggests that the newly generated model will lose only a small amount of accuracy, while significantly reducing the model size. To validate this, we train the newly compressed model and compare its test accuracy against that of the original large CNN.

Note that, our work is agnostic to what dataset is used since we rely solely on the properties of CNN architectures. That is, if we train the large CNN on a different dataset, our compressed model should still give accuracy close to that of the large CNN on the new dataset. Of course, the range of accuracy of different models will vary when the dataset is changed, but different architectures with similar NN-Mass should still yield a similar test accuracy. This observation is explicitly shown for CIFAR-10 and CIFAR-100 datasets in experiments (The "Results for CIFAR-100 Dataset" part in Section 4.2.1 shows that the same set of models that got clustered together for CIFAR-10 dataset, still form clusters for CIFAR-100 on the test accuracy vs. NN-Mass plot).

:

See Appendix B for more details on how these αij probabilities are assigned to channel connections.

Not all links are shown in Fig.2(c): All output channels at layer i will receive short-range links from the last layer, and additional long-range links from selected previous channels (seeFig. 8 (inset) in Appendix D).

When tc > wc(i -1), total possible channels that can supply long-range links is limited to wc(i -1), i.e., the total number of channels until layer i -2

Unlike the

5M parameter model in Table1(which we partially explored by training it for 200 epochs in the last section during NASE), we never trained these 31-and 37-layer compressed models before. In fact, we never trained any other 37-layer models at all throughout this work. Hence, these models are completely new!

Note that, choosing a prior without any long-range links makes sense even from an "evolution of CNN architectures" perspective since, initially, CNN architectures such as AlexNet[Krizhevsky et al. (2012)] and VGG-16[Simonyan & Zisserman (2014)] were developed (which do not have any shortcut connections), and complex architectures with long-range connections such asNASNET [Zoph et al. (2018)], DenseNets[Huang et al. (2017)], etc. were proposed only later.

Base number of channels in each group is[16,32,64]. Hence, a width-multiplier of 2 implies that each group will have[32,64,128] channels per layer.

Note that for evaluating the impact of αij's, we have fixed the number of cells to one; as explained in the footnote above, this cell contains three separate groups of[32,64,128] channels per layer. We found that creating more cells improves the accuracy and, therefore, in the rest of the paper, we will use three cells for all models.

Figures and Tables:

Figure 1: Approach Overview: (a) First, model a CNN as a network of channels. (b) Next, we propose NN-Mass and NN-Density, where NN-Mass is a theoretically-grounded metric that indicates generalization capability. (c) Exploit NN-Mass to directly design significantly compressed models.

Figure 2: (a) CNN consisting of three cells of d c layers each. (b) An input channel i contributes to a given output channel j with some fixed probability α ij . (c) Each cell contains d c layers with w c channels per layer. Output channels at each layer get contributions from output channels of last layer and additional long-range links from previous layers (via concatenation). Not all links are shown. The contribution probabilities (α ij 's) are used to define the weighted adjacency matrix of the CNN.

Figure 3: CIFAR-10 Width Multiplier wm = 2: (a) Shallower models with higher density can reach comparable accuracy to deeper models with lower density. This does not help since models with different depths achieve comparable accuracies at different densities. (b) Models with very different #parameters (box W) achieve similar test accuracies. (c) Models with similar accuracy often have similar NN-Mass: Models in W get clustered into Z. Results are reported as mean of three runs.

Fig. 3(a)). Therefore, NN-Density alone cannot be used to identify CNNs with similar generalization performance. Hence, we next focus on NN-Mass.Impact of Varying NN-Mass on Generalization.Fig. 3(b)  shows the test accuracy of the trained models vs. total parameters. As evident, some 40-layer models with 5M parameters (e.g., model A in Fig.3(b) within box W) perform comparably to several 64-layer models with more than 8M parameters (models D,E in Fig.3(b)). Hence, models with highly different numbers of parameters and layers can achieve comparable accuracies (see all models within box W in Fig.3(b)).

vs. Number of Parameters --wm = 3 c.

Figure 4: Similar observations hold for low-(wm = 1) and high-width (wm = 3) models: (a, b) Many models with very different #parameters (boxes U and V) get clustered into buckets W and Z (see also other buckets). (c, d) For high-width, we observe significantly tighter clustering compared to the low-width case. Results are reported as mean of three runs. a.b.

Figure 5: Impact of varying width: (a) Width multiplier, wm = 1, (b) wm = 2, and (c) wm = 3.As width increases, capacity of small (shallower) models increases and, therefore, the accuracy-gap between models of different depths reduces. Hence, the R 2 for linear fit increases as width increases.

vs. log(NN-Mass). R-squared = 0.84 c.

Figure 6: Similar results are obtained for the CIFAR-100 dataset (wm = 2). (a) Models in box W have significantly different #parameters but achieve similar accuracy. (b) These models get clustered into buckets Y and Z. (c) The R 2 value for fitting a linear regression model is 0.84 which shows that NN-Mass is a good predictor of test accuracy. Results are reported as mean of three runs.

Figure 8: An example CNN to calculate NN-Density and NN-Mass. Not all links are shown in the main figure for simplicity. The inset shows the contribution from all long-range and short-range links:The feature maps for randomly selected channels are concatenated at the current layer (similar to Densenets[Huang et al. (2017)]). At each layer in a given cell, the maximum number of channels that can contribute long-range links is given by t c .

Figure 9: (a) Small-World Networks in traditional network science are modeled as a superposition of a lattice network (G) and a random network R [Watts & Strogatz (1998a); Newman & Watts (1999); Monasson (1999)]. (b) A CNN with both short-range and long-range links can be similarly modeled as a random network superimposed on a lattice network. Not all links are shown for simplicity.

Poisson( kR|G )  ),

vs. log(#Parameters) --wm = 3. R-squared = 0.14

Figure 10: NN-Mass as an indicator of generalization performance compared to parameter counting. (a) For wm = 2, log(#parameters) fits the test accuracy with an R 2 = 0.76. (b) For the same wm = 2 case, log(NN-Mass) fits the test accuracy with a higher R 2 = 0.84. For lower width, parameter counting is a decent indicator of generalization performance. (c) For higher width (wm = 3), parameter counting completely fails to fit the test accuracy of various models (R 2 = 0.14). (d) In contrast, NN-Mass still fits the accuracies with a high R 2 = 0.9.

Fig 5(b) or Table 2 (in the initial setting, {31, 40, 49, 64}-layer models were trained for NN-Densities: {0.10, 0.15, 0.20, 0.25, 0.30}). We next use the linear model trained on the {31, 40, 49, 64}-layer models (see Fig. 5(b)) to predict the test accuracy of the unknown {28, 43, 52, 58}-layer CNNs. Note that, our testing set consists of models with both different number of layers and different NN-Densities (and, implicitly, different NN-Mass values) compared to the training set.

Fig. 11  shows that the testing R 2 = 0.79 (i.e., the R 2 obtained by predicting the accuracy of models in the testing set) which is close to the training R 2 = 0.84 (see Fig.5(b)). Hence, NN-Mass can be used to predict test accuracy of models which were never trained before.

Figure11: Linear modeled trained in Fig.5(b) is used to predict the test accuracy of completely new architectures. The resulting R 2 = 0.79 is still high and is comparable to the training R 2 = 0.84. The linear model was trained on the test accuracies and NN-Mass of models with {31, 40, 49, 64} layers, and densities varying as {0.10, 0.15, 0.20, 0.25, 0.30}. To create the testing set, we trained completely new models with {28, 43, 52, 58} layers, and densities varying as {0.125, 0.175, 0.225, 0.275, 0.325}.

] models were used for NAS[Xie et al. (2019);Wortsman et al. (2019)]. However, like the rest of the NAS research,[Xie et al. (2019); Wortsman et al. (2019)] did not explore what theoretical characteristics of the architecture make models (with different number of parameters and layers) achieve similar generalization performance. Hence, to our knowledge, no theoretical attempt has been made to understand the link between architecture design and generalization.Another prior work analyzes the impact of initialization on pruned networks via a lottery ticket hypothesis[Frankle & Carbin (2018)]. However, this work (and the rest of the model compression literature) does not explore the characteristics of the architectures that can indicate generalization. Generalization of deep networks. The field of generalization has recently gained attention to understand why deep networks generalize without overfitting [Saxe et al. (2013); Nye & Saxe (2018);

Table content: <table/>

Exploiting NN-Mass for Model Compression on CIFAR-10 Dataset. All our experiments are reported as mean ± standard deviation of three runs. DARTS results are reported fromLiu et al. (2018) which uses a similar setup for training the final model discovered after the search.

Table content: <table><tr><td>Model</td><td>Architecture design method</td><td>#Parameters/ #FLOPS</td><td>Number of layers/ cells/long-range links (t c )</td><td>Specialized search space?</td><td>NN-Mass</td><td>Test Accuracy</td></tr><tr><td>DARTS (first order)</td><td colspan="2">NAS [Liu et al. (2018)] 3.3M/-</td><td>-/20 cells/-</td><td>Yes</td><td>-</td><td>97.00 ± 0.14%</td></tr><tr><td colspan="3">DARTS (second order) NAS [Liu et al. (2018)] 3.3M/-</td><td>-/20 cells/-</td><td>Yes</td><td>-</td><td>97.24 ± 0.09%</td></tr><tr><td>Train large models to be compressed</td><td>Manual Manual</td><td>11.89M/3.63G 8.15M/2.54G</td><td>64/3 cells/ [90, 170, 300] 64/3 cells/ [50,100,150]</td><td>No No</td><td>1126 622</td><td>97.02 ± 0.06% 96.99 ± 0.07%</td></tr><tr><td>Proposed</td><td>Directly via NN-Mass</td><td>5.02M/1.59G</td><td>40/3 cells/ [60,130,170]</td><td>No</td><td>755</td><td>97.00 ± 0.06%</td></tr><tr><td>Proposed</td><td>Directly via NN-Mass</td><td>4.69M/1.51G</td><td>37/3 cells/ [70,140,180]</td><td>No</td><td>813</td><td>96.93 ± 0.10%</td></tr><tr><td>Proposed</td><td>Directly via NN-Mass</td><td>3.82M/1.2G</td><td>31/3 cells/ [70,140,200]</td><td>No</td><td>856</td><td>96.82 ± 0.05%</td></tr></table>

Mitchell Wortsman, Ali Farhadi, and Mohammad Rastegari. Discovering neural wirings. arXiv preprint arXiv:1906.00586, 2019. Bichen Wu, Xiaoliang Dai, Peizhao Zhang, Yanghan Wang, Fei Sun, Yiming Wu, Yuandong Tian, Peter Vajda, Yangqing Jia, and Kurt Keutzer. Fbnet: Hardware-aware efficient convnet design via differentiable neural architecture search. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 10734-10742, 2019. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03530, 2016. Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv:1611.01578, 2016.

Table content: <table><tr><td colspan="3">Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural</td></tr><tr><td colspan="2">networks for image recognition. arXiv preprint arXiv:1904.01569, 2019.</td><td/></tr><tr><td colspan="3">Tien-Ju Yang, Yu-Hsin Chen, and Vivienne Sze. Designing energy-efficient convolutional neural</td></tr><tr><td colspan="2">networks using energy-aware pruning. arXiv:1611.05128, 2016.</td><td/></tr><tr><td colspan="3">Fisher Yu and Vladlen Koltun. Multi-scale context aggregation by dilated convolutions. arXiv</td></tr><tr><td>preprint arXiv:1511.07122, 2015.</td><td/><td/></tr><tr><td>Sergey Zagoruyko and Nikos Komodakis.</td><td>Wide residual networks.</td><td>arXiv preprint</td></tr><tr><td>arXiv:1605.07146, 2016.</td><td/><td/></tr><tr><td>Chiyuan Zhang,</td><td/><td/></tr></table>

1, 0.15, 0.2, 0.25, 0.3}. That is, different t c values result in architectures with different NN-Mass and number of parameters and, hence, allows us to explore the architecture design space (see Example 1 for an illustration on how the set {d c , w c , t c } is used to define an architecture). Complete details of various t c values for different networks is given in Table. 2. • Impact of Varying NN-Mass and Width. The above experiment indirectly changes NN-Mass (due to varying NN-Density). We next explicitly vary the NN-Mass across models of different widths to analyze how the relationship between test accuracy and NN-Mass changes across a large spectrum of architectures. For all experiments, we explicitly quantify the relationship between accuracy of CNNs vs. NN-Mass by fitting a linear regression model. We report the goodness-of-fit (or coefficient of determination, R 2 ) of the linear model.

Table content: <table/>

Peer review (iclr2020):
------------------------ Summary: This paper derives a new generalization bound for CNNs that includes a term, NN-mass, based on PAC-Bayesian setup and Network Science. Notably, NN-mass can be calculated from a CNN architecture *without training*. It plots some graphs showing that log(NN-mass) correlates strongly with the test accuracy of CNNs of varying depth. It also proposes new architectures for the CIFAR-10 dataset, and compares its results against DARTS. ------------------------ Decision: Reject. 1) Theory contains a fatal flaw. McAllester*s Bound only applies to Gibbs classifiers -- every time a prediction is made, a new classifier is randomly sampled from the posterior distribution. (See: The Proof of McAllester*s PAC-Bayesian Theorem, M. Seegar 2002.) In other words, Theorem 1 does not bound the generalization gap for individual classifiers drawn from Q; it only bounds the generalization gap for the expected accuracy of a Gibbs classifier defined by the distribution Q. I didn*t check the proof for Theorem 2, but even if the steps are correct, Corollary 1 interprets f_Q^L and f_Q^S as individual models drawn from Q, which is incorrect. 2) Experiments do not directly support the generalization bound in Corollary 1. Corollary 1 is not about the relationship between log(NN-mass) and test accuracy; it is about the relationship between (generalization gap of deep model) - (generalization gap of shallow model) and the square root term. Unfortunately, data augmentation complicates this formula. For a proper evaluation, the models should not be trained with cutout. Besides, figure 10 consists of trend lines with just 20 data points, which is not very convincing. It would be much more convincing if this paper had a Q-Q plot of generalization error against NN-mass over a dataset of ~100 data points. 3) Empirical study does not verify whether different optimization and regularization settings would affect the results. Recent advancements in the performance of image classifiers came not only from architectures; it also comes from innovations in optimization (e.g., batch norm, learning rate scheduling) and regularization (e.g., cutout, drop path). A training-free architecture search procedure thus faces this concern: if we change these training hyperparameters, will the results still hold? Thus, experiments to confirm Corollary 1 should be repeated with/without cutout, with/without batch-norm, and with different learning rate schedules. ------------------------ Novelty: Applying Network science to the study of generalization of untrained CNNs seems novel to me. ------------------------ Clarifications: - Would this theory predict that DenseNets with a large number of channels have superior generalization performance compared to ResNets? If so, why are current state-of-the-art ImageNet models more similar to ResNet than DenseNet? ------------------------ Other issues: - Why does Table 1 choose DARTS, an architecture for which the NN-mass cannot be computed? Why not compare against DenseNet? ------------------------ Minor issues: - page 1, *In contrast, traditional wisdom suggests that models should overfit when the number of parameters is much larger than the dataset size (which is true in practice).* It should be *(which is *not* true in practice)*? - page 2, s/Densenet/DenseNet - page 6, Remark 1: *Theorem 2 guarantees that the test error should reduce as NN-Mass increases*. This overstates what can be deduced from a PAC upper bound; an upper bound alone can *suggest* a relationship, but it cannot guarantee anything because we don*t know if the bound is looser at lower values of NN-Mass. - page 6, Corollary 1: f^S_Q and m_S correspond to the shallower network, and f^L_Q and m_L correspond to the deeper network. Why not use D instead of L to label the deeper network? ------------------------