VC Theoretical Explanation of Double Descent
Authors: Eng Hock Lee
Vladimir Cherkassky
Venue: NeurIPS 2022 Submitted (2022)

Abstract: There has been growing interest in generalization performance of large multilayer neural networks, that can be trained to achieve zero training error, and yet they generalize well on test data. This regime is known as ‘second descent’ and it appears to contradict conventional view that optimal model complexity should reflect optimal balance between underfitting and overfitting, aka bias-variance trade-off. This paper presents VC-theoretical analysis of double descent and shows that it can be fully explained by classical VC generalization bounds. We illustrate application of analytic VC-bounds to 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 possible reasons for misunderstanding of VC-theoretical results in machine learning community.

VC Theoretical Explanation of Double Descent
Anonymous Author(s) Affiliation Address
email
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 test data. This regime is known 'second descent' and it appears contradict conventional view that optimal model complexity should reflect optimal balance between underfitting and overfitting, aka the bias-variance trade-off. This paper presents VC-theoretical analysis of double descent and shows that it can be fully explained by classical VC generalization bounds. We illustrate 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 possible reasons for misinterpretation of VC-theoretical results the machine learning community.
2
10
11
12
Introduction
13
14 There have been many recent successful applications of Deep Learning (DL). However, at present time, 15 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.
16
18 This contradicts conventional statistical wisdom that overfitting leads to poor generalization. This phenomenon has been systematically described by Belkin, et al. [I who introduced the appropriate terminology ('double descent') ) and pointed out the difference between the classical regime (first descent) and the modern one (second descent). This disagreement between the classical statistical view and modern machine learning practice provides motivation for new thcoretical explanations of the generalization ability of DL networks and other over-parannn parameterized estimators. Several different explanations include: special properties of multilayer network parameterization (2] choosing proper inductive bias during second descent [I] effect of Stochastic Gradient Descent (SGD) training
20
22
24
26
[6], and the effect of margin on generalization (7). The current consensus view on the 'generalization paradox' in DL networks is summarized below:
4 5), the effect of various heuristics (used for training) on generalization
27
28
29
Existing indices for model complexity (or capacity), such as VC-dimension, cannot explain generalization performance DL networks.
30
31
'Classical' theories developed in ML and statistics cannot explain generalization performance DL networks. In particular, classical VC generalization bounds cannot be used to explain double descent. Specifically, the ability of large DL networks to achieve zero training error (during second descent mode) effectively 'rules out all of the VC-dimension arguments as a possible explanation for the generalization performance of state-of-the-ae neural networks'
32
33
34
36
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

37 This paper demonstrates that these assertions are incorrect, and that classical VC-theorettiall results can fully explain generalization performance of DL networks, including 'double descent', for classifi- cation problems. In particular, we show that proper application of VC-bounds using correct estimates of VC-dimension provides accurate modeling of double descent curves, for various classifiers trained using stochastic gradient descent (SGD), least squares loss and standard SVM loss. The proposed VC-theoretical explanation provides many additional insights on generalization performance during first descent vs. second descent, and on the effect of statistical properties of the data the shape of double descent curves.
38
39
40
41
42
43
44
45
Next, we briefly review VC-theoretical concepts and results necessary for understanding generaliza- tion performance of all learning methods based on minimization of training error [8 9 10 [I]:
46
47
1. Finite VC dimension provides necessary and sufficient conditions for good generalization.
48
2. VC theory provides analytic bounds on (unknown) test error, as a function of training error, VC dimension and the number of training samples.
49
50
Clearly, these VC-theoretic results contradict an existing consensus view that VC-theory cannot
51
account for generalization performance of large DL networks. This disagreement results from misinterpretation of basic VC-theoretical concepts in DL research. These are few examples of such misunderstanding:
52
53
54
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' 3 In fact, it is well known that VC-dimension can be equal, or larger, smaller, than the number of parameters [8] M.].
55
56
58
Another common view is that "VC dimension depends only on the model family and data
59
distribution, and not on the training procedure used to find models'
(12). In fact, VC
80
dimension does not depend on data distribution [8] [1) Furthermore, VC dimension certainly depends on SGD algorithm [1]
61
For classification problems, VC theory provides analytic generalization bounds for (unknown) 63 Prediction Risk (or test error), as a function of Empirical Risk (or training error) and VC-dimension
62
64
(h) of a set of admissible models, aka approximating functions. That is, for given training data set
65 (of size n), VC generalization bound has the following form 8
4 4Rrm
Rest S Ram +
1 + V 1+
2
E
66
where 6 = a1 (1 (In
a22 h
+ - In 2) .7 min
This VC bound IT) holds with probability 1 17 (aka confidence level) for all possible models 68 (functions) including the one minimizing the training error (Rtrn). The second additive term in (I. called the confidence interval, aka excess risk, depends on both the empirical risk (training error)
70 and VC dimension (h). This bound describes the relationship between training error, test error and VC-dimension, and it is often used for conceptual understanding of model complexity control, i.e.
71
understanding the effect of VC-dimension on test error. Application of this bound for accurate modeling of double descent curves requires:
72
73
74
Selecting proper values of positive constants and 02 The worst-case values a1 = 4 and a2 2. provided in VC-theory [8 result in VC-bounds that are too loose for real-life data sets [II] For classification problems, we suggest using the values di 02 = 1. used for all empirical results presented in this paper.
75
76
77
78
Analytic estimate of VC-dimension. For many learning methods, including DL, analytic estimate of VC-dimension are not known. For example, for SGD style algorithms, the effect of various heuristies (e.g., initialization of weights, etc.) on VC-dimension is difficult (or impossible?) to quantify analytically.
79
80
81
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 8 9 M. Whereas
82

---

84 second descent corresponds to minimizing this bound when training error is kept at zero, using set a5 of models having small VC-dimension. This can be shown by setting the training error in bound (T)
86 to zero, resulting in the following simplified bound for test error during the second descent:
h1 π
Rist S E, where =
In
87
More formally, since VC bound (T) depends only on two factors, training error and VC-dimension, there are two different strategies for minimizing this bound [II]
89
For a set of functions (models) with fixed VC-dimension, reduce the training error. This strategy leads well-known classical bias-variance trade-off aka 'first descent';
90
91
For small (fixed) training error, minimize the VC-dimension. This strategy corresponds to second descent, when training error is zero.
92
93
These two strategies correspond to different methods for controlling VC-dimension, that have been known long before DL. For example, the second strategy corresponds margin maximization in SVM. Traditional learning methods typically implement a single strategy. whereas practitioners in DL observed the effect of both strategies when varying single hyper parameter, such network size or the number of epochs.
95
96
87
98
The main technical reason for misapplication of VC-theory, besides misinterpretation of VC- dimension, is that VC bound ( remains virtually unknown in the DL community. That is, all technical arguments suggesting that VC-theory is unable to explain double descent, are based on analysis of uniform convergence bounds 13]4111 16 17]. In such bounds, the confidence interval term, aka the excess error, is of the order O (v h//n) i.c. it does not depend on empirical risk (training error). However, VC-theory also provides more accurate uniform relative convergence bounds, such as VC-bound ( presented R 9 TO [T] where the confidence interval term also depends on the training error. So, whereas it is true that uniform convergence bounds cannot explain double descent, it can be fully explained by uniform relative convergence bounds.
99
101
102
103
104
105
106
107
Training of DL networks is based on stochastic gradient descent (SGD), which incorporates several heuristic rules ensure that the norm of weights remains small. These rules include: initialization of weights to small random values and re-normalization during training. Consequently, for large DL networks, the 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 only on network topology have found little practical use [11.
108
109
110
112
113
2
Application of VC Bounds for Modeling Double Descent
114
This section presents a VC-theoretical explanation of double descent for classification, for single- layer network shown in Figure The same network setting was used for analysis of double descent in recent papers 18 19 20
116
In this network, classifier is estimated in two steps:
118
First, input vector x is encoded using N nonlinear features. Commonly, random features (weak features) are used, such as random ReLU or Random Fourier Features (RFF);
119
120
Second, a linear model estimated in this N-dimensional feature space.
This simplified setting enables VC theoretical analysis of double descent, because the analytic estimates of VC-dimension are known. That is, since the network output is formed as a linear combination of N features, analytic estimate of VC-dimension for linear hyperplanes f(z,
122
123
124
(w2) + b is known g 9 10
h S min 2| +
125
This bound holds under the assumption that all training samples are enclosed within sphere of radius 1, Z-space. In summary, VC-dimension can be bounded by the input dimensionality (N), or by the norm of weights. These are two different mechanisms for controlling VC-dimension.
126
3

---

X1
W1
42
Zz
W22
g f (x, w)
Wy
Xd
ZN
Figure Single hidden layer network estimating a linear classifier in nonlinear feature space (Z-space).
128
The double descent phenomenon can be observed for various learning methods used to estimate weights w for the network structure in Figure I Next. present empirical results showing the application of VC bounds T and (3 for modeling double descent when network weights are estimated using SVM Least-Squares (LS) classifiers. For large networks trained using LS, when is larger than sample size (n), minimization of squared error is performed using pseudo-inverse, which finds solution corresponding to the minimization of the norm squared ||
130
132
134
In experimental results this section, double descent observed when the network size (N) gradually increased. Specifically, according to analytic bound (3):
136
When network size (N) is small, the VC-dimension initially grows linearly with N. This corresponds the first descent, traditional bias-variance trade-off.
138
For overparameterized networks (large N), VC-dimension is controlled by the norm squared of weights, leading to second descent.
139
140
We use two types of random nonlinear features [ 21). ReLU and RFF. Random ReLU features are formed as:
2, max ((v;, X), 0), i= 1,..,, N
where random vectors V1 ....... UN sampled uniformly from the range [-1,1]. Random Fourier Features (RFF) are formed as:
143
Z: exp (V-1 X)).
i i= 1= N
144
Where random ..,..., UN are sampled from Gaussian distribution with standard deviation o = 0.05. In all experiments, input (x) values were pre-scaled [0, 1] range, for both training and test data.
145
146
Following the nonlinear mapping X - Z, all z-values are re-scaled to [-1, 1] range. Such re-scaling performed satisfy the condition for bound (3). stating that all training samples in Z-space should be enclosed within a sphere of radius 1.
148
Training samples (z.
used estimate decision boundary in Z-space. Two different methods (LS and SVM classifiers) are used for estimating linear decision function f(z, w) = (wz) + 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 is set to 64 all experiments. Empirical test error is estimated using independent test set.
150
152
154 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 800, and test set size is 2,000. We have also used other data sets for modeling and observed similar results. See Appendix for additional results.
156

---

a) SVM Modeling Results
b) LS Modeling Results
0.0
500
Erro
Sugpor Wetors
0.4
400
Greer
300
0.2
200
100
10*
Norm Squared
Nom Squared
30>
10a
20*
150
100
600
400
50
200
0
200
800
1000
250
750 1000 1250
1500 1750 2000
Number rendom ReLLU features
Number random ReiUU Features
Figure 2: Application of VC-bounds for MNIST digit vs data set using random ReLU features.
a) SVM Modeling Results
Tran Enor VC Bound
0.2
b) LS Modeling Results
0.0
Enor Test VC Bound
Support Vectors
400
0.2
200
0.0
Norm Squared
10a
harms Squared
Narm Squared
10p
Korm Squared
107
10p
10k-
Estimated Dimension
Extimated Dimension
100
200
300
400
500
200
400
600
800
1000
Number random Fourter features N
Number of rendom Fourter features
Figure 3: Application of VC-bounds for MNIST digit 5 vs 8 data set using RFF.
158
Empirical results in Figures 2 and 3 show application of VC bounds to modeling MNIST data. They
159
show:
Empirical training and test error curves, a function of N ( the number of nonlinear features), along with VC-theoretical estimate of test error obtained via bounds (T) and (3).
161
These curves show that analytic VC-bounds explain (and predict) double descent;

---

163
The 'norm squared' of estimated linear model, as a function of the number of features N;
164
For SVM, we also show the number of support vectors for trained SVM model.
165
Modeling results for random ReLU and RFF features are similar, we only comment on results in Figure 2
166
187
For small N, VC-dimension grows linearly with N for SVM method. Empirical results show that first descent error curves can be explained by VC-bound (T), because the minimum of VC-bound closely corresponds to the minimum of test error. This can be clearly seen for LS classifier, and less obvious for SVM
168
189
170
171
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 (T. for both SVM and LS learning methods.
172
173
174
Whereas empirical results for both SVM and LS in Figure 2 are qualitatively similar, their double descent curves show different values of interpolation threshold N (where the training error reaches zero). For SVM, the value N* R 100 is achieved when the number of features equals the number of support vectors. For LS classifier, the interpolation point No xs 800 is achieved when the number of features equals the number of training samples.
175
178
177
178
The dependence of test error the norm of weights in large networks has been known to practitioners, and some limited theoretical explanation is provided in [T 22 23]. For example, [ [2] 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 of weights, and explain generalization performance for linear classifiers.
180
182
183
184
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. [12 investigated the effect of varying the number of training samples on test error, for a fixed-size DL network. In particular, they observed two double descent error curves for the same network trained using smaller and larger size training data, showing that during second descent, near interpolation threshold, the test error for network trained with larger data set is worse than for the same network trained on smaller data set. This phenomenon was called 'simple-wise non- non-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, as explained next. Note that for LS classifiers during second descent the shape of the 'norm squared' closely follows the shape of test error, according to VC bound (2). as evident in Figures 2
186
188
190
192
198
184
195
and Since for LS classifiers the interpolation threshold is given by training sample size, there is region near interpolation threshold, where VC-dimension for a smaller training
196
197
198
size is smaller than for larger training size. According to VC-bound (2). in this region of second descent we can expect a smaller (better) test error for smaller training size.
199
200
VC theoretical framework can also help to understand the effect of statistical characteristics of training 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 classifier using random ReLU features. We use digits data with corrupted class labels. The training set size is 800 (400 per class), and the test set size is 2,000. Figure F shows the effect of noise level the shape of double descent curves, for SVM and I.S classifiers. Results for both SVM and LS models show double descent curves, but their shape 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 LS model, we clearly observe first and second descent for both clean and noisy training data. For LS curves, the interpolation threshold (= 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 DD. Therefore, for SVM
202
203
204
205
206
207
208
209
210
211
212
213
214
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
215
interpolation threshold.

---

Random ReLU Features SVM
Random ReLU Features LS
0.4
0% Noise
0% Noise
Training Eroor
0.3
10% Noise
Noise
20% Noise
Training Error
0.3
20% Noise
0.2
0.2
0.0
0.1
0.4
Test Enrer
0.0
0.5
0.2
Error
0.3
0.0
Norm Squared
10a
0.2
10a
10a
10a
0.0
10a
Norm Squared
Support Vectors
600
400
200
10a
250
500
1000 1250
1500 1750 2000
250
500
750
1000 1250 1500 1750 2000
Number of random ReLU features
Number of random ReLU features N
Figure 4: Effect of noise double descent for MNIST data, for SVM and LS classifiers using random ReLU features.
217
The ability to generalize for noisy data can be explained by noting that during second descent VC bound (2) depends only 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 evident Figure for both SVM and LS).
219
220
221
Empirical results in Figure 1 also show that for noisy data, generalization performance during second descent degrades, relative to optimal first descent model. This is contrary to the popular view that DL networks usually provide superior generalization performance during second descent [I 12].
223
224
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 size nt,, generalization performance during second descent is likely to be good, because the VC bound on test error depends only on the ratio of VC-dimension to sample size (h/n).
225
227
3 Modeling Double Descent for Fully Connected Multilayer Networks
Empirical results for simplified network setting in Section 2 provide insights for generalization performance over- over--araman parameterized multilayer networks. Such general DL networks use SGD training that keeps the norm of weights small, that the model complexity is determined by the norm of weights, rather than the number of weights (parameters). However, direct application of analytic VC bounds to modeling double descent may be tricky, because need to address two challenging research issues:
230
232
234
1. How to estimate VC-dimension for general DL networks, where analytic estimates do not exist;
236
237
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 single complexity parameter, when all other tuning parameters are preset to 'good' values.
238
240

---

0.20
Error
Test Error
0.15
VC Bound
Error
0.10
0.05
0.00
Estimated Dimension
5.0
4.5
4.0
3.0
1000
1500
2000
Number of hidden units
Figure 5: Modeling results for second descent as function of network width (N).
N 10
N 100
0.5
0.5
Train
Error
0.4
Test Error
0.4
VC Bound
Bound
0.3
0.3
Enro
Error
0.2
0.1
0.0
0.0
6-
Estimated VC Dimension
Estimated Dimension
5
5-
4-
2000
4000
6000
2000
4000
6000
Number of epochs
Number epochs
Figure Second descent as a function of the number of epochs, for = 10 and 100.
For these reasons, the application of analytic VC bounds to general DL networks is difficult (or impossible?). However, it can still be done for restricted and well-defined network settings. this section, we consider fully connected network with a single hidden layer, as in Figure [ where the network weights both layers are estimated during training via SGD. this case, z-features are adaptively estimated from training data, in contrast fixed random features used earlier in Section 2
243
245
Let consider two factors (hyperparameters) controlling 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 function of these two factors have been extensively reported in
249
250
DL literature [ 12]. However, our purpose here is not to replicate such double descent curves, but to explain them using VC bounds [T] and 33). In order to make possible, we have to specify network
251
setting where VC-dimension can be approximately estimated. Therefore, we only consider modeling
253
for second descent, where training error is kept very small (or zero), and test error is bounded by (2).
This can be achieved when the number of hidden units N is large, the number of training epochs

---

255
large. So, our experiments intend to show application of VC bounds only in such restricted settings, where varying one complexity factor (for example, N) has an effect on VC-dimension and test error, according to bound (2).
256
258
Further, in order to estimate VC dimension, we hypothesize that under such restricted settings, during second descent, the norm of weights in the output layer can be used to approximate the VC-dimension of a neural network. The reasoning (behind this hypothesis) is that for such restricted settings the training error is zero, so a linear decision boundary in Z-space should have a large separation margin,
259
260
261
262
Le. VC dimension is controlled mainly by the norm of weights in the output layer. This assertion
263
appears to be supported by experiments for fully connected networks, trained on several different
264
data sets.
265
Next, we present empirical results for MNIST digits data, under the following experimental setting:
266
200 training and 2,000 test examples (of digits and 8);
Fully connected network using random ReLU activation function in hidden units (24]
268
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 is used during training.
269
Weights initialized, prior to training, using Xavier uniform distribution, following 22
271
Our design choices for SGD implementation mainly follows earlier studies II
272
Figure shows modeling results for second descent mode, as function of the number of hidden units (the number of epochs is set to 6000 in all experiments). The top part shows empirical training and test еπтог curves, and the VC-bound on test eтror, that closely approximates empirical test error. The bottom part of the figure shows the VC-dimension, estimated as the norm squared of the output layer weights (for trained network). Tigure[Jshove modeling results for second descent mode, as a function of the number of epochs (for networks with = 10 and 100 hidden units). Note that VC-bound and VC-dimension can be reliably estimated only in second descent mode, when training error is close to zero. This region, where training error is smaller than I 1%, is indicated by dotted vertical line. These results show that in the region where training error is very small, increasing
273
274
275
276
277
279
281
the number of epochs results is a small increase in VC-dimension and a slight decrease of training error. This is a particular form of peemorizaaiinncomplesse trade-off, implicit in VC bound ( when training error is very small (close to zero).
282
283
These results demonstrate applicability of VC bounds for modeling second descent in fully connected multilayer networks. 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 DL networks during second descent.
285
286
287
Summary
208
This paper provides a VC-theoretical explanation of 'double descent' in multilayer networks. We show that for simplified network structures where VC-dimension can be analytically estimated, VC generalization bounds can be applied directly to the model and predict double descent phenomenon.
290
292
VC-theoretical framework helpful for improved understanding of empirical results observed in DL, such as: the effect of various heuristics on generalization, relative performance of first and second descent, etc. Another important VC-theoretical insight that during second descent VC-dimension depends on the norm of weights. According to VC-theoretical explanation, second descent occurs when zero training error is achieved using an estimator having small VC-dimension, i.c. small norm of weights. This phenomenon is general, and it does not depend particular training algorithm or on a chosen parameterization (such as multilayer network). Therefore, double descent can be observed for other learning methods, such as SVM estimators, and not only for DL networks trained by SGD algorithm.
294
296
296
300
301
Empirical results presented in this paper contradict the consensus opinion that VC-theory cannot
302
explain prediction performance of neural networks. Possible future work in this area may investigate
VC theoretical modeling of double descent for low-dimensional data, and also for regression problems.
304
Note that for regression problems VC-theoretical bounds have a different form 8 9 10
and
these bounds have not been previously used for modeling second descent.
9

---

References
306
307
[1] Belkin, M., Hsu, D., Ma, S. & Mandal, S. (2019) Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 11 116(32):15844-15554
308
309
310
[2] Bengio, Y. (2009) Learning deep architectures for AI. Foundations and Trends in Machine Learning, 2(1):11127.
311
312
[3] Zhang, C., Bengio, S., Hardt, M., Recht, B. & Vinyals, O. (2021) Understanding deep learning
313
requires rethinking generalization. Communications of the ACM, 64(3):007-115.
314
[4] Neyshabur, B., Tomioka, R. & Srebro, N. (2014) In search of the real inductive bias: On the role of implicit regularization in deep learning, arXiv preprint arXiv: 1XXiv:4422.6614
315
316
[5]
Dinh, L.., Pascanu, R., Bengio, S. & Bengio, Y. (2017) Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028.
317
318
[6] Srivastava, N., Hinton, G., Krizhevsky, A., Sutskever, I. & Salakhutdinov, R. (2014) Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 1556)):192-11558
319
320
[7] Bartlett, P., Foster, D. & Telgarsky, M. (2017) ppectrally-normalinn margin bounds for neural networks. In Advances in Neural Information Processing Systems, pages 6241-6250.
322
323
88] Vapnik, V. (1998) Statistical Learning Theory. John Wiley & Sons, New York.
[9]
Vapnik, V. (1999) The Nature of Statistical Learning Theory, Springer.
325
[10] Vapnik, V. (2006) Estimation of Dependencies Based on Empirical Data, Second Edition.
328
Springer.
[1I] Cherkassky, V. & Mulier, F. (2007) Learning from Data, Second Edition, Iiley-nnterscience.
328
[12] Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B. & Sutskever, I. (2021) Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment, 2121.12).
329
330
331
[13] Schölkopf, B., Smola, A.J. & Bach, F. (2002) Learning with kernels: support vector machines, regularization, optimization, and beyond, MIT press.
332
333
[14] Tewari, A. & Bartlett, (2014) Learning Theory. Academic Press Library Signal Processing.
334
[15] Bartlett. P., Montanari, A. & Rakhlin, A. (2021) Deep learning: a statistical viewpoint, Acta Numerica.
338
[16] Koltchinski,, V. (2001) Rademacher penalties and structural risk minimization, IEEE Transac- tions on Information Theory, 1902-1994
337
[17] Sokolié, J., Giryes, R., Sapiro, G. & Rodrigues, M. (2017) Robust large margin deep neural networks, IEEÉ Transactions on Signal Processing, 65166:4426-44288.
339
340
[18] Belkin, M., Hsu, D. & J. Xu. (2020) Two Models of Double Descent for Weak Features, SIAM Journal on Mathmatics of Data Science, 2(4).
341
342
[19] Neal, B., Mittal, S., Baratin, A., Tantia, V., Scicluna, M., Lacoste-Julien, S. & Mitliagkas, I. (2018) A modern take on the bias-variance tradeoff in neural networks. arXiv preprint 180.0.181...
344
345
[0
Hastie, T., Montanari, A., Rosset, S. & Ryan J. (2019) Surprises in high-dimensional ridgeless least squares interpolation. arXiv preprint wrxiv:1903.085000
346
347
[21]
Rahimi, A. & Recht, B. (2008) Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pages 1177-1184,
349
[22] Belkin, M., Hsu, D., Ma. S. & Mandal, S. (2018) To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541- 549.
350
[23] Gunasekar, S., Woodworth, B., Bhojanapalli, S., Neyshabur, B. & N. Srebro. (2017) Implicit regularization in matrix factorization. In Advances in Neural Information Processing Systems,
352
pages 6151-6159.
10

---

354 [24] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L. & Desmaison, A. (2019) Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing systems, pages 8026-8037.
355
357
[25] Glorot, X. & Bengio, Y. (2010) Understanding the difficulty of training deep feedforward neural networks. In Proceedings of Machine Learning Reseach, pages 249-256.
359

---

Checklist
380
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
363
364
(b) Did you describe the limitations of your work? [Yes] We provide an explanation in section 3 that direct application of VC bound is possible only under restricted settings where analytic estimate of VC dimension are known.
385
386
(c) Did you díscuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
369
370
2. If you are including theoretical results...
371
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
372
(b) Did you include complete proofs of all theoretical results? [N/A] The paper does not contain any new theoretical concepts.
374
3. If you ran experiments...
375
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or URL)? [No] We have provided detailed description of dataset and experimental procedure in the main text.
377
378
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
379
380
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A] This is not relavent since we are only using small dataset.
383
384
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
386
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
389
390
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
381
392
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
394
5. If you used crowdsourcing or conducted research with human subjects...
385
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
396
397
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
400
12


Reviews:
[{"review_id": "y2SiEfoQDKh", "reviewer": "Reviewer_8Fpz", "summary": "The paper empirically investigates whether relative VC bounds can\nexplain the double descent phenomenon. To this end, random features \nof size $N$ are created and then a (regularized) least squares \napproach in the feature space is performed. For the resulting, \nempirically observed weights, the relative VC bounds (among other \nquantities) are plotted as function of $N$. The obtained curves reflect \nthe double descent phenomenon, at least for the unregularied case.\nIn addition, similar experiments are reported for NNs with one\nhidden layer.", "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.", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Unfortunately, the paper relies on a fundamental misunderstanding \nof VC bounds. Indeed, in these bounds, one first needs to FIX a \nclass of hypotheses that is INDEPENDENT of the data samples, which \nare then observed in a second step. For this reason, it does not make\nsense to use an estimate on the VC dimension that is obtained AFTER\ntraining (as done in the experiments via the norm of the weights), and for the same reason, the \ndiscussion on the top of page 3 is entirely pointless.  \nIn 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.\n\nThe entire setup somewhat reminds me to the so-called \"luckiness\"\napproach taken in the early 2000s, but there the goal was to first \nderive solid new bounds, which is completely missing in this paper.\n\nFinally, 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). ", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "MpM3VTTU2Rh", "reviewer": "Reviewer_vA1k", "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.\n\nTheir 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.\n\nThe 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.\n\n[1] Reconciling modern machine learning practice and the bias-variance trade-off. Belkin, Hsu, Ma & Mandal.", "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?\n\n2. 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.\n\nSocietal impact: N/A this is a theoretical work.", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n**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.\n\n**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.\n\n### Weaknesses\n\n**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.\n\n**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\".\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "41YoxQ23_HF", "reviewer": "Reviewer_Zr4x", "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.", "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).\nHow you can deal with this cases?\nCan't you show similar results using Rademacher or Local Rademacher Complexity?\n[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).\n[Belkin] https://arxiv.org/pdf/2105.14368.pdf", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- approach is sound and theoretical grounded\n- explanation of this phenomena by means of well known theory\n\nWeaknesses\n- there is actually nothing new theoretically\n- experimental result is limited", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject