Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provides an upper boundary of the generalization error of networks: the sum of its training error, the distillation error, and the complexity of the distilled network. Then, it also provides an instantiation of the lemma applicable to residual networks, an explicit compression analysis via pruning with a corresponding generalization bound, and empirical supports.

**Pros**

* The idea of applying distillation to tackle the generalization dilemma seems interesting, and the proof seems rigorous.
* Experiments in section 2 on the width independence, depth, and random label are reasonable for me.

**Cons**

* A comparison (e.g. on the tightness of the bound, or the correlation with generalization) between the proposed distillation-based generalization bound and existing generalization bounds in literature may help demonstrating the effectiveness of the proposed bound.
review_title: An interesting theoretical study on the generalization bound, while comparison between existing bounds may make it more convincing

final_score: rating: 6: Marginally above acceptance threshold
review_content: The generalization performance of learning algorithms characterizes their ability to generalize their empirical behavior on training examples to unseen test data, which provides an intuitive understanding of how different parameters affect the learning performance and some guides to design learning machines. Different from the traditional error analysis, this paper focuses on bounding the divergence bettween the test error and the training error by the the corresponding distillation error and distillation complexity, e.g., test error  is bounded by training error + distillation error + distillation complexity. The current learning theory analysis may be important to understand the theoretical foundations of distillation strategy in deep networks. However, some theoretical issues should be illustrated to improve its readability, e.g,. 
1)What is the relation between the original network complexity and the corresponding distillation error +distillation complexity? 
2)Is the derived upper bound (e.g., Theorem 1.2) tighter than the traditional one? Please present a table to compare it with  the related error bounds.
3)What are necessary/sufficient theoretical conditions for the effectiveness of distillation strategy (from the generalization error bounds)?
4)It may be better to state some discussions for the lower bound on the generalization error. Does it also relate with distillation complexity?  

review_title: some comments

final_score: rating: 7: Good paper, accept
review_content: The paper overall is of good quality. The story of the work is well-written which makes the contributions easier to digest. One suggestion would be to comment a bit more on the relevance of the margin distribution for readers that are unfamiliar with it, for instance, in Figure 1, the term margin distribution is thrown without explaining why one should look into it. 

The topic of this work is of great significance given that understanding the generalization error of neural nets is relevant to the community.

In terms of theoretical contributions, the results seem sound although I did not check the proofs in much detail. Most of the proofs are based on known techniques to find upper bounds. Authors also show some experiments on the behavior of their bounds, and in particular, on margin distributions.

Overall, I like the idea of bounding complex models by distilled models (simpler ones), and as authors point out, to make this approach work one needs to have a solid way to find such distilled models. If my understanding is correct, the "weak" part of the work is that authors do rely on sparsification to find distilled models. While valid, my intuition is that such distillation process could still lead to large bounds. Which seem to be the case of Figure 3(b)? 
To give an example, consider a task where an overparametrized complex network generalizes well in practice, it seems unlikely to me that a (very) sparse or pruned network would "perform similarly". That is, the "sparsified" model to be "close in performance" to the complex model would not be simple enough to give a non-vacuous upper bound. I would appreciate if authors can comment on this concern.


review_title: Good paper

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper provides generalization bounds for seemingly complex neural networks
on the basis of much simpler ones. That is a good idea and something that is currently very relevant I think and the approach seems to be the natural one to take. 

Essentially the bounds proved, bound the out of sample error
with a form of in sample error, average difference in predictions between complex and simple network, and complexity term for the simple network in terms of Rademacher complexity. 

The authors provide a general framework which can be applied and show a particular way of using it and use recent results (Bartlett et al) to provide interesting application of the framework.


In terms of the actual bound achieved there are a few things I feel should be discussed more.

In Lemma 1.1.
The in-sample error. First it is not the in-sample classification error but the sort of a margin error that essentially is never zero for any prediction. Usually margin errors have a
linear penalty on the wrong side of the margin and zero on the correct side of the margin.
Second, there is a factor 2 in front of it. Normally, and in uniform convergence bounds, there are no constants in front of the in-sample error. (The other constants are of no concern).

The authors state that their work can be applied to  generalization bound of Arora et a. 18 that only worked for a compressed network but not the original one. Given the above comments about the actual bound achievable it is not clear to me what exactly one would get out of "distilling" the construction in Arora et al, but it seems it does not become the same bound as for the compressed network as shown by Arora et al. Comments on that would be appreciated.

Another small question: What does the early distillation phase on page 4 means (below lemma 1.3)?


I like the experimental setup, particularly using gradient descent to try and find a network to distill to.

Overall, I think the paper is well written including the proof sketches that make me believe the statements are actually provable (I did not rigorously check)

Overall, I think this is an interesting paper and should be accepted. 


review_title: Interesting approach to generalization bounds for deep neural networks. 

Meta-review: This paper provides a novel generalization bound for neural networks using knowledge distillation. In particular, they argue that

"test error <= training error + distillation error + distillation complexity" where the distillation complexity is typically much smaller than the original complexity of the neural network. This is motivated by the empirical findings that neural networks can typically be significantly compressed in practice using KD without losing too much accuracy. 


I found this result novel and the direction is very promising. This is a clear accept for ICLR. 
Decision: Accept (Spotlight)