Venue: ICLR 2018 conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: Review Summary:
The primary claim that there is "a strong correlation between small generalization errors and high learnability" is correct and supported by evidence, but it doesn't provide much insight for the questions posed at the beginning of the paper or for a general better understanding of theoretical deep learning. In fact the relationship between test accuracy and learnability seems quite obvious, which unfortunately undermines the usefulness of the learnability metric which is used in many experiments in the paper.

For example, consider the results in Table 7. A small network (N1 = 16 neurons) with low test accuracy results in a low learnability, while a large network (N1 = 1024 neurons) gets a higher test accuracy and higher learnability. In this case, the small network can be thought of as applying higher label noise relative to the larger network. Thus it is expected that agreement between N1 and N2 (learnability) will be higher for the larger network, as the predictions of N1 are less noisy. More importantly, this relationship between test accuracy and learnability doesn't answer the original question Q2 posed: "Do larger neural networks learn simpler patterns compared to neural networks when trained on real data". It instead draws some obvious conclusions about noisy labeling of training data.

Other results presented in the paper are puzzling and require further experimentation and discussion, such as the trend that the learnability of shallow networks on random data is much higher than 10%, as discussed at the bottom of page 4. The authors provide some possible reasoning, stating that this strange effect could be due to class imbalance, but it isn't convincing enough.

Other comments:
-Section 3.4 is unrelated to the primary arguments of the paper and seems like a filler.
-Equations should have equation numbers
-Learnability numbers reported in all tables should be between 0-1 per the definition on page 3
-As suggested in the final sentence of the discussion, it would be nice if conclusions drawn from the learnability experiments done in this paper were applied to the design new networks which better generalize
review_title: The paper poses interesting questions, but learnability doesn't provide many answers

final_score: rating: 6: Marginally above acceptance threshold
review_content: The proposed approach to figure out what do deep network learn is interesting -- the approach of learning a learned network. Some aspects needs more work to improve the work. The presentation of the results can be improved further. 

Firstly, confidence intervals on many experiments are missing (including Tables 3-9). Also, since we are looking at empirically validating the learnability criterion defined by the authors, all the results (the reported confusion tables) need to be tested statistically (to see whether one dominates the other). 

What is random label learning of N1 telling us? How different would that be in terms of simply learning random labels on real data directly. Further, the evaluations in Tables 3-6 need more attention since we are interested in the TLP=1 vs. PLP=0 case, and TLP=0 vs. PLP=1 case. 

The influence of depth is not clear -- may be it is because of the way results are reported here. A simple figure with increasing layers vs. learnability values would do a better job at conveying the trends. 

The evaluations in Section 3.5 are not conclusive? What is the question being tested for here? 

What about the influence of number of classes on learnability trends? Some experiments on large class datasets including cifar100 and/or imagenet need to be reported. 

--- Comments after response from authors --- 

The authors have clarified and shown results for several of the issues I was concerned about. Although it is still unclear what the learnability model is capturing for deeper model or the trends in Section 3.5 (looks like the trends may relate to stability of SGD as well here) -- the proposed ideas are worth discussing. I have appropriately modified my rating. 


review_title: This is an interesting empirical attempt at understanding the reproducibility of learned neural networks. Great ideas but needs more work.

final_score: rating: 7: Good paper, accept
review_content: 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.
review_title: Very nice paper showing how large networks can actually be "simple", in spite of their large capacity.

Meta-review:  + The paper proposes an interesting empirical measure of ""learnability"" of a trained network: how well the predictive function it represents can be learned by another network. And shows it empirically seems to correlate with better generalization.
 - The work is purely empirical: it features no theory relating this learnability to generalization
 - Learnability measure is somewhat ad-hoc with moving parts left to be specified (learning network, data splits, ...)
 - as pointed out by a reviewer, learnability doesn't really provide any answers for now.
 - the work would be much stronger if it went beyond a mere correlation study, and if learnability considerations allowed to derive a new approach/regularization scheme that was convincingly shown to improve generalization.

Decision: Reject