VC Theoretical Explanation of Double Descent
Authors: Eng Hock Lee
Vladimir Cherkassky
Venue: Submitted to ICLR 2023 (2023)
Keywords: Double Descent
Deep Learning
SVM
Least Squares
VC Dimension
VC Generalization Bounds
Structural Risk Minimization

Abstract: There has been growing interest in generalization performance of large multilayer neural networks that can be trained to achieve zero training error, while generalizing well on test data. This regime is known as ‘second descent’ and it appears to contradict the conventional view that optimal model complexity should reflect an optimal balance between underfitting and overfitting, i.e., the bias-variance tradeoff.
This paper presents a VC-theoretical analysis of double descent and shows that it can be fully explained by classical VC-generalization bounds. We illustrate an application of analytic VC-bounds for modeling double descent for classification problems, using empirical results for several learning methods, such as SVM, Least Squares, and Multilayer Perceptron classifiers. In addition, we discuss several reasons for the misinterpretation of VC-theoretical results in Deep Learning community.

Under review as a conference paper at ICLR 2023
VC THEORETICAL EXPLANATION OF DOUBLE DE- SCENT
Anonymous authors Paper under double-blind review
ABSTRACT
There has been growing interest in generalization performance of large multilayer neural networks that can be trained to achieve zero training error, while general- izing well test data. This regime is known 'second descent' and it appears to contradict the conventional view that optimal model complexity should reflect optimal balance between underfitting and overfitting, i.e., the bias-variance trade-off. This paper presents a VC-theoretical analysis of double descent and shows that it can be fully explained by classical VC-generalization bounds. We illustrate an application of analytic VC-bounds for modeling double descent for classification, using empirical results for several learning methods, such as SVM. Least Squares, and Multilayer Perceptron classifiers. In addition, we discuss sev- eral reasons for the misinterpretation of VC-theoretical results in Deep Learning community.
INTRODUCTION
There have been many recent successful applications of Deep Learning (DL). However, present, various DL methods are driven mainly by heuristic improvements, while theoretical and conceptual understanding of this technology remains limited. For example, large neural networks can be trained to fit available data (achieving zero training error) and still achieve good generalization for test data. This contradicts the conventional statistical wisdom that overfitting leads to poor generalization. This phenomenon has been systematically described by [Belkin et al. (2019) who introduced the term 'double descent' and pointed out the difference between the classical regime (first descent) and the modern one (second descent). The disagreement between the classical statistical view and modern machine learning practice provides motivation for new theoretical explanations of the generaliza- tion ability of DL networks and other over peee-paaamtteieeed estimators. Several different explanations include: special properties of multilayer network parameterization (Bengio 2009), choosing proper inductive bias during second descent (Belkin et al. 2019). the effect of Stochastic Gradient Descent (SGD) training (Zhang et al.) 2021: Neyshabur et 2014 Dinh et al. 2017), the effect of various heuristics (used for training) on generalization (Srivastava al. (0014), and the effect of margin on generalization (Bartlett et al. 2017). The current consensus view on the 'generalization paradox' in
DL networks is summarized below:
Existing indices for model complexity (or capacity), such as VC-dimension, cannot explain generalization performance of DL networks.
'Classical' thcories developed in ML and statistics cannot explain generalization perfor- mance of DL networks and the double descent phenomenon. Specifically, Zhang et al. (202T) argues that the ability of large DL networks to achieve zero training error (during second descent mode) effectively "rules out all of the VC-dimension arguments possi- ble explanation for the generalization performance of state-of-the-art neural networks."
This paper demonstrates that these assertions are incorrect, and that classical VC-theoretical re- sults can fully explain generalization performance DL networks, including double descent, for classification problems. In particular, we show that proper application of VC-bounds using correct estimates of VC-dimension provides accurate modeling of double descent, for various classifiers trained using SGD, least squares loss and standard SVM loss. The proposed VC-theoretical expla- nation provides additional insights on generalization performance during first descent vs. second descent, and the effect of statistical properties of the data on double descent curves.

---

Under review as a conference paper at ICLR 2023
Next, briefty review VC-theoretical concepts and results necessary for understanding general- ization performance of all learning methods based on minimization of training error (aapnik 1998
1999 2006; Cherkassky & Mulier 2007):
1. Finite VC-dimension provides necessary and sufficient conditions for good generalization.
2. VC-theory provides analytic bounds on (unknown) test error, as function of training error, VC-dimension and the number of training samples.
Clearly, these VC-theoretical results contradict an existing consensus view that VC-theory cannot account for generalization performance of large DL networks. This disagreement results from a misinterpretation of basic VC-theoretical concepts in DL research. These are a few examples of such misunderstanding:
A common view that VC-dimension grows with the number of parameters (weights), and therefore, "traditional measures of model complexity struggle to explain the generalization ability of large artificial neural networks" (Zhang et al., 202I). p. In fact, is well known that VC-dimension can be equal, or larger, or smaller, than the number of parameters (Vapnik)
1998 Cherkassky & Mulier 2007).
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 data distribution (Vapnik) 1998] Cherkassky & Mulier 2007, Schölkopf & Smola 2002). Furthermore, VC-dimension certainly depends on SGD algorithm (Vapnik] 1998 Cherkassky & Mulier 2007).
For classification problems, VC-theory provides analytic generalization bounds for (unknown) Pre- diction Risk (or test error Rtst), as a function of Empirical Risk (or training error Rern) and VC- dimension (h) of a set of admissible models. That is, for given training data set (of size n), VC-bound has the following form /Vapnik
1998
1999
2006 Cherkassky & Mulier 2007):
Rest S Rern +
1+
4Rern
where 8 = a1 (n
[In
a2n h
+
-In
" 7)
(I)
This bC-bo T holds with probability of 1 1- for all possible models (functions) including the one minimizing Kirn- The value of 1) is preset to a small value, i.e., 17 = 4/ /n. The second additive term IT. called the confidence interval (also known as excess risk), depends on both Rern and h. This bound describes the relationship between training error, test error, and VC-dimension, and it is used for conceptual understanding of model complexity control, i.c. the effect of VC-dimension on test error. Application of this bound for accurate modeling of double descent curves requires:
Selecting proper values of positive constants and a2 The worst-case values = 4 and 02 2. provided in VC-theory (Vapnik) 1998, 1999) correspond to the worst-case "heavy-tailed" distributions, resulting in VC-bounds that are too loose for real-life data sets (Cherkassky & Mulier 2007). For real-life data sets, when distributions are unknown, we suggest the values a 3 and 02 = 1, that were used for all empirical results in this paper. For additional discussion about selecting these values (incorporating a-priori knowledge about unknown distributions), see Appendix A.
Analytic estimates of VC-dimension. For many learning methods (including DL), analytic estimates of VC-dimension are not known. For example, for SGD-style algorithms, the effect of various heuristics (e.g.. initialization of weights, etc.) on VC-dimension is difficult (or impossible) quantify analytically.
Note that VC-bound (T) provides conceptual explanation of both first and second descent. That is. first descent corresponds to minimizing this bound when training error is non-zero (Vapnik) [998] 1999 Cherkassky & Mulier 2007). Second descent corresponds to minimizing this bound when training error is kept at zero, using models having small VC-dimension. This can be shown by setting the training error in bound (I) to zero, resulting in the following bound for test error during the second descent (uisng values
3 and 02 = 1):
where = = 3h
Rist S E,
In
+ +1)
(2)
h
2

---

Under review as a conference paper at ICLR 2023
Technically, since VC-bound depends only on two factors, training error and VC-dimension, there are two different strategies for minimizing this bound (Cherkassky & Mulier 2007):
Strategy 1: for a set of functions (models) with fixed VC-dimension, reduce the training er- ror. This leads to well-known classical bias-variance trade-off, also known as first descent;
Strategy 2: for small (fixed) training error, minimize the VC-dimension. This strategy corresponds to second descent.
These are two different strategies for controlling VC-dimension, leading to different implementa- tions of Structural Risk Minimization (SRM) in VC-theory. Strategy 2 is formally described in VC-theory by considering set of functions (models) where the training error remains constant, called an equivalence class (Vapnik, 1998 1999; Cherkassky & Mulier] 2007). For example, all models during second descent form an equivalence class (since the training error is zero). For each equivalence class, we define a structure, or complexity ordering, according to the norm squared of weights (of a linear classifier). Then an optimal model (minimizing the norm squared of weights) is found using training data. Such strategy has been implemented via maximization of margin in SVM classifiers. Most learning methods typically implement a single strategy, whereas practitioners in DL observed the effect of both strategies when varying single hyper- hyper-paraman parameter, such as network size or the number of epochs. Therefore, double descent curve has a simple VC-theoretical explana- tion. For instance, consider the effect of increasing the number of hidden units N (in single-layer network) on the test error. When the number of hidden units is small, SGD training aims to minimize training error, and VC-dimension is increasing with the number of hidden units. This corresponds to Strategy for minimizing the VC-bound ( On the other hand, for pver-parameterized networks (large N), SGD training finds minimum norm of weights solution effectively implementing Strat- egy 2 for minimizing VC bound ( The mystery of improved generalization performance during second descent explained by noting that for larger networks, VC-dimension is actually decreasing. This is confirmed by the empirical modeling results presented later in Section 2
Another technical reason for misapplication of VC-theory, besides misinterpretation of VC- dimension, is that VC-bound (T) remains virtually unknown in the DL community. Many papers suggesting that VC-theory is unable explain double descent, are based on analysis of uniform convergence bounds (Belkin et al. 20199, Zhang et al. [202 Tewari & Bartlen 2014, Bartlett et al.) 2021 Koltchinskii 2001] Sokolii et al.) 2017). In such bounds, the confidence interval term (or
excess error), is of the order O (vh/n) However, VC-theory also provides more accurate uni- form relative convergence bounds, such as VC-bound ( presented in (Vapnik 1998 1999 2006 Cherkassky & Mulier 2007), where the excess error of the order (hh/n) For small values of h/n, common in practical applications, this difference is large. For example, for h/n = 0.1, uniform relative convergence bounds give 10% excess error, but the uniform convergence bounds give v0.1 or ~ 33%. So, while it true that uniform convergence bounds cannot accurately model second descent, it can be done using uniform relative convergence bounds.
Training of DL networks is based on SGD, which incorporates several heuristic rules ensure that the norm of weights remains small. These rules include: initialization of weights to small random values, weight decay, and re-normalization during training. Consequently, for large networks, model complexity is determined by the norm of weights, rather than the number of weights (parameters). Further, this dependence of VC-dimension on the training algorithm helps explain why theoretical estimates of VC-dimension based on network topology (network size) have found little practical use CChrrassky & Mulier 2007).
APPLICATION OF VC BOUNDS FOR MODELING DOUBLE DESCENT
This section presents a VC-theoretical explanation of double descent for classification, for a single- layer network shown in Figure
The same network setting was used for analysis of double descent
in recent papers (Belkin al. 2019 2020 Neal al. 2018 Hastie al. 2019). In this network,
classifier is estimated in two steps:
First, input vector is encoded using N nonlinear features in Z-space. Commonly, ran- dom features (weak features) are used, such as random ReLU or Random Fourier Features (RFF);
3

---

Under review as a conference paper at ICLR 2023
9 (x.w)
Miy
Figure 1: A single hidden layer network estimating linear classifier in nonlinear feature space.
Second, a linear model is estimated in this N-dimensional feature space.
This simplified setting enables VC theoretical analysis of double descent, because the analytic esti- mates of VC-dimension are known, That is, since the network output is formed as linear combina- tion of features, the analytic estimate of VC-dimension for linear hyperplanes [(z, w) = (wz)+
is known /Vapnik 1998 1999 2006):
h S min 3 +
(3)
This bound holds under the assumption that all training samples are enclosed within sphere of radius in Z-space. In summary, VC-dimension can be bounded by the input dimensionality (N), or by the norm squared of weights These are two different mechanisms for controlling VC- dimension. In machine learning literature, the expression (3) is widely known as scale-sensitive or fat- fat-shattering VC-dimension (Schölkopf & Smola 2002) Shawe-Taylor al. 1996), where shatter- ing is performed by delta margin hyperplanes (with constraints on margin size or [[0]] ())
The double descent phenomenon weights w for the network structure in Figure [1] Next, we present empirical results showing the application of VC-bounds (1) and (3) for modeling double descent when network weights are esti- mated using SVM or Least-Squares (LS) classifiers. For large networks trained using LS, when N is larger than sample size (n), minimization of squared error is performed using pseudo-inverse, which finds a solution corresponding to the minimization of the norm squared ||
be observed for various learning methods used estimate
In all experimental results in this section, double descent is observed when the network size (N) is gradually increased. Specifically, according to analytic bound 3
When network size (N) is small, the VC-dimension initially grows linearly with N. This corresponds to the first descent, or traditional bias-variance trade-off.
For overparameterized networks (large N), VC-dimension controlled by the norm squared of weights, leading second descent.
We use two types of random nonlinear features (Belkin et al. 2019 Rahimi & Recht 2008), ReLU and RFF. Random ReLU features are formed as:
Z: max ((v; X),0), 0), i= 1,..., N
where random vectors "1,..., uy sampled uniformly from the range [-1,1]. Random Fourier Features (RFF) are formed as:
Z: exp (x-(1Vl X)), i= 1,.,,, N
Where random vi,..., Uy are sampled from Gaussian distribution with standard deviation 0.05. In all experiments, input (x) values were pre-scaled to [0, 1] range, for training and test data.
Following the nonlinear mapping X - Z. all z-values re-scaled to [-1, 1] range. Such rescaling is performed to satisfy the condition for bound (3), stating that all training samples Z-space should be enclosed within sphere of radius 1.
4

---

Under review as a conference paper at ICLR 2023
a)
b)
SVM Modeling Results
LS Modeling Results
SVM Modeling Results
L3 Modeling Results
8
24
0.2
0.2
Separt
300
Norm Sgeane
0
Nar
800
VC Demeroan
VC Omeesion
VCDrense
8
Figure 2: Application of VC-bounds for MNIST digit 8 data set using a) random ReLU features and b) RFF.
Training samples (z. y) are used to estimate decision boundary in Z-space. Two different methods (L. and SVM classifiers) are used for estimating linear decision function f(z, w) (w²² + from training data, in order to show double descent curves for two different loss functions, LS and SVM loss. For SVM modeling, the regularization parameter C is set to in all experiments.
Most empirical results in this paper were obtained for MNIST digits adapted for binary classification (digit 5 vs 8), where digits are grey-scale images of size 28x28. The training set size is n = 800 and test set size is 2,000. We have also used other data set for modeling and observed similar results. See Appendix for additional results.
Figures
a) and bb) show application of VC-bounds modeling MNIST data. They show:
Empirical training and test error curves, function of N (the number of nonlinear fea- tures), along with VC-theoretical estimate of test error obtained via bounds (I) and (3). These curves show that analytic VC-bounds explain (and predict) double descent;
The norm squared of weights of estimated linear models, function of the number of features N;
The estimated VC-dimension via bound (3). as a function of the number of features N;
For SVM, also show the number of support vectors for trained SVM model.
Modeling results for random ReLU features and RFF are similar, only comment on results in Figure 2 a):
For small N, VC-dimension grows linearly with N for SVM method. Empirical results show that first descent eиrог curves be explained by VC-bound (I), because the minimum of VC-bound closely corresponds to the minimum of test error. This can be clearly seen for LS classifier, but less obvious for SVM.
For large N, VC-dimension is controlled by the norm squared, according to bound (3) These results show that second descent can be explained by VC-bound (I). for both SVM and LS learning methods.
Whereas empirical results for both SVM and LS in Figure 2 a) are qualitatively similar, their double descent curves show different values interpolation threshold N (where the training error reaches zero). For SVM, the value N* z 100 is achieved when the number of features equals the number of support vectors. For LS classifier, the interpolation point N x 800 is achieved when the number of features equals the number of training samples.
5

---

Under review as a conference paper at ICLR 2023
Random ReiLU Features.
Random RolL Features
0%
Noke 20% hotus
10% Nose
20% Mose
Eiee
0.3-
20% Noise
0.0
0.3
0.4
6.3-
0.2
10
20F
Korm Squared
Suspont Veter
400
250
500
750
1000 1250 1930
3750
2000
250
500
750 1000 L250 1500 1750 2010
Figure 3: Effect of noise on double descent for MNIST data, for SVM and LS classifiers using random ReLU features.
The dependence of test error on the norm of weights in large networks has been known to practition- ers, and some limited theoretical explanation is provided in (Belkin et al., 2019 2018 Gunasekar a 2017). For example, Belkin et (2019 2018) suggest that minimum norm provides inductive bias by favoring models with higher degree of smoothness. However, these papers do not mention VC-bounds that clearly relate the VC-dimension to the norm weights, and explain generaliza- tion performance for linear classifiers. Our results also show that the same VC-bounds apply with different loss functions used for training, i.e., SVM and LS loss. For both loss functions, second descent implements the same VC-theoretical structure where the elements of structure are ordered according to the norm squared of weights. For large N, the estimated model trained using SVM loss approaches standard kernel SVM solution, whereas model trained using LS loss approaches Least-Square SVM solution (Sykens & Vandewalle 1999).
The dependence of interpolation threshold N* on training sample size for LS classifiers has also been observed in the DL literature. However, in the absence of sound theoretical framework for double descent, interpretation of this empirical dependency leads to convoluted explanations. For example, Nakkiran et al. (021) investigated the effect of varying the number of training samples on test error, for a fixed-size DL network. particular, they observed two double descent error curves for the same network trained using smaller and larger size training data. Under this setting, near interpolation threshold, the test error for network trained with a larger data set is worse than for the same network trained on a smaller data set. This phenomenon was called 'sample-win wise monotonicity' and a new theory was proposed for explaining regimes where 'increasing the number of training samples actually hurts test performance'. However, this phenomenon has simple VC- theoretical explanation, presented next. During second descent, the shape of the 'norm squared' closely follows the shape of test error, according VC-bound (2). as evident in Figures Ph and ( Since for LS classifiers the interpolation threshold is given by training size, there is a region near interpolation threshold where VC-dimension for a smaller training size is smaller than for larger training size. So, in this region we can expect smaller test error for smaller training size.
"C-theoretical framework can also help understand the effect of statistical characteristics of train- ing data on generalization curves. Next, we present empirical results demonstrating the effect on noisy data on the shape of double descent curves, along with their VC-theoretical explanation. For these experiments, we use single-layer network trained using SVM and LS classifiers using ran- dom ReLU features. We use digits data with randomly corrupted class labels. The training set size is 800 (400 per class), and the test set size is 2,000. Figure 3 shows the effect of noise level on the shape of double descent curves, for SVM and LS classifiers. Results for both SVM and LS models show double descent curves, but their shape is different. For the SVM model estimated using "clean' data (0% label noise), there is no visible first descent at all, but for noisy data we observe both first and second descent. For the L. model, clearly observe first and second descent for both clean

---

Under review as a conference paper at ICLR 2023
and noisy training data. For LS curves, the interpolation threshold (<s training size 800) is the same for different noise levels, but for SVM the value of interpolation threshold increases with noise level in the data. This can be explained by noting that for SVM, the interpolation threshold is reached when the training data becomes linearly separable (in nonlinear feature space, or Z-space in Figure D. Therefore, for SVM the interpolation threshold is given by the number of support vectors needed to separate training data. For noisy data, a SVM model requires a larger number of support vectors, resulting in larger interpolation threshold
The ability to generalize for noisy data can be explained by noting that during second descent VC- bound (2) depends only on VC-dimension (the norm of weights). With increasing noise (in the data), the norm of weights increases, resulting in degradation of test error and flattening of second descent test error curve (as evident in Figure for both SVM and I.S).
Empirical results in F also show that for noisy data, generalization performance during second descent degrades relative to an optimal first descent model. This is contrary to the popular view that DL networks usually provide superior generalization performance during second descent (Belkin)
ct al. 2019 Zhang et al. 2021 Neyshabur et al. 2014 Nakkiran et al.) 2021).
We suspect that superior performance during second descent, reported in the DL community, can be explained by using large and 'clean' data sets (common in Big Data). For such training data sets (of large size n),, generalization performance during second descent is likely to be good, because the VC-bound (2) on test error depends only on the ratio of VC-dimension to sample size (h/n).
MODELING DOUBLE DESCENT FOR MULTILAYER NETWORKS
Empirical results for simplified network setting in Section provide insights for generalization performance of over- peeemaaraeteri multilayer networks. Such general DL. networks use SGD train- ing that keeps the norm of weights small, so that the model complexity is determined by the norm of weights, rather than the number of weights. However, direct application of analytic VC-bounds to modeling double descent may be tricky, due to two challenging research issues:
1. How to estimate VC-dimension for DL networks, where analytic estimates do not exist;
2. Understanding design choices for setting multiple 'tuning' parameters, such as network width, number of training epochs, weight initialization, etc. All of these hyperparameters can be used to control the VC dimension of DL networks. Double descent curves show dependence of training and test error on a single complexity parameter, when all other tuning parameters are preset reasonably 'good' values.
For these reasons, the application of analytic VC-bounds to general DL networks is difficult. How- ever, it can still be done for restricted and well-defined network settings. In this section, we consider fully connected network with single hidden layer, in Figure [ where the network weights in both layers are estimated during training via SGD. In this case, z-fcutures are adaptively estimated from training data, in contrast to fixed random features used earlier in Section 2
Let us consider two factors (hyperparameters) controlling the complexity of such networks trained via SGD: the number of hidden units (N), and the number of training epochs. Empirical results showing double descent curves as a function of these two factors have been extensively reported in DL literature (Beikin et al.) 2019 Nakkiran al., 2021). However, our purpose here is not to replicate such double descent curves, but to explain them using VC-bounds TT and (3). In order to achieve this, we specify network settings where the VC-dimension can be approximately esti- mated. Therefore, we only consider over peer-aramettrized (wide) networks during second descent, i.c., when the number of hidden units N large, or the number of training epochs is large. We hypoth- esize that under such restricted settings, the VC-dimension of neural network can be estimated as the norm squared weights of the output layer. This hypothesis is based on the recent understanding that during second descent regime sufficiently wide dingle-layer networks (trained via SGD) closely approximate a linear classifier shown in Figure T See Belkin (2021) for a mathematical explana- tion of this phenomenon called "transition to linearity". Similarly, Bietti & Bach (2021) showed that wide fully-connecter multilayer networks have essentially the same approximation properties as their "shallow" two-layer counterparts, implementing standard kernel machines.
7

---

Under review as a conference paper at ICLR 2023
a)
b)
100
Tunn Ener Ter Enor
Tran Crer
Trin Degr
*xt Emar
0.3
Erur
0.9
5.5
6
VC Dineeedoon
Morm Squaree
4.5
Momo
530
1000
1500
2000
4500
0000
1500
3000
4500
6000
Number ofiddden units
Number of epachs
Number epechs
Figure 4: VC-theoretical modeling of second descent in fully connected network. a) Second descent as a function of network width (N). b) Second descent as function of the number of epochs, for 10 and N 100.
According to this interpretation, minimization of the norm of weights in the output layer is mainly responsible for generalization, whereas all previous layers perform non-linear transformation of input x, by encoding it as large number of weak nonlinear features (~ N nonlinear features in Z-space). argue that this assumption is plausible for data sets originating from well-separable (low-noise) class distributions, such as MNIST digits where good generalization can indeed be achieved during second descent, by both linear and nonlinear networks (of large width). Therefore, restrict modeling of second descent for nonlinear networks using VC-bounds, presented in this section, only for such separable distributions.
Our experiments show application of VC-bound 2 under such restricted settings, i.e., for over- parameterized fully connected networks trained using SGD, using the norm of weights in the output layer as estimate of VC-dimension during second descent.
We present empirical results for MNIST digits data, under the following experimental setting:
800 training and 2,000 test examples (of digits and 8);
Fully connected network using ReLU activation function in hidden units (Paszke et al., 2019);
Training using SGD with learning rate 0.001 and momentum 0.95. The learning rate is reduced by 10% for every 500 epochs. Batch normalization used during training.
Weights initialized, prior to training, using Xavier uniform distribution, following Glorot
& Bengio 2010).
Our design choices for SGD implementation mainly follows earlier studies (Belkin et al. 2019 Glorot & Bengio 2010).
Figure shows modeling results for second descent mode, as a function of the number of hidden units N (the number of epochs is set to 6000 in all experiments). These results show empirical training and test error curves, and the VC-bound on test error, that closely approximates empirical test eиror. This figure also shows the VC-dimension, estimated as the norm squared of the output layer weights. It is interesting to compare modeling results in Figure 4 (for nonlinear network) and LS results shown in Figure a) for the same data set, but using a linear network. First, we can observe similarly decreasing norm squared of the output layer weights, in both figures. Second, direct comparison models, for large networks, indicates their similar values. For network size N= 2,000, the norm squared of the weights (and test error) equals 3.3 (3.7%) for linear network and 2.3 (3.1%) for a nonlinear network. Since the norm squared of weights was used as VC-dimension in bound (2) for both linear and nonlinear networks, these comparisons support our hypothesis about using this norm squared, proxy for VC-dimension during second descent.
the norm squared weights (of the output layer), for linear and nonlinear
8

---

Under review as a conference paper at ICLR 2023
Figure bb shows modeling results for second descent, function of the number of epochs (for networks with N = 10 and 100 hidden units). Note that VC-dimension can be reliably estimated only in second descent mode, when training error is close to zero. This region, where training emror is under 1%, is indicated by dotted vertical line. In this region, increasing the number of epochs results in small increase in VC-dimension and slight decrease of training error. This is particular form of cemmorization-comlllxe to zero. For additional results on modeling double descent multilayer networks, see Appendix B.
trade-off, implicit in VC-bound ( when training error is close
These results demonstrate application of VC-bounds for modeling second descent in multilayer networks. In addition, we can see the effect of each complexity parameter (network size N and the number of epochs) on VC-dimension. This can be used for ranking tuning parameters, according to their ability to control VC-dimension of DI. networks during second descent.
SUMMARY AND DISCUSSION
This paper provides a VC-theoretical explanation of 'double descent' in multilayer networks. We show that for simplified network settings, where analytic estimates of VC-dimension exist, VC- generalization bounds can be applied directly to predict double descent phenomenon. VC-theoretical framework is helpful for improved understanding of empirical results observed in DL, such as: mod- eling of double descent, the effect of various heuristics generalization, comparing generalization during first and second descent, etc. According to VC-theoretical explanation, second descent oc- curs when zero training error is achieved using an estimator having small norm of weights. This phenomenon is general, and it does not depend on particular training algorithm or chosen model parameterization. Therefore, double descent can be observed for other learning methods, such as SVM estimators.
VC theoretical interpretation of double descent has several methodological implications. As ex- plained in this paper, the first and second descent modes of learning implement two different types of VC-theoreticall 'structures', or complexity orderings, of possible models. Both types of structures have been well-known but are usually presented separately when analyzing different learning meth- ods (Vapnik] 1998 1999; Cherkassky & Mulier, 2007). Second descent mode of learning has been studied in the past, long before DL. albeit under different terminology, such as margin maximiza- Squares SVM classifiers (Suykens Vandewalle 1999), and Optimal Linear Associative Memory (Kohonen 1989). Recently, the similarity between second descent and kernel learning has been rediscovered by several authors (Belkin et al., 2018 Belkin 2021 Bietti & Bach 2021).
tion standard SVM,
According to VC-methodology, we should analyze the first and second descent modes of learning separately, as they implement two different types of SRM structures. Just showing test eтror curves for these two structures on the same figure, as double descent, does not provide much technical insight. An important open question is understanding under what conditions a model estimated during first descent provides better generalization than a model estimated during second descent. Current DL literature suggests that second descent provides better generalization performance, for most 'real life' data sets but this statement requires better technical explanation.
According VC-theoretical explanation, superior generalization performance during second de- scent can be expected for large sample size, that are inherently separable, i.e. have small Bayes optimal test error (say, under 5%). In this case, using structure based on the norm of weights results in a second descent mode, where training error is zero and VC-bound on test error is given by ( According to this expression (2), this bound is expected to be small, for small values of the ratio of VC-dimension to sample size (h/n).
Finally, we point out that VC-theoretical explanation of double descent utilizes just a few well known concepts, such as VC-dimension and Structural Risk Minimization. The same VC-theoretical con- cepts and results explain generalization performance of other methods, such as parametric estima- tors, SVM, signal denoising, etc (Cherkassky & Mulier 2007). This is in contrast to multiple recent theories for explanation of double descent, that introduce various new theoretical constructs and associated technical jargon, aimed explain this particular empirical phenomenon.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ralph G. Andrzejak, Klaus Lehnertz, Florian Mormann, Christoph Ricke, Peter David, and Chris- tian E. Elger. Indications nonlinear deterministic and finie-ddimnnsionl structures in time se- ries of brain electrical activity: Dependence on recording region and brain state. Physical Review E, 64:061907, 2001.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. pppctrally-normalizee margin bounds for neural networks. In Advances Neural Information Processing Systems, pp. 6241-6250, 2017.
Peter Bartlett, Andrea Montanari, and Alexander Rakhlin. Deep learning: a statistical viewpoint. Acta Numerica, 2021.
Mikhail Belkin. Fit without fear: Remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-248, 2021.
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to under- stand kernel learning. In International Conference on Machine Learning, pp. 541-549, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences,
2019.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4), 2020.
Yoshua Bengio. Learning deep architectures for ai. Foundations and Trends in Machine Learning, 2(1):1-127, 2009.
Alberto Bietti and Francis Bach. Deep equals shallow for relu networks in kernel regimes. In Proceedings of the International Conference on Learning Representations, 2021.
Vladimir Cherkassky and Filip Mulier. Learning from Data. Second Edition, Intes-ent 2007.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pp. 1019-1028, 2017.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. Proceedings of Machine Learning Reseach, pp. 249-256, 2010.
Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nathan Sre- bro. Implicit regularization in matrix factorization. Advances Neural Information Processing Systems, pp. 6151-6159, 2017.
Trevor Hastie, Andrea Montanari. Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:
2019.
Teuvo Kohonen. Orfaniaaanzzttion and Associative Memory. Third Edition, Springer Series in Information Sciences, 1989.
Vladimir Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 47(5):1902-1914, 2001.
Alex Krizhevsky and Geofrey Hinton. Learning multiple layers of features from tiny images. Mas- ter's thesis, University of Toronto, 2009.
Yann LeCun, Léon Bottou, Yoshua Bengio. and Patrick Haffner. Gradient-based learning applied to document recognition. In Proceedings of the IEEE, 86(1 (6(11):222 1):2278-2324, 1998.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2021 2021.
10

---

Under review as a conference paper at ICLR 2023
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Loannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv preprint arXiv: arXiv:1810.08899/ 2018.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning. 2011.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv: 1412.6614, 2014.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury. Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Ed- ward Yang. Zach Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing systems, pp. 8026-8037, 2019.
Ali Rahimi and Ben Recht. Random features for large-scale kernel machines. In Advances Neural Information Processing Systems, pp. 1177-1184, 2008.
Bernhard Schölkopf and Alexander J. Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, 2002.
John Shawe- Taylor, Peter L. Bartlett, Robert C. Williamson, and Martin Anthony. A framework for structural risk minimisation. In Proceedings of the Ninth Annual Conference Computational Learning Theory, 1996.
Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel R. D. Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265-4288. 2017.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56): 1958, 2014.
Johan A. K. Suykens and Joos Vandewalle, Least squares support vector machine classifiers. Neural Processing Letters, 93):2933300, 1999.
Ambuj Tewari and Peter L. Bartlett. Learning theory. Academic Press Library in Signal Processing, 2014.
Vladimir Vapnik. Statistical Learning Theory. John Wiley & Sons, New York, 1998.
Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer, 1999.
Vladimir Vapnik. Estimation of Dependencies Based on Empirical Data. Second Edition, Springer, 2006.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint 1088v01708.07777 2017.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. Communications of the ACM, 64(3):107-155, 2021.
APPENDIX A: SELECTION OF PARAMETERS IN VC-BOUNDS
This Appendix includes additional empirical results for modeling double descent in single-layer network shown in Figure in the main paper. First set of results investigates the choice of theoretical reproduced below:
constants and 02 in VC-bound (1)
E 2
4R
Rest < Ramn +
1 +
1 +

---

Under review as a conference paper at ICLR 2023
a)
b)
0% Noise
5% Noise
1.0
Train Error
Train Error
VC Bound
VC Bound
Error
0.5
0.5
2000 Number of random ReLU features N
0
500
1000
1500
500
1000
1500
2000
Number random ReLU features
Figure 5: Modeling double descent for MNIST data set (digit 5 vs 8) using values = and
02 1, with a) original data set (no label noise) and b) 5% label noise added.
0% Noise
5% Noise
10% Noise
Train Error
VC Bound
0.5
1000
1300
2000
1000
1500
2000 0
1000
2000
N
Figure 6: Modeling double descent for digits data with corrupted class labels, using values d1 3 and 02
1.
where
(
In
O27
+ In 7)
4 Vn
VC-theory [Vapnik 1998 1999) specifies their range and provides the values corresponding to pes- simistic assumptions (about unknown data distributions):
the range [0, 4] for aj and [0,2] for d2-
worst-case values a1 = 4 and d2 =
These worst-case values result in upper bounds that are too crude for real-life data sets. It may be worth noting here that VC-bounds (and most other analytic results in VC-theory) are regarded as conceptual, and they have not been used for modeling real-life data sets. However, in this paper, we apply VC-bounds for modeling double descent, selecting 'practical' values of these constants be- comes critical. The original reference on VC-theory (Vapnik (2066) provides a technical discussion on the problem of incorporating prior knowledge (about unknown distributions) into VC-bounds. Whereas a-priori knowledge about particular form of distribution allows to obtain accurate results (for that distribution), such results have limited practical value. Therefore, we can only provide general guidelines for selecting proper values for values aj and 02. based empirical results for multiple data sets. Such guidelines, along with their empirical justification, are presented next.
The overall recommendation is that using values a = 3 and 02 results in practical VC-bounds providing accurate and robust modeling of double descent for real- data sets. For 'clean' data sets from well-separable class distributions using values a 1 and 0g results in more accurate bounds.... Applying bounds with values a, and 02 to model clean and noisy data sets illustrated in Figure 5).), showing modeling results for digits data set used in Section 2 of the
12

---

Under review as a conference paper at ICLR 2023
Ô 0
Ô= 0.1
0.2
1.0
Train Error
Test Erro
VC Bound
Emor
0.5
500
1000
1500
2000
500
1000
1500
2000 0
500
1000
1500
2000
N
Modeling double descent for digits data with pixels corrupted by Gaussian noise, using values Q1 = and 02 = 1.
Figure 7:
main paper. These results show that VC-bounds provide accurate estimates for clean data set, but underestimate empirical curves for noisy data in Figure ()), for both first and especially second descent. However, using suggested practical values a1 3 and 02 = results in practical VC- bounds that provide accurate modeling of double descent for this data, at various noise levels. See empirical results in Figure G
Next, we show experimental results for the same digits data set, when images are corrupted by random Gaussian noise. Here, the noise level is given by the standard deviation of the Gaussian noise ā 0, 0.1, 0.2. Empirical results Figure show that VC-bounds (with values a = 3 and 42 1) provide accurate modeling of double descent, at various noise levels. We conclude that using values a1 = 3 and 02 provide robust VC-theoretical modeling of double descent for noisy data.
In the following, we present the application of VC bounds on 4 different data sets adapted for binary classification, namely CIFARIO (cat automobile) (Krizhevsky & Hinton 2009), SVHN (digit vs 8) (Netzer et al. 2011), Fashion MNIST (dress vs coat) (Xiao et al. 2017). and epileptic seizure (Andrzejak et al. 2001). For the image-basee dataset, each sample is first transformed into grayscale image, and then rescaled to [0, 1] interval via min-max scaling. For the epileptic seizure dataset, the data procedures as the modeling of MNIST data set shown in section 2. All data sets has 800 training samples and 2,000 test samples. Modeling results are obtained for network with random ReLU features, trained using both SVM and LS classifier, are shown in figures 8. TO.
normalized
and unit standard deviation. We follow the same training
The last set of results shows the effect of varying the number of training samples on test error, for fixed-size network, using MNIST data set. This setting was used in Nakkiran et al. (2021) for demonstrating double descent. Results in Figure [2 show modeling double descent for digits data set, using fixed-size network with N=500 and N=1500. These results are obtained for the network with random ReLU features and are trained using LS classifier with 0j 3 and d2 = 1. They show very accurate modeling of double descent using VC-bounds, under this setting.
13

---

1250 1500 1750 2000 Under review as a conference paper at ICLR 2023
a) SVM Modeling Results
LS Modeling Results
0.3
0.2
Etoo
0.1
BBrer
0.2
0.0
140
120
109-
100
Nom Squared
20*
1.0
10a
Norm
101
900
Dimenston
600
VC D.Dimrstoo
100
500
750
3000
1250
1500
1750
2000
0
250
1250 1500 1750 2000 Number random ReLU teatures N
500
750
1000
Number random
Figure 8: Application of VC-bounds for Fashion MNIST coat dress data set using random ReLU features.
SVM Modeling Results
LS Modeling Results
1.0
1.0
Train trro Test tmor vC Bound
Tain Ertor
Test Enpr vC Bound
Enerr
Enner
0.5
0.0
400
10"
Norm Squared
200
107
10"
900
Dimension
400
600
VC
250 500 750 1000 1250 1500 1750 2000 250
500
750
1000
Number random ReLU features
Number random ReWU features
Figure 9: Application of VC-bounds for CIFAR10 cat vs automobile data set using random ReLU features.
14

---

Under review as a conference paper at ICLR 2023
a) SVM Modeling Results
b) LS Modeling Results
1.0
ETor
1.0
0.5
Enror
0.5
0.0
0.0
Support
10"
Norm Squared
Norm Squared
10a
100
1500
Dimercion
800
2000
VC Dimersion
600
800
500
200
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
5000
6000
Number random
random features
Figure 10: Application of VC-bounds for SVHN digit 5 vs 8 data set using random ReLU features.
SVM Modeling Results
LS Modeling Results
1.0
1.5
Trin Emer Test Emr Bound
Thein Enirr
Text troe yc Sound
Emar
0.5
1.0
Ermer
0.0
110
10'
Norm Square
20*
Norm Squared
10a
900
Dimanzion
240
VC Dimersion
600
150
0
500 1000 1500 2000 2300 3000 3500 Number of random ReLU features
4000
500 1000 1500 2000 2500 3000 3500 4000 Number random Relli features N
Figure 11: Application of VC-bounds for epileptic seizure data set using random ReLU features.
15

---

Under review as a conference paper at ICLR 2023
N=500
N=1500
Train Error Test Ener
Train Error
Test Error
Bound
VC Bound
Error
0.2
0.2
Squared
Norm Squared
Norm Squared
10a
10*
10'
10a
Estimated VC Dimersion
1500
Estimated Dimension
400
1000
500
1000
1500
2000
2500
1000
2000
2500
3000
training sample
training sample
Figure 12: Modeling double descent as function of the number of training samples, for fixed-size network, using values @1 = and 0g = 1.
APPENDIX B: SECOND DESCENT MODELING FOR TWO-LAYER FULLY CONNECTED NETWORK AND CONVOLUTIONAL NETWORK
In Section 3 of the main paper, showcase the application of VC-bounds for a I-layer fully nected network. We considered over- werrparameterized networks during second descent (when training error is close zero), and showed that, in this region: (a) VC-bounds can be applied for modeling second descent, and (b) the VC-dimension can be estimated as the norm squared of weights of the output layer. Empirical results shown in the main paper confirmed the hypothesis that in a single layer network, minimization of weights in the output layer effectively controls generalization. This appendix extends application of bo-ubusds two-layer fully connected network and convolutional LeNet-5 network (LeCun et al. 1998) for MNIST data set.
Consider fully connected network with N₁ hidden units in the first layer and N₂ hidden units in the second layer. We adopt the same experimental setting as in the main paper. The number of epochs set to 6000.
Figure 13 shows modeling results for a two-layer network, where N₂ is fixed at 10 and N₂ is varied. Figure 14 shows modeling results for a two-layer network, where N₁ fixed at 10 and N₂ varied. Both Figures 13 and 14 show training and test errors similar to the results of a one-layer network in Figure 5 in the main paper. In Figures bb) and [4),),, the region of second descent where the training error is less than 1 1% is on the right side of the dotted vertical line.
Next, we present VC-theoretical modeling of second descent for a convolutional network. We use the LeNet-5 architecture (LeCun et al. 1998), modified for binary classification problem by setting the number of output units to I. See Figure [3 showing the schematic of the modified LeNet-5 model, where the number of hidden unit N in the last hidden layer is varied (denoted by dark grey color). Figure T6(a) shows the error curve and VC-bound, along with the estimated VC-dimension, function of the number of hidden units N. Similar to multilayer network results, observe that VC-dimension (estimated as the norm of weights) decreases as the number of hidden units N increases. Figure [6(bb shows the error curve and VC-bound, along with the norm squared of weights, as function of the number of epochs, for N = 10 and N = 100.
Results in Figures 13 14 and confirm that VC-bounds can accurately model empirical test er- ror, further supporting our hypothesis that VC-dimension can be estimated as the norm squared of weights of the output layer during the second descent.
16

---

Under review as a conference paper at ICLR 2023
a
b)
N1 10
N; = 100
0.6
Tain Error
Than trror Error
Tain Era
Text Ennor
Test Bound
Bound
VC Bound
0.1
Stror
Sror
0.0
5.
Vc (CDimesion
Norm Squared
45
3.5
500
1000
1500
2000
1500
3000
4500
6000
Number hidden units
Number
eporhs
Figure 13: VC-theoretical modeling of second descent in two-layer fully connected network, with the second layer width N2 fixed at 10. a) Second descent as function of the first layer width N1- b) Second descent as a function of the number of epochs, for N₃ 10 and N₃ 100.
a) 0.2
b)
0.6
Error
0.4
Erer
0.1
Error
0.2
0.2
0.0
0.0
0.0
6
VC. UcDiimension
Norm Squared
Nom Square
3.5
15:00
1500
3000
4500
6000
1500
3000
4500
6000
Number hidden units No
Number opochs
Number of opochs
Figure 14: VC-theoretical modeling of second descent two-layer fully connected network, with the first layer width N₃ fixed at 10. a) Second descent function of the second layer width N₂. b) Second descent as a function the number epochs, for N₂ 10 and N₂ = 100.
17

---

Under review as a conference paper at ICLR 2023
1695x5
16810x10
Input
6028x28
6814x14
120
Output y
32x32
Convolution
Max Pooling
Linear
Hidden Unit
Convolution
Max
Pooling
Flatten
Schematic LeNet-5 architecture adapted for binary classification setting, where the number of output units is set to 1. The size of the last hidden layer N is varied.
Figure 15:
a)
b)
10
100
Tran Emor
Tain
Enor
Enorr
0.2
0.2
0.0
0.0
4.2
VC. D.Dimrssoon
Norm Squared
Norm Squard
3.4
4500
hidden units
epochs
spochs
Figure 16: VC-theoretical modeling of second descent for LeNet-5. a) Second descent function of the last layer width N. b) Second descent as a function of the number of epochs, for N = 10 and 100.
18


Reviews:
[{"review_id": "hB1U-_xbND", "reviewer": "Reviewer_4NbT", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "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.", "strength_and_weaknesses": "Strengths\n-------------\nThe 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.\n\nWeaknesses\n----------------\nThe 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). \nAlso, 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.\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WhBGSwHdHg5", "reviewer": "Reviewer_7rdX", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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.", "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. ", "strength_and_weaknesses": "Strengths:\n\n- 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\n\n- 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.\n\nWeaknesses:\n- 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:\n    - 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. \n    - 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.\n    - 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. \n\n- 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). \n\n\n[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).\n\n[2] Neyshabur, Behnam, et al. \"Towards understanding the role of over-parametrization in generalization of neural networks.\" arXiv preprint arXiv:1805.12076 (2018).\n\n[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).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "FKO0kfl6bPC", "reviewer": "Reviewer_Uf6C", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. ", "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. ", "strength_and_weaknesses": "Strength:\n\nThe 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. \n\nWeaknesses:\n\n1: 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. \n\nWithout giving details of the VC-theory, I cannot judge the correctness of the paper. \n\n2: 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.\nThe 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. \n\n3: 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.\n\n4: 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. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ErXXocgUeLX", "reviewer": "Reviewer_J8jr", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "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. \n", "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.", "strength_and_weaknesses": "The goal of the paper is certainly commendable; revisiting classical ideas may shed insights into recent empirical observations. \n\nHowever, 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.\n\nSecond, 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.\n\nThird, 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.\n\n[1] Bartlett, P. L. The sample complexity of pattern classification with neural networks: the size of the weights is more\nimportant than the size of the network. IEEE Transactions on Information Theory, 44(2): 525–536, 1998.\n\n[2] Bartlett, P. L.; Foster, D. J.; and Telgarsky, M. J. Spectrally-normalized margin bounds for neural networks. NeurIPS, 2017\n\n[3] Arora, S.; Ge, R.; Neyshabur, B.; and Zhang, Y.  Stronger generalization bounds for deep nets via a compression approach. ICML, 2018.\n\n[4] Neyshabur, B.; Tomioka, R.; and Srebro, N. Normbased capacity control in neural networks. COLT, 2015.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject