Title: LEARNABILITY OF LEARNED NEURAL NETWORKS

Abstract: This paper explores the simplicity of learned neural networks under various settings: learned on real vs random data, varying size/architecture and using large minibatch size vs small minibatch size. The notion of simplicity used here is that of learnability i.e., how accurately can the prediction function of a neural network be learned from labeled samples from it. While learnability is different from (in fact often higher than) test accuracy, the results herein suggest that there is a strong correlation between small generalization errors and high learnability. This work also shows that there exist significant qualitative differences in shallow networks as compared to popular deep networks. More broadly, this paper extends in a new direction, previous work on understanding the properties of learned neural networks. Our hope is that such an empirical study of understanding learned neural networks might shed light on the right assumptions that can be made for a theoretical study of deep learning.

1. INTRODUCTION:

Over the last few years neural networks have significantly advanced state of the art on several tasks such as image classification (Russakovsky et al. (2015) ), machine translation (Xiong et al. (2016) ), structured prediction (Belanger & McCallum (2016) ) and so on, and have transformed the areas of computer vision and natural language processing. Despite the success of neural networks in making these advances, the reasons for their success are not well understood. Understanding the performance of neural networks and reasons for their success are major open problems at the moment. Questions about the performance of neural networks can be broadly classified into two groups: i) optimization i.e., how are we able to train large neural networks well even though it is NP-hard to do so in the worst case, and ii) generalization i.e., how is it that the training error and test error are close to each other for large neural networks where the number of parameters in the network is much larger than the number of training examples (highly overparametrized). This paper explores three aspects of generalization in neural networks.

The first aspect is the performance of neural networks on random training labels. While neural networks generalize well (i.e., training and test error are close to each other) on real datasets even in highly overparametrized settings, Zhang et al. (2017) shows that neural networks are nevertheless capable of achieving zero training error on random training labels. Since any given network will have large error on random test labels, Zhang et al. (2017) concludes that neural networks are indeed capable of poor generalization. However since the labels of the test set are random and completely independent of the training data, this leaves open the question of whether neural networks learn simple patterns even on random training data. Indeed the results of Rolnick et al. (2017) establish that even in the presence of massive label noise in the training data, neural networks obtain good test accuracy on real data. This suggests that neural networks might learn some simple patterns even with random training labels. The first question this paper asks is (Q1): Do neural networks learn simple patterns on random training data?

A second, very curious, aspect about the generalization of neural networks is the observation that increasing the size of a neural network helps in achieving better test error even if a training error of zero has already been achieved (see, e.g., Neyshabur et al. (2014) ) i.e., larger neural networks have better generalization error. This is contrary to traditional wisdom in statistical learning theory which holds that larger models give better training error but at the cost of higher generalization error. A recent line of work proposes that the reason for better generalization of larger neural networks is implicit regularization, or in other words larger learned models are simpler than smaller learned models. See Neyshabur (2017) for references. The second question this paper asks is (Q2): Do larger neural networks learn simpler patterns compared to smaller neural networks when trained on real data?

The third aspect about generalization that this paper considers is the widely observed phenomenon that using large minibatches for stochastic gradient descent (SGD) leads to poor generalization Le-Cun et al..

(Q3): Are neural networks learned with small minibatch sizes simpler compared to those learned with large minibatch sizes?

All the above questions have been looked at from the point of view of flat/sharp minimizers Hochreiter & Schmidhuber (1997) . Here flat/sharp corresponds to the curvature of the loss function around the learned neural network. Krueger et al. (2017) for true vs random data, Sagun et al. (2017) for large vs small neural networks and Keskar et al. (2016) for small vs large minibatch training, all look at the sharpness of minimizers in various settings and connect it to the generalization performance of neural networks. While there certainly seems to be a connection between the sharpness of the learned neural network, there is as yet no unambiguous notion of this sharpness to quantify it. See Dinh et al. (2017) for more details. This paper takes a complementary approach: it looks at the above questions through the lens of learnability. Let us say we are considering a multi-class classification problem with c classes and let D denote a distribution over the inputs x ∼ R d . Given a neural network N , draw

n independent samples x tr 1 , • • • , x tr n from D and train a neural network N on training data (x tr 1 , N (x tr 1 )), • • • , (x tr n , N (x tr n )), where N (x) ∈ [c]

denotes the prediction of N on x. The learnability of a neural network N is defined to be

EQUATION

Note that L(N ) implicitly depends on D, the architecture and learning algorithm used to learn N as well as n. This dependence is suppressed in the notation but will be clear from context. Intuitively, larger the L(N ), easier it is to learn N from data. This notion of learnability is not new and is very closely related to probably approximately correct (PAC) learnability Valiant (1984) ; Kearns & Vazirani (1994) . In the context of neural networks, learnability has been well studied from a theoretical point as we discuss briefly in Sec.2. There we also discuss some related empirical results but to the best of our knowledge there has been no work investigating the learnability of neural networks that are encountered in practice.

This paper empirically investigates the learnability of neural networks of varying sizes/architectures and minibatch sizes, learned on real/random data in order to answer (Q1) and (Q2) and (Q3). The main contributions of this paper are as follows:

Contributions: The results in this paper suggest that there is a strong correlation between generalizability and learnability of neural networks i.e., neural networks that generalize well are more learnable compared to those that do not generalize well. Our experiments suggest that

• Neural networks do not learn simple patterns on random data.

• Learned neural networks of large size/architectures that achieve higher accuracies are more learnable.

• Neural networks learned using small minibatch sizes are more learnable compared to those learned using large minibatch sizes.

Experiments also suggest that there are qualitative differences between learned shallow networks and deep networks and further investigation is warranted.

Paper organization: The paper is organized as follows. Section 2 gives an overview of related work. Section 3 presents the experimental setup and results. Section 5 concludes the paper with some discussion of results and future directions.

2. RELATED WORK:

Learnability of the concept class of neural networks has been addressed from a theoretical point of view in two recent lines of work. The first line of work shows hardness of learning by exhibiting a distribution and neural net that is hard to learn by certain type of algorithms. We will mention one of the recent results, further information can be obtained from references therein. Song et al. (2017) (see also Shamir (2016) ; Shalev-Shwartz et al. ( 2017)) show that there exist families of single hidden layer neural networks of small size that is hard to learn for statistical query algorithms (statistical query algorithms Kearns (1998) capture a large class of learning algorithms, in particular, many deep learning algorithms such as SGD). The result holds for log-concave distributions on the input and for a wide class of activation functions. If each sample is used only ones, then the hardness in their result means that the number of samples required is exponentially large. These results do not seem directly applicable to input distributions and networks encountered in practice.

The et al. (2017) . Recently, Goel & Klivans (2017) give a provably efficient algorithm for learning one hidden layer neural networks consisting of sigmoids. However, their algorithm, which uses the kernel method, is different from the ones used in practice and the output hypothesis is not in the form of a neural network.

Using one neural net to train another has also been used in practice, e.g. Ba & Caurana (2013); Hinton et al. (2015) ; Urban et al. (2016) . The goal in these works is to train a small neural net to the data with high accuracy by a process often called distillation. To this end, first a large network is trained to high accuracy. Then a smaller network is trained on the original data, but instead of class labels, the training now uses the classification probabilities or related quantities of the large network. Thus the goal of this line of research, while related, is different from our goal.

3. EXPERIMENTS:

In this section, we will describe our experiments and present results.

3.1. EXPERIMENT SETUP:

All our experiments were performed on CIFAR-10 Krizhevsky et al. (2009) . The 60, 000 training examples were divided into three subsets D 1 , D 2 and D 3 with D 1 and D 2 having 25000 samples each and D 3 having 10000 samples. We overload the term D i to denote both the unlabeled as well as labeled data points in the i th split; usage will be clear from context. For all the experiments, we use vanilla stochastic gradient descent (SGD) i.e., no momentum parameter, with an initial learning rate of 0.01. We decrease the learning rate by a factor of 3 4 if there is no decrease in train error for the last 10 epochs. Learning proceeds for 500 epochs or when the training zero-one error becomes smaller than 1%, whichever is earlier. Unless mentioned otherwise, minibatch size of 64 is used and the final training zero-one error is smaller than 1%. For training, we minimize logloss and do not use weight decay. The experimental setup is as follows.

Step 1 Train a network N 1 on (labeled) D 1 .

Step 2 Use N 1 to predict labels for (unlabeled) D 2 , denoted by N 1 (D 2 ).

Step 3 Train another network N 2 on the data (D 2 , N 1 (D 2 )).

Learnability of a network is computed as:

1 |D3| |D3| i=1 1 {N1(D3)=N2(D3)} × 100%.

All the numbers reported here were averaged over 5 independent runs. We now present experimental results aimed at answering (Q1), (Q2) and (Q3) we raised in Section 1.

3.2. EFFECT OF DATA:

The first set of experiments are aimed at understanding the effect of data on the simplicity of learned neural networks. We work with three different kinds of data. In this section we vary the data in three ways

• True data: Use labeled images from CIFAR-10 for D 1 in Step 1.

• Random labels: Use unlabeled images from CIFAR-10 for D 1 in Step 1 and assign them random labels uniformly between 1 and 10. clearly demonstrates that the complexity of a learned neural network heavily depends on the training data. Given that complexity of the learned model is closely related to its generalizability, this further supports the view that generalization in neural networks heavily depends on training data. Similar results can be observed for shallow convolutional networks on CIFAR-100 in Table 4 .

It is perhaps surprising that the learnability of networks trained on random data is substantially higher than 10% for shallow networks, on the other hand it's close to 10% for deeper networks. Some of this is due to class imbalance: in the case of true data, class imbalance is minimal for all architectures. While, when trained on random labels or random images output of N 1 on D 2 was skewed. This happened both for shallow networks and deeper networks but was slightly higher for shallow networks. Table 5 presents the percentage of each class in the labels of N 1 on D2. However, we do not have a quantification of how much of learnability in the case of shallow networks arises due to class imbalance and a compelling reason for high learnability of shallow networks. 6 and 7 8 and 9 present these results for VGG-11 and GoogleNet. The key point we would like to point out from these tables is that if we focus on those examples where N 1 does not predict the true label correctly i.e., TLP = 0 or the first row in the tables, we see that approximately half of these examples are still learned correctly by N 2 . Contrast this with the learnability values of N 1 learned with random data which are all less than 20%. This suggests that networks learned on true data make simpler predictions even on examples which they misclassify.

3.3. EFFECT OF NETWORK SIZE/ARCHITECTURE:

The second set of experiments are aimed at understanding the effect of network size and architecture on the learnability of the learned neural network. First, we work with shallow convolutional neural networks (CNN) with 1 convolutional layer and 1 fully connected layer.

The results are presented in Table 10 . Even though training accuracy is always greater than 99%, test increases with increase in the size of N 1 -Neyshabur et al. ( 2014) reports similar results for 2-layer multilevel perceptrons (MLP). It is clear that for any fixed N 2 , the learnability of the learned network increases as the number of filters in N 1 increases. This suggests that the larger learned networks are indeed simpler than the smaller learned networks. Note also that for every N 1 , its learnability values are always larger than its test accuracy when N 2 has 16 or more filters. This suggests that N 2 learns information about N 1 that is not contained in the data.

We performed the same experiment for some popular architectures as in Section 3.2. The results are presented in Table 12 . Note that the accuracies reported here are significantly lower than those reported in published literature for the corresponding models; the reason for this is that our data size is essentially cut by half (see Section 3.1). Except for the case where N 2 is ResNet18 and N 1 is either a VGG or ResNet, there is a positive correlation between test accuracy and learnability i.e., a network with higher test accuracy is more learnable. We do not know the reason for the exception mentioned above. Furthermore, the pattern observed for shallow networks, that learnability is larger than accuracy, does not seem to always hold for these larger networks.

3.4. EFFECT OF BATCH SIZE:

The third set of experiments are aimed at understanding the effect of minibatch size on the learned model. For this set of experiments, N 1 and N 2 are again varied over different architectures while keeping the architectures of N 1 and N 2 same. The minibatch size for training of N 2 (Step 3) is fixed to 64 while the minibatch size for training of N 1 (Step 1) is varied over {32, 64, 128, 256}. Table 13 presents these results. It is clear from these results that for any architecture, increasing the minibatch size leads to a reduction in learnability. This suggests that using a larger minibatch size in SGD leads to a more complex neural network as compared to using a smaller minibatch size.

3.5. VARIABILITY OF PREDICTIONS:

In this section, we will explore a slightly orthogonal question of whether neural networks learned with different random initializations converge to the same neural network, as functions. While there are some existing works e.g., Goodfellow et al. (2014) , which explore linear interpolation between the parameters of two learned neural networks with different initializations, we are interested here in understanding if different SGD solutions still correspond to the same function. In order to do this, we compute the confusion matrix for different SGD solutions. If SGD is run k times (k = 5 in this case), recall that the (i, j) entry of the confusion matrix, where 1 ≤ i, j ≤ k gives the fraction of examples on which the i th and j th SGD solutions agree. The following are the confusion matrices The experimental results so far show a clear correlation between learnability and generalizability of learned neural networks. This naturally leads to the question of why this is the case. We hypothesize that learnability captures the inductive bias of SGD training of neural networks. More precisely, when we start training, intuitively, the initial random network generalizes well (i.e., both train and test errors are high) and is also simple (learnability is high). As SGD changes the network to reduce the training error, it becomes more complex (learnability decreases) and generalization error increases. Figure 3 which shows the plots of learnability and generalizability of shallow 2-layer CNNs supports this hypothesis.

5. DISCUSSION AND CONCLUSION:

This paper explores the learnability of learned neural networks under various scenarios. The results herein suggest that while learnability is often higher than test accuracy, there is a strong correlation between low generalization error and high learnability of the learned neural networks. This paper also shows that there are some qualitative differences between shallow and popular deep neural networks. Some questions that this paper raises are the effect of optimization algorithms, hyperparameter selection and initialization schemes on learnability. On the theoretical front, it would be interesting to characterize neural networks that can be learned efficiently via backprop. Given the strong correlation between learnability and generalization, driving the network to converge to learnable networks might help achieve better generalization.

:



Figures and Tables:

second line of work shows, under various assumptions on D and/or N , that the learnability of neural networks is close to 1 Arora et al. (2014); Janzamin et al. (2015); Giryes et al. (2016); Zhong

any given example, let us denote TLP(x) def = 1 {N1(x)=y(x)} , where y(x) denotes the true label of x and PLP(x) def = 1 {N1(x)=N2(x)} . Tables

Figure 1: Shallow network with 1024 filters Figure 2: VGG11

Random images: Use random images and labels in Step 1, where each pixel in the image is drawn uniformly from[-1, 1].For this set of experiments architecture of N 1 was the same as that of N 2 . The networks N 1 and N 2 were varied over different architectures:VGG Simonyan & Zisserman (2014),GoogleNet Szegedy  et al. (2015), ResNetHe et al. (2016a), PreActResnetHe et al. (2016b)  ,DPN Chen et al. (2017)   and DenseNetHuang et al. (2016). We also do the same experiment on shallow convolutional neural networks with one convolutional layer and one fully connected layer. For the shallow networks, we vary the number of filters in N 1 and N 2 from {16, 32, 64, 128, 256, 512, 1024}. We start with 16 filters since that is the minimum number of filters where the training zero one error goes below 1%. The learnability values for various networks for true data, random labels and random images are presented in Table1for shallow convolutional networks, Table2for popular deep convolutional networks and Table3for shallow multilayer perceptrons (MLPs).

Table content: <table><tr><td colspan="3">Network Random Labels Random Images</td><td>True Data</td><td>True Data Acc.</td></tr><tr><td>16</td><td>21.57±0.66</td><td>14.19±1.01</td><td>58.81±0.4</td><td>53.91±0.56</td></tr><tr><td>32</td><td>22.07±0.34</td><td>16.13±0.44</td><td>68.32±0.3</td><td>58.67±0.41</td></tr><tr><td>64</td><td>28.98±0.38</td><td>22.91±0.65</td><td>73.04±.25</td><td>61.37±0.36</td></tr><tr><td>128</td><td>35.34±0.55</td><td>31.05±1.75</td><td>76.12±0.34</td><td>62.90±0.35</td></tr><tr><td>256</td><td>40.93±0.62</td><td>40.5±0.84</td><td>78.05±0.29</td><td>63.80±0.32</td></tr><tr><td>512</td><td>43.51±0.91</td><td>49.43±2.78</td><td>79.56±0.5</td><td>64.43±0.11</td></tr><tr><td>1024</td><td>46.49±1.15</td><td>52.06±0.29</td><td>80.41±.09</td><td>64.88±0.33</td></tr></table>

Learnability comparison of shallow networks on CIFAR-10 dataset with a batchsize of 64 averaged across five independent runs.

Table content: <table><tr><td>Network</td><td colspan="2">Random Labels Random Images</td><td>True Data</td><td>True Data Acc.</td></tr><tr><td>VGG11</td><td>17.99±0.34</td><td>11.30±0.15</td><td>73.47±0.63</td><td>72.93±0.36</td></tr><tr><td>VGG13</td><td>16.82±0.54</td><td>12.51±0.15</td><td>75.21±1.25</td><td>75.01±0.56</td></tr><tr><td>VGG16</td><td>17.88±0.49</td><td>11.97±0.34</td><td>75.41±0.77</td><td>75.78±0.60</td></tr><tr><td>VGG19</td><td>17.95±0.62</td><td>11.78±0.46</td><td>75.84±0.49</td><td>76.10±0.28</td></tr><tr><td>ResNet18</td><td>14.96±0.20</td><td>13.56±0.58</td><td>69.93±0.74</td><td>69.98±0.55</td></tr><tr><td>Resnet34</td><td>16.14±0.54</td><td>13.96±0.07</td><td>72.22±0.85</td><td>71.88±0.41</td></tr><tr><td>PreActResnet18</td><td>16.33 ±0.35</td><td>14.61±0.80</td><td>70.83±0.75</td><td>68.35±1.97</td></tr><tr><td>DPN26</td><td>17.03±0.30</td><td>12.61±0.05</td><td>70.36±0.70</td><td>69.84±0.27</td></tr><tr><td>DenseNet121</td><td>19.32±0.26</td><td>13.35±0.35</td><td>79.46±0.08</td><td>79.47±0.67</td></tr><tr><td>GoogleNet</td><td>16.10±0.55</td><td>13.77±0.02</td><td>78.55±1.26</td><td>78.58±0.31</td></tr></table>

Learnability comparison of popular neural network architectures on CIFAR 10 dataset with a batchsize of 64 averaged across five independent runs.

Table content: <table><tr><td colspan="3">Network Depth Random Labels Random Images</td><td>True Data</td><td>True Data Acc.</td></tr><tr><td>1</td><td>21.39±0.35</td><td>45.13±0.83</td><td>50.18±0.72</td><td>40.88±0.65</td></tr><tr><td>2</td><td>17.65±0.43</td><td>34.89±1.29</td><td>48.58±0.57</td><td>42.62±0.53</td></tr><tr><td>3</td><td>15.99±0.21</td><td>24.78±0.91</td><td>48.62±1.01</td><td>42.83±0.63</td></tr><tr><td>4</td><td>13.74±0.01</td><td>20.33±0.99</td><td>48.12±0.83</td><td>42.74±0.83</td></tr><tr><td>5</td><td>12.60±0.60</td><td>16.55±0.12</td><td>46.12±0.81</td><td>42.76±0.52</td></tr></table>

Learnability comparison of MLPs (Multi Layer Perceptrons)  of fixed hidden unit size 64 and varying depth on CIFAR-10 dataset with a batchsize of 64 averaged across five independent runs.We see from the results that the learnability values of neural networks learned using true data are much larger compared to the values for those learned using random labels or random images. This

Table content: <table><tr><td colspan="7">Network Random Labels Random Images</td><td>True Data</td><td colspan="3">True Data Acc.</td><td/></tr><tr><td>16</td><td/><td colspan="2">13.52±0.54</td><td colspan="2">8.98±0.59</td><td colspan="3">38.56±1.10</td><td colspan="2">26.13±0.36</td><td/></tr><tr><td>32</td><td/><td colspan="2">18.92±0.43</td><td colspan="2">16.93±0.90</td><td colspan="3">44.05±0.67</td><td colspan="2">28.89±0.43</td><td/></tr><tr><td>64</td><td/><td colspan="2">22.61±1.13</td><td colspan="2">25.74±0.72</td><td colspan="3">47.18±0.73</td><td colspan="2">30.32±0.18</td><td/></tr><tr><td>128</td><td/><td colspan="2">25.88±0.30</td><td colspan="2">34.34±2.27</td><td colspan="3">48.87±0.47</td><td colspan="2">30.71±0.18</td><td/></tr><tr><td>256</td><td/><td colspan="2">28.52±0.88</td><td colspan="2">43.27±2.15</td><td colspan="3">49.75±0.32</td><td colspan="2">31.39±0.13</td><td/></tr><tr><td>512</td><td/><td colspan="2">29.62±1.07</td><td colspan="2">47.45±2.04</td><td colspan="3">50.71±0.29</td><td colspan="2">31.68±0.19</td><td/></tr><tr><td>1024</td><td/><td colspan="2">30.57±1.05</td><td colspan="2">48.08±2.41</td><td colspan="3">51.06±0.26</td><td colspan="2">32.10±0.19</td><td/></tr><tr><td colspan="12">Table 4: Learnability comparison of shallow CNNs on CIFAR-100 dataset with a batchsize of 64</td></tr><tr><td colspan="4">averaged across five independent runs.</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>``````````Ǹ etwork Arch.</td><td>Class</td><td>0</td><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>8</td><td>9</td></tr><tr><td>True Data</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>GoogleNet</td><td/><td colspan="2">10.89 8.95</td><td>9.73</td><td colspan="3">8.88 12.29 9.04</td><td colspan="4">9.13 11.48 8.85 10.75</td></tr><tr><td>DenseNet</td><td/><td>9.19</td><td>9.27</td><td colspan="4">8.51 11.18 12.14 8.90</td><td colspan="3">6.35 16.54 9.28</td><td>8.65</td></tr><tr><td colspan="2">Shallow conv 1024</td><td colspan="2">10.45 9.45</td><td>9.14</td><td>9.08</td><td colspan="5">9.72 12.44 10.15 10.41 9.50</td><td>9.65</td></tr><tr><td colspan="2">Shallow conv 16</td><td colspan="2">11.78 9.67</td><td>9.44</td><td>9.48</td><td colspan="6">9.83 10.35 9.90 10.37 9.16 10.03</td></tr><tr><td colspan="2">Random Labels</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>DenseNet</td><td/><td colspan="10">10.17 8.24 11.54 6.84 11.11 10.81 10.70 9.17 11.01 10.42</td></tr><tr><td>GoogleNet</td><td/><td colspan="3">9.33 11.51 6.76</td><td colspan="7">9.71 12.82 9.20 10.32 7.08 10.70 12.57</td></tr><tr><td colspan="2">Shallow conv 1024</td><td colspan="8">11.86 10.05 13.93 10.07 9.79 12.69 14.60 4.88</td><td>4.94</td><td>7.19</td></tr><tr><td colspan="2">Shallow conv 16</td><td>8.86</td><td colspan="9">9.78 11.89 10.40 10.14 7.39 10.69 10.99 12.37 7.50</td></tr><tr><td colspan="2">Random Images</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td>DenseNet</td><td/><td>4.05</td><td>8.07</td><td>2.02</td><td>9.02</td><td colspan="6">0.49 17.59 0.75 17.85 37.46 2.70</td></tr><tr><td>GoogleNet</td><td/><td colspan="2">28.78 7.29</td><td>4.56</td><td>4.50</td><td colspan="4">1.13 12.12 21.79 8.45</td><td colspan="2">0.93 10.46</td></tr><tr><td colspan="2">Shallow conv 1024</td><td colspan="4">3.42 22.07 19.03 6.79</td><td>5.00</td><td>3.46</td><td>8.99</td><td>7.88</td><td colspan="2">4.19 19.17</td></tr><tr><td colspan="2">Shallow conv 16</td><td colspan="3">9.68 10.13 9.33</td><td>8.70</td><td colspan="5">8.52 11.76 12.01 11.91 8.69</td><td>9.28</td></tr></table>



Table content: <table/>

present the percentage of examples for the N

Table content: <table><tr><td>P TLP P P P 0 1</td><td>P P P PLP</td><td>0 11.68. 23.38 1 7.93 57.01</td><td>P P TLP P</td><td>P P PLP P P 0 1</td><td>0 25.84 19.83 1 15.29 39.04</td></tr></table>

N

Table content: <table><tr><td>P TLP P P P 0</td><td>P P P PLP</td><td>0 14.58. 12.93 1</td><td>P P TLP P</td><td>P P PLP P P 0</td><td>0 11.21 9.97 1</td></tr><tr><td>1</td><td/><td>11.94 60.55</td><td/><td>1</td><td>10.23 68.59</td></tr><tr><td colspan="3">Table 8: N 1 : VGG11 and N 2 : VGG11; in</td><td/><td/><td/></tr><tr><td>percentage</td><td/><td/><td/><td/><td/></tr></table>

N 1 : GoogleNet, N 2 : GoogleNet; in percentage four different possibilities of TLP and PLP for shallow networks while Tables

Table content: <table/>

Learnability values for shallow 2-layer CNNs of various sizes. Values in the first column represent the number of filters in N 1 and values in the header row represent the number of filters in N 2 .

Table content: <table><tr><td>P P P N 1</td><td colspan="3">P P P P N 2 # Params</td><td>Test Acc.</td><td>16</td><td>32</td><td>64</td><td>128</td><td>256</td><td>512</td><td>1024</td></tr><tr><td colspan="2">16</td><td/><td>42186</td><td colspan="7">53.91±0.56 58.81±0.40 61.61±0.49 63.78±0.54 65.09±0.24 65.08±0.21 65.12±0.19 63.94±0.73</td></tr><tr><td colspan="2">32</td><td/><td>84362</td><td colspan="7">58.67±0.41 63.86±0.06 68.32±0.30 69.25±0.88 70.00±1.23 70.03±0.62 71.14±0.22 70.44±0.66</td></tr><tr><td colspan="2">64</td><td/><td>168714</td><td colspan="7">61.37±0.36 67.60±0.04 71.37±0.58 73.04±0.25 74.48±0.05 73.80±0.19 74.92±0.36 74.04±0.01</td></tr><tr><td colspan="3">128</td><td>337418</td><td colspan="7">62.90±0.35 68.80±0.11 73.52±0.38 75.04±0.10 76.12±0.34 76.73±0.27 76.60±0.14 76.89±0.09</td></tr><tr><td colspan="3">256</td><td>674826</td><td colspan="7">63.80±0.32 70.63±0.08 74.53±0.22 77.53±0.10 77.61±0.04 78.05±0.29 78.10±0.01 77.56±0.68</td></tr><tr><td colspan="3">512</td><td colspan="8">1349642 64.43±0.11 71.69±0.05 76.23±0.28 77.15±0.05 78.07±0.06 79.43±0.06 79.56±0.50 78.96±0.02</td></tr><tr><td colspan="3">1024</td><td colspan="8">2701910 64.88±0.33 71.85±0.43 76.45±0.37 78.01±0.32 79.19±0.38 79.36±0.31 79.90±0.19 80.41±0.09</td></tr><tr><td colspan="2">P P P N 1</td><td>P</td><td colspan="3">P P P N 2 # Params Test Accuracy</td><td>1</td><td/><td>2</td><td>3</td><td>4</td><td>5</td></tr><tr><td/><td/><td>1</td><td colspan="2">197322</td><td>40.88±0.65</td><td colspan="5">50.18±0.72 48.85±1.02 48.38±0.32 48.04±0.39 48.04±0.04</td></tr><tr><td/><td/><td>2</td><td colspan="2">201482</td><td>42.62±0.53</td><td colspan="5">48.48±0.10 48.58±0.57 50.03±0.43 48.96±0.33 47.80±1.11</td></tr><tr><td/><td/><td>3</td><td colspan="2">205642</td><td>42.83±0.63</td><td colspan="5">48.06±0.30 48.09±0.19 48.62±1.01 48.39±1.14 47.45±0.24</td></tr><tr><td/><td/><td>4</td><td colspan="2">209802</td><td>42.74±0.83</td><td colspan="5">46.35±0.41 46.89±0.76 48.32±0.95 48.12±0.83 46.40±0.12</td></tr><tr><td/><td/><td>5</td><td colspan="2">213962</td><td>42.76±0.52</td><td colspan="5">44.96±0.92 46.14±0.92 46.62±0.57 46.25±0.61 46.12±0.81</td></tr></table>

Learnability values for shallow MLPs of various sizes. Values in the first column represent the depth ofN 1 and values in the header row represent the depth of N 2 . Each MLP layer had a hidden unit size of 64 followed by a ReLU

Table content: <table><tr><td colspan="3">P P P P N 1 DPN26 P P N 2 # of Layers, Params Test Accuracy P 89-11574842 69.84±0.27</td><td colspan="2">VGG11 68.54±0.97 69.84±0.89 72.33±0.52 ResNet18 GoogLeNet DenseNet121 72.47±0.15</td></tr><tr><td>ResNet18</td><td>62-11173962</td><td>69.98±0.55</td><td>68.79±0.68 69.94±0.55 71.76±0.24</td><td>73.33±0.29</td></tr><tr><td>ResNet34</td><td>110-21282122</td><td>71.88±0.41</td><td>71.51±0.41 71.14±0.01 72.22±0.69</td><td>73.86±0.09</td></tr><tr><td>VGG11</td><td>34-9231114</td><td>72.93±0.36</td><td>73.47±0.39 69.46±0.57 72.39±0.11</td><td>73.42±0.03</td></tr><tr><td>VGG13</td><td>42-9416010</td><td>75.01±0.56</td><td>74.87±0.67 70.83±0.08 73.84±0.83</td><td>74.65±0.01</td></tr><tr><td>VGG16</td><td>54-14728266</td><td>75.78±0.60</td><td>74.23±1.04 72.28±0.14 74.40±0.66</td><td>74.76±0.39</td></tr><tr><td>VGG19</td><td>66-20040522</td><td>76.10±0.28</td><td>74.66±0.10 71.84±0.15 74.29±0.93</td><td>76.75±0.12</td></tr><tr><td>GoogLeNet</td><td>258-6166250</td><td>78.58±0.31</td><td>70.75±0.18 71.24±1.55 78.55±1.58</td><td>77.74±0.05</td></tr><tr><td>DenseNet121</td><td>362-6956298</td><td>79.47±0.67</td><td>73.41±0.37 73.95±0.56 78.61±0.01</td><td>79.46±0.01</td></tr></table>

Learnability values for various popular architectures. The first column gives the architecture of N 1 and the header row shows the architecture of N 2 . See text for discussion.

Table content: <table><tr><td>``````````Ǹ 1 /N 2</td><td>Batch size</td><td>32</td><td>64</td><td>128</td><td>256</td></tr><tr><td/><td>VGG11</td><td colspan="4">74.56 ±0.71 73.75 ±0.07 72.05 ±0.83 69.10 ±0.53</td></tr><tr><td/><td>VGG13</td><td colspan="4">74.85 ±0.43 73.95 ±1.13 73.32 ±0.23 69.84 ±0.29</td></tr><tr><td/><td>VGG16</td><td colspan="4">74.87 ±0.60 74.73 ±0.44 73.14 ±0.25 69.88 ±0.32</td></tr><tr><td/><td>VGG19</td><td colspan="4">74.44 ±0.40 74.38 ±0.03 73.03 ±0.15 70.74 ±0.52</td></tr><tr><td/><td>ResNet18</td><td colspan="4">72.51 ±0.87 70.06 ±0.45 64.98 ±0.17 61.72 ±0.64</td></tr><tr><td colspan="2">DenseNet121</td><td colspan="2">73.79 ±0.25 73.33 ±0.06</td><td>-</td><td>-</td></tr><tr><td colspan="2">GoogleNet</td><td colspan="2">72.01 ±0.25 71.55 ±0.54</td><td>-</td><td>-</td></tr></table>

Learnability comparison of network architectures on CIFAR-10 dataset with varying batch sizes. For this experiment we fixed N2 to be VGG11 with batch size of 64. GoogleNet and DenseNet architectures ran out of memory for batch size of 128 and 256.

Table content: <table><tr><td></td><td>1.</td><td>0.93 0.93 0.93 0.93</td><td></td><td></td><td>1. 0.73 0.73 0.73 0.72</td><td></td></tr><tr><td colspan="3">    0.93 1. 0.93 0.94 0.94 0.93 0.93 1. 0.93 0.94 0.93 0.94 0.93 1. 0.93</td><td>   </td><td colspan="2">    0.73 1. 0.74 0.73 0.74 0.73 0.74 1. 0.74 0.75 0.73 0.73 0.74 1. 0.74</td><td>   </td></tr><tr><td colspan="3">0.93 0.94 0.94 0.93 1.</td><td/><td colspan="2">0.72 0.74 0.75 0.74 1.</td><td/></tr></table>

Peer review (iclr2018):
 Summary: This paper presents very nice experiments comparing the complexity of various different neural networks using the notion of "learnability" --- the learnability of a model (N1) is defined as the "expected agreement" between the output of N1, and the output of another model N2 which has been trained to match N1 (on a dataset of size n). The paper suggests that the learnability of a model is a good measure of how simple the function learned by that model is --- furthermore, it shows that this notion of learnability correlates well (across extensive experiments) with the test accuracy of the model. The paper presents a number of interesting results: 1) Larger networks are typically more learnable than smaller ones (typically we think of larger networks as being MORE complicated than smaller networks -- this result suggests that in an important sense, large networks are simpler). 2) Networks trained with random data are significantly less learnable than networks trained on real data. 3) Networks trained on small mini-batches (larger variance SGD updates) are more learnable than those trained on large minibatches. These results are in line with several of the observations made by Zhang et al (2017), which showed that neural networks are able to both (a) fit random data, and (b) generalize well; these results at first seem to run counter to the ideas from statistical learning theory that models with high capacity (VC dimension, radamacher complexity, etc.) have much weaker generalization guarantees than lower capacity models. These results suggest that models that have high capacity (by one definition) are also capable of being simple (by another definition). These results nicely complement the work which studies the "sharpness/curvature" of the local minima found by neural networks, which argue that the minima which generalize better are those with lower curvature. Review: Quality: I found this to be high quality work. The paper presents many results across a variety of network architectures. One area for improvement is presenting results on larger datasets (currently all experiments are on CIFAR-10), and/or on non-convolutional architectures. Additionally, a discussion of why learnabiblity might imply low generalization error would have been interesting (the more formal, the better), though it is unclear how difficult this would be. Clarity: The paper is written clearly. A small point: Step 2 in section 3.1 should specify that argmax of N1(D2) is used to generate labels for the training of the second network. Also, what dataset D_i is used for tables 3-6? Please specify. Originality: The specific questions tackled in this paper are original (learnability on random vs. real data, large vs. small networks, and large vs. small mini-batch training). But it is unclear to me exactly how original this use of "learnability" is in evaluating how simple a model is. It seems to me that this particular use of "learnability" is original, even though PAC learnability was defined a while ago. Significance: I find the results in this paper to be quite significant, and to provide a new way of understanding why deep neural networks generalize. I believe it is important to find new ways of formally defining the "simplicity/capacity" of a model, such that "simpler" models can be proven to have smaller generalization gap (between train and test error) relative to more "complicated" models. It is clear that VC dimension and radamacher complexity alone are not enough to explain the generalization performance of neural networks, and that neural networks with high capacity by these definitions are likely "simple" by other definitions (as we have seen in this paper). This paper makes an important contribution to this conversation, and could perhaps provide a starting point for theoreticians to better explain why deep networks generalize well. Pros - nice experiments, with very interesting results. - Helps explain one way in which large networks are in fact "simple" Cons - The paper does not attempt to relate the notion of learnability to that of generalization performance. All it says is that these two metrics appear to be well correlated.