Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper argues that, contrary to a common belief, the "double descent" effect can be fully explained by classical VC-generalization bounds. The paper argues that this requires a proper form and interpretation of the bounds, which are discussed at length. The authors then perform an empirical study of several models on the MNIST data in which the VC bound curve can be plotted and shown to describe double descent. 

strength_and_weaknesses: Strengths
-------------
The main strength of the paper is that it makes a clear point challenging a common belief, and consistently argues in favor of this point. The paper is quite thoughtfully written. The conceptual problem addressed - practically deriving the complex dependence of model performance on model complexity and sample size - is important and hard. The experimental demonstrations in the case of shallow networks look convincing to me. I think the paper has a definite methodological value and can be useful to the readers.

Weaknesses
----------------
The main weakness that I see is that the main claim of the paper, that theoretical VC bounds can be used to describe double descent, is essentially only demonstrated for shallow models or in effectively shallow settings, when it is not that interesting because there are now other analytical methods applicable in these settings that can often provide more detailed information (e.g., explicit solutions based on random matrix theory). 
Also, I'm not an expert in statistical learning theory, and it's hard for me to judge, but the paper contains no new technical results; its novelty seems to be limited to interpreting old VC bounds and performing an empirical study in a new context. The key idea on which the discussion of double descent rests in the paper is that VC dimension is primarily determined by the number of parameters in the underparameterized regime but rather by the weight norm in the overparameterized regime. In some form, this or closely related ideas seem to have already been around for a while in recent works on double descent (and are in a sense already present in bound (3)). However, this does not mean that I doubt the novelty of specific details of theoretical analysis and experimental setup in the present paper.




clarity,_quality,_novelty_and_reproducibility: The paper is generally quite well written.

I'm not familiar with the VC bounds in the form (1), (3) playing a central role in the paper, and the paper only vaguely refers to the books of Vapnik and Cherkassky & Mulier as the sources. It would be helpful to see more specific references or maybe an appendix with exact formulations of relevant theorems.

summary_of_the_review: A solid well-written paper offering a comprehensive discussion of the very important topic of explaining double descent and related effects via classical VC dimension theory. However, I'm not fully convinced in the significance of the results, due to a lack of any analytical novelty and a relatively limited scope of demonstrated applications.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper aims to provide an explanation of double descent using classical VC theory. The primary argument is that since the test error can be bounded by a function involving both the training error and the VC dimension, one may observe double descent if one minimizes the training error and then “minimizes the VC dimension” subject to having a small training error (e.g. zero). The authors argue that this explains double descent in modern neural networks. They conduct experiments in simple settings (mostly linear classification) to support their argument. 

strength_and_weaknesses: The goal of the paper is certainly commendable; revisiting classical ideas may shed insights into recent empirical observations. 

However, I don’t think that the authors apply VC theory correctly in their argument. First, it is important to keep in mind that one does *not* minimize a VC dimension because the VC dimension is a property of the hypothesis space that you consider during training. The only valid way to reduce the VC dimension is to change the hypothesis space *from the outset*, not during training. It seems that the authors allude to structural risk minimization (SRM), but SRM is different. In SRM, one has a nested set of hypothesis spaces and learning proceeds from the smallest to the largest hypothesis spaces. In this case, the VC dimension is the VC dimension of the largest set ever considered. Note that all hypotheses outside of the last set in SRM are *never* considered during training. In the arguments the authors make, one starts with a complex hypothesis space and then try to reduce it by picking a smaller set if any. This is not a correct application of VC theory.

Second, while authors focus on linear classification, the extension of their argument to deeper architectures is based on an unsupported hypothesis without any proof. The authors hypothesize that one can treat a deep neural network as a linear classifier on the pre-logit features and then proceed by stating that the norm of the weights on the classifier’s head gives a measure of generalization. One problem with this argument is that when using activations like ReLU, we can always rescale the weights of the early layers and decrease the norm of the weights of the classifier head without changing the decision boundary. That's why in norm-based generalization bounds, such as in [1, 2, 3, 4], it is the *product* of the norms of all layers that count. In addition, since the product itself can be increased or decreased arbitrarily without changing the decision boundary, generalization bounds almost always normalize the product of the norms of the layers by the *margin* on the training examples.

Third, the VC dimension is independent of the distribution of the data. If there is a claim that neural networks have a small VC dimension, then neural networks should generalize across *all* data distributions including those with random labels. But, clearly that’s not the case.

[1] Bartlett, P. L. The sample complexity of pattern classification with neural networks: the size of the weights is more
important than the size of the network. IEEE Transactions on Information Theory, 44(2): 525–536, 1998.

[2] Bartlett, P. L.; Foster, D. J.; and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. NeurIPS, 2017

[3] Arora, S.; Ge, R.; Neyshabur, B.; and Zhang, Y.  Stronger generalization bounds for deep nets via a compression approach. ICML, 2018.

[4] Neyshabur, B.; Tomioka, R.; and Srebro, N. Normbased capacity control in neural networks. COLT, 2015.

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and the experiments are described enough to be reproducible. 
summary_of_the_review: I do not believe VC theory is applied correctly in this paper. Also, the main hypothesis that the authors postulate for deep neural networks is not valid in my opinion since one can rescale the weights in the early layers and reduce the norm of the weights at the last layer without changing the decision boundary.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This article makes the case that the double descent phenomenon in overparameterized neural networks and random feature models can be explained by considering the VC-dimension of spaces of such functions with L_2-bounded final layer weights. Moreover, the authors claim that this point has been missed in the existing literature.
strength_and_weaknesses: Strengths:

- The paper is well-written and clearly makes a simple point regarding VC-dimension of neural networks and random feature models with L_2-bounded final layer weights

- I agree with the authors that in some prior literature there are overly strong statements about how the extent to which VC-dimension bounds are useful in the overparameterized regime. So it is a valuable message to push back again this point of view to some extent.

Weaknesses:
- The main point raised in this paper: namely that VC dimension with norm bounds on network weights can explain generalization in deep networks is not new. In my view, before this article can be published, it is imperative that a thorough review of and comparison with prior literature is undertaken. Once this is done, I am not certain whether there will be anything truly novel about the article under consideration. A short list of some relevant prior articles includes:
    - Bartlett’s paper [1] that is among the earliest works directly about one hidden layer neural networks with bounds on the norm of the weights in second layer the giving rise to VC-dimension bounds. This article has over 1700 citations. 
    - Neyshabur et. al.’s work [2]. They consider in Theorems 1 and 2 rademacher complexity neural networks with bounds on the distance weights changed from initialization. They also review in Table 1 a range of other norm-based complexity measures that can given VC or Rademacher bounds. This article has over 400 citations.
    - Bartlett et. al.’s article [3], which considers Rademacher complexity bounds on overparameterized neural networks with a variety of norms constraints on all layer weights (see e.g. Theorem 3.3). This article has over 800 citations. This paper was already cited in the article under review. However, its use of weight norms to compute bounds on covering numbers is not discussed. 

- The authors give the following as an example of an improperly held belief about the role of VC dimension in explaining generalization in overparameterized neural networks: “Another common view is that “VC-dimension depends only on the model family and data distribution, and not on the training procedure used to find models” (Nakkiran et al., 2021). In fact, VC-dimension does not depend on data distribution.” I believe this assertion deserves a more nuanced treatment. Specifically, VC-dimension bounds on norm-constrained classes of predictors can only really be useful when the size of the norm-constraints depends on the data-distribution! For instance, consider a random feature model $f(x) = \theta \cdot x$ with a bound $||\theta||_2 \leq B$ on the model weights. If $y(x)$ is, say $\pm 1$,  independent of x, then B will have to be much larger in order to fit the data and give non-vaucuous bounds, compared with the case when $E[y(x) | x]$ is a say a smooth function. Hence, this seems like an important example where VC-dimension should depend on the data distribution (via the choice of a priori constrains on the collection of functions whose VC-dimension is being computed). 


[1] Bartlett, Peter. "For valid generalization the size of the weights is more important than the size of the network." Advances in neural information processing systems 9 (1996).

[2] Neyshabur, Behnam, et al. "Towards understanding the role of over-parametrization in generalization of neural networks." arXiv preprint arXiv:1805.12076 (2018).

[3] Bartlett, Peter L., Dylan J. Foster, and Matus J. Telgarsky. "Spectrally-normalized margin bounds for neural networks." Advances in neural information processing systems 30 (2017).
clarity,_quality,_novelty_and_reproducibility: The paper is well-written. However, as explained above, the main contribution of this article is not original.
summary_of_the_review: This article proposes that VC-dimension bounds of classes of neural networks with bounds on the norm of the final layer weights can explain double descent. However, the article fails to differentiate its point of view from the majority of prior literature on this subject. As a result, I believe this article is not ready for publication.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper presents a formula bounding the test error using VC-dimension. By further considering linear models, the paper connects VC-dimension with the squared norm of weights, Eq.(3). The paper then empirically computes the weight norm square and observed that, for the linear models, the curve of weight norm square matches the double descent curve. 
strength_and_weaknesses: Strength:

The strength of the paper lies in that it empirically observes the perfect match of the curve of weight norm square and the double descent curve on several linear models. This suggests a deep connection between the weight norm square and the test error. 

Weaknesses:

1: The paper only presents a few key formulas about the VC theory, but provides no theoretical derivation except a few references of prior works. As the VC-theory is the key of the paper, the authors should include a full analysis of all the details of the theory. The theory presented in the paper should be self-contained, such that readers with some background can understand the analysis/theory with minor or no reference to literature. 

Without giving details of the VC-theory, I cannot judge the correctness of the paper. 

2: Explaining double descent includes two parts: 1, theoretically connecting test error with weight norm square, or VC-dimension; and 2, theoretically explaining the behavior of weight norm square and VC-dimension.
The paper does not theoretically explain the behavior of the weight norm square. Even assuming all the formulas in the paper are correct, one still cannot claim the double descent is explained. 

3: The formula of VC-dimension, in Eq.(3), only applies to linear models. However, the most interesting part of double descent is for non-linear models, e.g., over-parameterized neural networks. For the non-linear models, there is still no explanation.

4: The values of $a_1$ and $a_2$ are not from theoretical analysis, but from empirical guesses. Then, I don’t think the key equation, Eq.(2), is theoretical. 

clarity,_quality,_novelty_and_reproducibility: [clarity] Most discussions are presented clearly. However, the main theory lacks many key details, making the correctness of the paper not judgable. 

[novelty] The empirical coincidence of the curves of weight norm square and double desent for linear model is novel.

[reproducibility] The experimental plots are considered reproducible.
summary_of_the_review: The observation of the empirical coincidence of the curves of weight norm square and double desent for linear model is interesting and encouraging. However, the main VC-theory is absent in the paper, and the behavior of weight norm square is not theoretically explained.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The main claim of the paper is that it "fully explains" double descent phenomenon in Deep Learning using VC theory. The authors claim to achieve this by applying VC theory and the corresponding bounds in a correct way. Significant part of the paper is the discussion around the fact that VC theory has largely been misunderstood by the Deep Learning community.

The authors build their suggested interpretation on two results from the VC theory: (a) the VC bound on the generalization gap that has empirical error as a multiplier in front of the classical $\sqrt{VC / n}$ term (Equation 1); and (b) the margin bound on the VC dimension (Equation 3). Both results are standard and well known in the literature: certainly in the statistical learning community and, perhaps to a lesser extent, in the Deep Learning community. After describing their interpretation, the authors demonstrate empirical results (for linear models) to support their claims.

I agree with the reviewers, who pointed out that revisiting old classical results in light of new developments can be an important and fruitful direction and that it "may shed insights into recent empirical observations". I also fully agree that "in some prior literature there are overly strong statements about ... extent to which VC-dimension bounds are useful in the overparameterized regime" and that it is important to "push back again[st] this point of view to some extent". 

Unfortunately, after reading the paper and also based on my detailed account of the entire reviewing and rebuttal process I have to agree with the reviewers and conclude that at this point the authors failed to support their claim ("fully explain the double descent in Deep Learning") in a convincing way. It has been noticed that what the authors argue for is "a conjecture/hypothesis that is inspired by VC theory, not an actual explanation", that the "explanation of double descent in the paper is fairly weak", and that "the paper "demonstrates" rather than "explains" it". The reviewers also expressed a concern regarding the novelty and contribution of the paper, questioning "whether there will be anything truly novel about the article under consideration", noticing that the paper "contains no new technical results" and that rather "its novelty ... [is] limited to interpreting old VC bounds and performing an empirical study in a new context". 

Considering all these points and given how bold the claims made in the paper are, I feel the paper can't be published in its current form. 

There are several concerns raised by most of the reviewers. 

First, while both the "formal" and empirical parts of the paper are focused on the linear setup, the authors extrapolate to the general Deep Learning (which is the main subject of the paper's claim) using a rather hand wavy argument. Quoting the reviewers, "the extension of their argument to deeper architectures is based on an unsupported hypothesis without any proof". It has been also noticed that the margin based VC-bound in Equation 3 "only applies to linear models" and that "for the non-linear models, there is still no explanation". 

Second, the formalism within the linear setup also raised some concerns. Very likely the authors can improve on this point by providing detailed and clear definitions, whenever applicable. The reviewers noticed that the paper is"very unspecific in citing the references for many of its general statements" and that it is "authors' responsibility to present the whole theoretical argument" in a clear, formal, and transparent way. "Simply citing the related works does not give readers the detailed argument". For example, I would suggest the authors to write down the precise definition of VC dimension *before presenting their proposed explanation* and to refer to it whenever making any claims related to the VC dimension. Equation 3 should appear together with all the accompanying assumptions (that the class only consists of predictors perfectly separating a given set with a required margin etc) made explicit. Also, I would suggest the authors to set in stone what exactly they mean by the "double descent phenomenon" --- is it with respect to the training step, or the number of parameters, or the model capacity? All versions have been presented and studied in the literature.

Third, the reviewers agree that the paper is largely missing a detailed discussion of the related results, including more recent works on the bounds accounting for various weight norms. They agreed that "it is imperative that a thorough review of and comparison with prior literature is undertaken".

Finally, if I am allowed to do so, I want to suggest the authors to be more forgiving and restrained in future, especially during the rebuttal phase.
justification_for_why_not_higher_score: As explained in my detailed meta-review, the paper makes a bold claim that it fails to support in a convincing way. Toning down the abstract and introduction, unfortunately, won't be enough to fix this issue. The authors should at least address three concrete points, raised by the reviewers (and listed in my meta-review), before the work can be considered for the publication.
Decision: Reject