Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 2: Strong Reject: For instance, a paper with major technical flaws, and/or poor evaluation, limited impact, poor reproducibility and mostly unaddressed ethical considerations.
review_content: summary: The paper empirically investigates whether relative VC bounds can
explain the double descent phenomenon. To this end, random features 
of size $N$ are created and then a (regularized) least squares 
approach in the feature space is performed. For the resulting, 
empirically observed weights, the relative VC bounds (among other 
quantities) are plotted as function of $N$. The obtained curves reflect 
the double descent phenomenon, at least for the unregularied case.
In addition, similar experiments are reported for NNs with one
hidden layer.
strengths_and_weaknesses: Unfortunately, the paper relies on a fundamental misunderstanding 
of VC bounds. Indeed, in these bounds, one first needs to FIX a 
class of hypotheses that is INDEPENDENT of the data samples, which 
are then observed in a second step. For this reason, it does not make
sense to use an estimate on the VC dimension that is obtained AFTER
training (as done in the experiments via the norm of the weights), and for the same reason, the 
discussion on the top of page 3 is entirely pointless.  
In other words, unless you are able to prove in advance that the algorithm you consider produces a weight vector whose norm is not exceeding a certain a-priorily fixed threshold, you cannot apply these bounds. And of course, you need to plug-in this threshold in the bounds and not the observed norm.

The entire setup somewhat reminds me to the so-called "luckiness"
approach taken in the early 2000s, but there the goal was to first 
derive solid new bounds, which is completely missing in this paper.

Finally, the authors idea to use relative bounds instead of the "usual" uniform bounds is also missing the point as both depend on $h/n$, where $h$ is (an upper bound of) the VC dimension and $n$ is the number of samples. The only major difference between these two type of bounds is that the uniform bounds depend on $h/n$ in a square-root fashion, whereas, at least in the ideal case, the relative bounds depend linearly on this fraction, see (2). 
questions: Can you address the serious issues I identified? Or did I completely misunderstood your paper?
limitations: Unfortunately, the authors do not seem to be aware of the limitations of their approach outlined above.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors present an alternative explanation for the “double-descent” phenomenon [1] sometimes observed in training classifiers as their capacity is increased. They claim that a VC-theoretic analysis can explain this behaviour, in contrast to the claims of prior work.

Their analysis is based on two changes to prior analysis: the use of relative-deviation VC bounds (which interpolate between slow and fast rates as the empirical risk tends to zero) rather than the slow-rate uniform deviation bounds commonly used; and the use of norm-based bounds on the VC dimension for larger models, for example the bound $V_C \le \min(\operatorname{dim}_\text{input}, \|w\|_2^2) + 1$ for linear classifiers.

The behaviour of this VC bound is compared directly to the training and testing error in settings seen in double-descent literature, such as linear classification based on fixed random Fourier or ReLU features, and one-hidden-layer ReLU networks using a hypothesised estimate for VC dimension in these settings.

[1] Reconciling modern machine learning practice and the bias-variance trade-off. Belkin, Hsu, Ma & Mandal.
strengths_and_weaknesses: ### Strengths

**Originality**: I am not too familiar with the literature since the early "double descent" papers, but it seems to me that the better VC bounds applied in this paper are new in this setting, although not new in general.

**Central idea**: I think the central (implied) idea of the paper is that the double descent phenomenon is observed because once we reach the interpolation threshold, we are minimising a norm instead of the error. This is actually mentioned already in [1], but the fact that this can be explained (at least in some cases) already through VC theory is a significant idea.

### Weaknesses

**Clarity**: This is one of the biggest shortcomings of this work. There are many grammatical mistakes, and I found myself flicking back and forward to look for explanations or definitions. The subject material is not particularly technical so I feel the authors could do much better here.

**Rigour**: This is another major shortcoming. A number of ad-hoc assumptions seem to be made, for example the way the authors assume that the VC dimension of a shallow neural network can simply be approximated by the final layer norm, or how it appears (see question) that the authors change the constants in the VC bound, because the original constants are "too loose for real-life data sets".

questions: 1. In l.76 you mention that you use alternative constants in the VC bound to that given by the theory. Are these just chosen in an ad-hoc way or justified by any theoretical development?

2. In l.146 you say that you rescale z values to $[-1, 1]$ to meet the condition for equation (3). But should this not be rescaling to $|z|_2 < 1$ instead?
limitations: I do not feel the authors discuss enough the limitations of the assumptions they use in obtaining their empirical results.

Societal impact: N/A this is a theoretical work.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper presents VC-theoretical analysis of double descent and shows that it can be fully explained by classical VC generalisation bounds. Theoretical and experimental results support the analysis.
strengths_and_weaknesses: Strengths
- approach is sound and theoretical grounded
- explanation of this phenomena by means of well known theory

Weaknesses
- there is actually nothing new theoretically
- experimental result is limited
questions: It is now always true that the norm of the weight goes down with the number of parameters (see e.g., Belkin et. al. and its experiment).
How you can deal with this cases?
Can't you show similar results using Rademacher or Local Rademacher Complexity?
[Belkin] https://arxiv.org/pdf/2105.14368.pdf
limitations: It is now always true that the norm of the weight goes down with the number of parameters (see e.g., Belkin et. al. and its experiment).
[Belkin] https://arxiv.org/pdf/2105.14368.pdf
review_title: null

Meta-review: metareview: Having read the paper on my own, I am, like one of the reviewers, not convinced by the authors' approach: The VC-bound (3) is actually of the following form (see Cherkassy + Mulier, page 420 for a statement that is more clearly formulated than those in Vapnik's books):

Given a data set $D$ in the unit ball, the set $H_{\Delta,D}$ of all hyperplanes that correctly classify $D$ with margin $\Delta$, see (9.6) on page 419 for a definition of the latter, has VC-dimension $h \leq \min(\Delta^{-2}, N) + 1$. Now, to apply a generalization bound of Vapnik to this VC-estimate one needs to fix this set $H_{\Delta,D}$ of hyperplanes, get a second data set $D_2$, and train a learning algorithm on this second data set $D_2$ that chooses a predictor from $H_{\Delta,D}$. This is the way one needs to interpret the rather informal corollary of Theorem 5.1 in Vapnik's [9] on page 133. Indeed, the same statements can be found in Vapnik's [8] on page 408, where he explicitly refers to results on page 148, in which the class of predictors is, of course, a-priori fixed. (By the way, if the corollary was interpreted to hold on the original data set $D$, instead, then the first term $m/l$, which is the empirical training error, would always vanish.) 

Now, if we have a hyperplane $w$ with zero loss on $D$, then it is in $H_{||w||^{-1}, D}$ and one could apply the bounds as described above. But this is far from what is done in the paper. 

In summary, the paper has a major technical flaw and for this reason it cannot be accepted.
confidence: Certain
Decision: Reject