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.
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.