Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper proposes a bootstrap framework to study the generalization problem of deep learning, by decomposing the traditional test error into an ‘Ideal World’ test error plus the gap between. Empirically, it demonstrates that such gap (soft-error) is small in supervised image classification for typical deep learning model architectures. It then proposes to explain several phenomena in deep learning using the bootstrap framework. I appreciate the authors' efforts on conducting extensive experiments related to deep learning generalization.

Pros:

+ The proposed decomposition of test error is new to the field.

+ The presented experiments are extensive, which connected to various important aspects in deep learning. 


Cons:

- My main concern is that the motivation of the proposed bootstrap framework is unclear. I have a hard time understanding how the proposed framework overcomes the two major obstacles of classical approaches listed in the introduction section. Why are the subproblems presented in (2) easier than the original one? 

- Classical generalization bounds (although can be vacuous in some scenarios) are mostly theoretically-derived, which are able to characterize the dependencies of the error term on parameters, such as input dimension, sample size and model class complexities. However, the main claim of the paper (claim 1 in Page 3) is a pure experimental claim. The paper will be much stronger, if claim 1 can be characterized theoretically with bounds on the error term (even in a simplified setting).

- The implications of the proposed framework and results on how to improve the existing deep learning methods are not clear to me. Assuming the bootstrap error is always small, then how can one modify the current deep learning training method to reduce the ‘Ideal World’ test error? 

- Characterizing the ‘Ideal World’ test error requires a significant large amount of labeled inputs for supervised image classifications. The paper construct synthetic datasets by first generating images using an unconditional generative model, then labeling the images using a pretrained classification model. How do you guarantee the label quality for the whole generated dataset? Why not directly use a conditional generative model?

Minor Comments:

1. The mathematical definitions of test error and test soft error are not provided. I would recommend the authors to lay out these metrics in the main body of the paper to add clarity.


===== Post-Discussion Update =====

I appreciate the authors' efforts for responding my concerns and comments. The provided response and the update of the introduction do help better explain the motivations and the implications of the proposed generalization framework. Therefore, I raise my previous rating a little bit to reflect this. 

Although the proposed framework may suggests a potentially-interesting future direction for the deep learning research community, it still does not fully convince me its feasibility. In particular, the paper would be much stronger, if the author can dig deeper with the Real-World test (soft) error, which I view it as the end-goal of a real-world classification system, to provide more specific directions on how to make it smaller, or more importantly, how it changes the current deep learning training paradigm.
review_title: New Framework, but Not Good Enough

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper defines a metric of generalization gap between the ideal world and real-world via 'bootstrap approximation', and seeks to use his gap to explain some phenomena.

Although I have respect for this paper trying to define some statistical terms in the deep learning society, I have a very strong concern about the novelty, as it appears to be whether trivial or hard to understand. For example, I could relate to the empirical finding that bootstrap error defined in claim 1 is uniformly small, but I personally believe that the 'TestSoftError' defined in 3 should dominate the generalization error and the paper circumvents this term to study some term that is way non-significant, especially considering how the datasets are built around CIFAR or DOG-bird, via simple data augmentation that is frequently used in vision society. The problem being mentioned in the paper, i.e. 'Most if not all techniques for understanding the generalization gap (e.g. uniform convergence, VC-dimension, regularization, stability, margins) remain vacuous', appears to be not tackled at all in this paper, which, in its main effort, to discuss generalization.

Section 5 says some practical suggestions to train deep networks, which seem to be not persuasive, especially that the ideal world error might be harder to measure than that in the real world, according to the paper. On top of this, why these factors such as sample size, model selection, are not to be tuned even better if that were through the lens of other metrics, such as gradient norms, validation error, etc.
review_title: a concern about the novelty and practicality of the proposed generalization gap framework

final_score: rating: 6: Marginally above acceptance threshold
review_content: ######################################################################

1.  Paper Summary 

The authors propose a bootstrap framework for understanding generalization in deep learning.  In particular, instead of the usual decomposition of test error as training error plus the generalization gap, the bootstrap framework decomposes the empirical test error as online error plus the bootstrap error (the gap between the population and empirical error).  The authors then demonstrate empirically on variants of CIFAR10 and a subset of ImageNet that the bootstrap error is small on several common architectures.  Hence, the empirical test error is controlled by the online error (i.e. a rapid decrease in the error in the online setting leads to low test error).  The authors then provide empirical evidence to demonstrate that same techniques perform well in both over and under-parameterized regimes.  

######################################################################

2. Strengths

2.1. The bootstrap framework presented for understanding generalization is novel to the best of my knowledge and provides an interesting connection between optimization in online learning and generalization in offline learning.  

2.2. When the bootstrap error is low, the bootstrap framework implies that understanding generalization reduces to understanding optimization in the online setting.  This perspective provides an alternative to characterizing the implicit bias of deep networks when explaining generalization in deep networks.  

2.3. The authors present significant empirical evidence that the bootstrap error (in terms of soft error) is consistently low in image classification settings across a number of architectures.   

######################################################################


3. Concerns

3.1. While at first this framework serves as a very appealing alternative to the classical decomposition, the fact that the bootstrap error is low seems heavily reliant on the soft-error only found in the classification networks using a softmax on the outputs.  In particular, the authors focus on the soft-error in their decomposition throughout the work, but in Appendix A and in section 6, it appears that the MSE/cross entropy loss produce a significant bootstrap gap.  At first, this may seem innocuous, but if this bootstrap gap is low only for soft error, this would imply that we need to then focus on understanding how quickly the population soft error decreases, which to the best of my knowledge is a very different object of study in optimization than the MSE or cross entropy loss.  

3.2.  In light of the previous point, I feel that the following experiment could help solidify whether the bootstrap error is indeed low for convolutional networks used for classification. When using the square loss for classification as is done in (https://arxiv.org/abs/2006.07322) (for example on the CIFAR10 setting), is the bootstrap error still low or is the bootstrap error being low really only a side effect of measuring soft-error? This experiment should resolve the authors' claim with the gap in Figure 6c being large due to unbounded weights when minimizing the empirical loss.  

3.3. (Minor) I have a hard time understanding how strong some of the claims are in the paper.  In particular, the authors claim a main implication as "The same techniques [...] are used in practice in both over- and under-parameterized regimes."  Do the authors mean to claim that a technique that is successful in the over-parameterized regime is also successful in the under-parameterized regime? They do state this in briefly on page 6, but it seems to be claimed less strongly in the introduction.  Additionally, in light of the fact that there are cases where the bootstrap error is high, the claim that "the generalization of models in offline learning is largely determined by their optimization speed in online learning" may need to be more precise.

######################################################################

4. Score and Rationale

Overall, I currently vote for rejecting. However, my decision is borderline.  In particular, while I find the authors' bootstrap framework appealing in that it could nicely connect generalization and optimization, I am concerned about the results relying heavily on the soft-error (especially since the softmax activation is not necessary for deep networks to perform well on test data).  I am definitely open to changing my review provided that the authors are able to address my concerns about the soft-error above.  

######################################################################


5. Questions 

Please clarify the questions listed in the concerns section above.  

######################################################################

6. Post-rebuttal Updates

In light of the authors new experiments and response, I have increased my score.  The bootstrap error shows slight deviations under the MSE, and thus, I do feel that the scope of generality of this work is still limited.  However, I feel that the presented framework is novel and the experiments consistently demonstrate that the bootstrap error is consistently low under soft-error in a number of settings.  
review_title: Interesting framework but there appear to be some caveats 

final_score: rating: 7: Good paper, accept
review_content: This paper studies generalization through a novel "bootstrap" framework relating the test loss from training on a finite fixed training set to the loss when training on fresh samples at each iteration. The framework is quite novel and suggests alternative perspectives on understanding empirical phenomena such as the success of overparametrization, data augmentation, and implicit biases. 

Positives:
- The paper is clearly written
- The empirical bootstrap phenomenon is very interesting and the experimental results are quite surprising.

Cons:
- The paper could benefit from some more prominent discussion of settings where the bootstrap error is small vs large. It was briefly mentioned in this sentence in the conclusion: " The bootstrap error is not universally small for all models and
learning tasks: for example, we found the gap was larger at limited sample sizes and without data
augmentation. " Space permitting, it would be helpful and more convincing if more details were provided about settings where the bootstrap error could be large. 
- The choice of soft error to compute the bootstrap error seems somewhat ad-hoc, especially for the datasets studied where the Bayes optimal risk is presumably quite low. For example, it seems like ImageNet-DogBird should be quite easy to separate unambiguously. 

Some other comments and questions: 
- It would be interesting to hear the authors thoughts on the feasibility of rigorously analyzing the bootstrap error. Are there any obstacles to analyzing this error that arise in the prior literature? 
review_title: Interesting empirical phenomenon

Meta-review: The paper is proposing a new framework for understanding generalization in the deep learning. The main idea is considering the difference of stochastic optimization on a population risk and optimization on an empirical risk. The classical theory considers the difference of empirical risk and population risk. This basically translates the practical motivation from finding good function classes to finding good optimizers which can re-use the data effectively. Although the paper provides no theoretical result, it provides an interesting empirical study. The paper somewhat demonstrates that SGD on deep networks is somehow good at re-using the same data. I believe this angle is very novel and might hope to future theoretical discoveries. The paper is reviewed by four reviewers and two of them argue its acceptance and two of them argue rejection. After discussion, this status remained and I carefully read and reviewed the paper. Here are the major issues raised by the reviewers:

- R#1: The paper is missing a theoretical study. The implications on the practical deep learning is not clear.
- R#2: Choice of the soft-error is particular to the task and how to go beyond soft-max is not clear.
- R#3: Finds the paper not novel as well as trivial or hard to understand.
- R#4: The choice of soft error is ad-hoc.

I believe the issues raised by R#3 are not justified. First of all, novelty is very clear and. appreciated by other reviewers. Moreover, the paper is rather easy to understand and the results are very farm from trivial. However, the other issues raised by other reviewers are valid. Specifically, soft-error seems to be a limitation of the study. However, the authors respond to this concern and reviewer increases their score. I believe the theory is lacking but the paper is simply showing this novel approach and its empirical validity. A theory to explain this phenomenon would be amazing but not necessary for publication. Similarly, without a theory it is hard to expect any practical implication. Overall, I believe the paper is an interesting and novel one which will likely to lead additional work in the area. Considering we are still far from a satisfying theory of generalization for deep learning and the role of the optimization is clear, this angle worth sharing with the community. Hence, I decide to accept. However, I have some concerns which should be addressed by the camera-ready. 

- Claims should be revised and authors should make sure they have enough evidence for them. For example, authors provide no satisfying evidence for random labels or very limited evidence for pre-training. I strongly recommend authors to either remove some of these discussions or present in a fashion which is not a result but part of the discussion for future research.
- A section about limitations should be added. Specifically, the soft-error choice should be discussed in this limitation section.
- Discussion section should be extended with the pointers to the relevant work on bootstrap literature as well as suggestions to the theoreticians. Not providing any theoretical result is always fine but authors should understanding why is it hard to make theoretical statements and where to search them.
Decision: Accept (Poster)