Deep Learning: When Conventional Wisdom Fails to be Wise
Authors: Pierre Baldi
Venue: NeurIPS 2022 Submitted (2022)
Keywords: neural networks
deep learning
overparameterization
generalization
overfitting.

Abstract: A major tenet of conventional wisdom dictates that models should not be over-parameterized: the number of free parameters should not exceed the number of training data points. This tenet originates from centuries of shallow learning, primarily in the form of linear or logistic regression. It is routinely applied to all kinds of data analyses and modeling and even to infer properties of the brain. However,
we show that this conventional wisdom is completely wrong as soon as one moves from shallow to deep learning. In particular, we construct sequences of both linear and non-linear deep learning models whose number of parameters can grow to arbitrarily large values, and which remain well defined and trainable using a fixed, finite size, training set. In deep models, the parameter space is partitioned into large equivalence classes. Learning can be viewed as a communication process where information is communicated from the data to the synaptic weights. The information in the training data only can, and needs to, specify an equivalence class of the parameters. It cannot, and does not need to,  specify individual parameter values. As such, the number of training examples can be smaller than the number of free parameters. 

Deep Learning: When Conventional Wisdom Fails to be Wise
Anonymous Author(s)
Affiliation
Address
email
Abstract
A major tenet of conventional wisdom dictates that models should not be over- parameterized: the number of free parameters should not exceed the number of training data points. This tenet originates from centuries of shallow learning, pri- marily in the form of linear or logistic regression. is routinely applied to all kinds of data analyses and modeling and even infer properties of the brain. However, through a variety of precise mathematical examples, we show that this conventional wisdom is completely wrong In particular, we construct sequences of both linear and non-linear deep learning models whose number of parameters can grow to arbitrarily large values, and which remain well defined and trainable using a fixed, finite size, training set. In deep models, the parameter space is partitioned into large equivalence classes. Learning can be viewed as a communication process where information communicated from the data to the synaptic weights. The information in the training data only can, and needs to, specify an equivalence class of the parameters. It cannot, and does not need to, specify individual parameter values. As such, the number of training examples can be smaller than the number of free parameters.
2
one moves from shallow to deep learning.
10
12
14
15
18
Introduction
17
18 long held form of conventional wisdom is that in order to train a model with parameters one should have at least n training examples, and preferably more. The origin of this statistical "dogma" 20 stems from linear regression and other forms of shallow learning"] The soundness this dogma
19
21 appears to be obvious from our experiences with linear regression: in general examples are
22 necessary and sufficient order to solve system of linear equations v unknown variables.
result, the dogma is routinely repeated and used in myriads applications of statistics to modeling data 24 across all areas of human inquiry, often well beyond shallow learning, and to inspire a fear, if not disgust, for the so-called wer-paaameterrieed models. The dogma is also routinely used in variety www.eeooooppcccccclatiooosss for instance to infer properties or processing strategies for the human brain. Here we show, through variety of examples, that this central dogma is valid only for shallow learning and that it is completely wrong when it comes to deep learning. Hence, in deep learning it may not be unwise to get rid of the conventional wisdom entirely.
26 of "beckko-ttee--ovellppp"" "calculations,
28
30
1.1
The Origin of the Dogma
For the past three centuries, since the discovery of least square linear regression by Gauss and 32 Legendre in the late 1700s (e.g. (. of the most central dogma of statisties has been that a model
31
'The mathematically correct distinction between shallow and deep learning is whether there are hidden units/layers or not.
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

33
should not have more parameters than data points. There is little doubt that the origin of this dogma
34 lies in linear regression, or equivalently linear systems of equations where in general if there are n unknown variables one needs n. linear equations (or training examples) to uniquely solve the system. However, this not a characteristic of linear systems alone. The same holds true immediately for
35
36
37 logistic regression. Since the logistic function is monotone increasing, it has unique inverse and
38 by inverting the targets one can reduce logistic regression to a linear system. While this is true for
39 single linear or logistic neurons, the same result holds for a shallow layer of linear or logistic neurons, since in this case each neuron operates and learns independently of all the other neurons. Similar observations can be made for single-variabee polynomial regression. Thus, in short, the origin of the conventional wisdom can easily be traced back to shallow learning and basic results in linear algebra.
40
42
43
Not only the soundness of the dogma seems obvious from basic linear algebra considerations, but its violation in shallow learning leads to two kinds of problems: (1) an over- wver-parameterized shallow model is not well defined in the sense that its parameters are not uniquely determined by the data; and, as a result, (2) such model can overfit the data by achieving low error on the training data, while performing poorly on held out data. Finally, the widespread aversion for over-parameterized models stems also from our sense of elegance and simpliciy, as embodied in the principle of Occam's razor.
44
45
46
47
48
49
50
1.2
Applications of the Dogma
51
While the dogma makes sense for shallow learning situations, it is often applied deep learning situations. For instance, many articles have been published in the literature recommending that deep learning models ought have training sets that are 10 times ( or 50 times [2] bigger than the number of free parameters. Obviously these arbitrary, constant, and widely discording prescriptive multiplicative factors should be viewed with a grain of suspicion.
52
53
54
55
Another standard application of the dogma is to infer properties of complex, non-shallow systems, like the brain. For instance, Geoff Hinton and others like to point out that the human brain has on the order of say 10 synapses, while human lives last on the order of 3 x 10 seconds. Assuming one training example per second, even 1000 training examples per second, the brain does not have enough training examples to train its army of synapses. From this false premise, one may draw all kinds of conclusion from "the brain must be doing something special" to "the majority of synapses 62 must be hardwired".. However, as we shall see, all these conclusions are worthless: they may be false
56
58
59
60
61
63 or true, since they are derived from a false premise. The false premise is obtained by applying statistical principle, correctly observed in shallow learning situations, to deep learning situations.
64
2 Preliminary Evidence against the Dogma
65
86
Preliminary evidence that something may be wrong with the dogma comes from at least three directions: Bayesian statistical theory, statistical ensembles, and deep learning practice.
67
68
From a purely Bayesian perspective, selecting the complexity of model based the amount of training data makes no sense at all, as there is in general no relationship between the two. Using a prior that favors simple models may be convenient, or satisfy tradition, however there is intrinsic epistemological reason for selecting such a prior. If anything, a situation with few data points may be the sign that data are hard or expensive to acquire. In turn, this is possibly the sign of an underlying complex phenomena, which may call for a complex model rather than simple one. Using prior that favors models with few parameters is analogous the paradigm of searching for one's car keys at night under the only lamp present in a dark parking lot: there is no epistemoligical reason for the keys be under the lamp. But what about Occaam's 's razor? As noted in (TO] M. such a prior is not needed to implement Occam's 's razor which naturally emerges from the Bayesian framework. To
69
70
71
73
74
75
76
77
78 see this in a simple way, imagine having an overall class of models comprising two sub-classes of
79 models: simple models (S) and complex models (C). Imagine that priori one has no preference
80 between the two classes S and C, and likewise that within each class one has no preference among
81 the models in that class. Let and e denote the value of the constant prior probability shared by all
82 the models in class S and in class C' respectively. Thus the overall prior distribution must satisfy
s|S| + +c|C| =
2

---

Input layer
Hidden layer
Output layer
Input
Input #2
Output
Input #3
Input #4
Figure 1: A A(4,5, architecture.
where [S] and |C| represent the volumes of the corresponding classes. Because the complex models 84 have more parameters, in general |S] << |C). As result, we must have: s >> c. short, simple models will automatically have much higher prior probability, and this effect will tend to be reflected
86 also the posterior probabilities.
87 A second line of evidence against the soundness of the dogma comes from the widespread use, and recognized effectiveness, of statistical ensembles, where many different models are combined together, for instance through simple weighted averaging operation. This combination alone generally results deep overall model, even if the individual models are shallow. And even the number of parameters of each individual model satisfies the dogma, obviously as the number of models in the ensembles increased, there is a point where the overall model starts to violate the dogma. Perhaps surprisingly the parameterization aspect of ensembles does not seem to have systematically worried statisticians.
88
90
82
94
95
Finally, and perhaps most importantly. it has been observed several times that in deep learning practice that over- peeammrrmeter models can work well, with no significant sign of overfitting. However, this phenomena has been used either to criticize deep learning, or is regarded as some kind of oddity possibly requiring novel strategies for combating the over-fitting curse.
96
96
mystery (e.g. 112 13 S
89
Here we set out to prove why the conventional wisdom is simply wrong when it comes to deep learning. In particular we give several examples of large networks with many parameters that can be trained with far fewer examples in both the linear and non-linear cases. We consider primarily the supervised learning framework, but through the use of autoencoder architectures we show that the same basic ideas can be applied to the unsupervised, or semi-supervised learning frameworks. At the linear end of the spectrum of models, we look at deep, fully-connected ,linear networks. At the other extreme non-lineat end of the spectrum, we look at deep, fully-connected, unrestricted Boolean networks. And in the middle of the spectrum, we look at deep fully fully-connected networks of linear threshold gates.
100
102
104
105
106
108
We use the notation A(no, R....., n2) to denote deep feedforward architectures with n, units layer where the input layer layer and the output layer is layer L (Figure l).
Notation:
109
3
The Linear Regime
Deep feed-forward linear networks have been studied for quite some time (e.g. 4.7 b)) in the 112 context of least square linear regression. One of the main theoretical results is that, the fully- connected case, the error functions of these networks does not have any spurious local minima. All critical points where the gradient of the error function is zero are either global minima or saddle points. As a result, properly applied stochastic gradient descent will tend to converge to global minimum. The structure of the global minima and the saddle points can understood terms of
113
114
116
Principal Component Analysis (CS). Clearly, the depth of these models is increased the number

---

W1
W
WL1
W
y=Px
An A(I,...,1) 1) architecture with L single-layer neurons. There is single synaptic weight w; connecting neuron
Figure 2:
to neuroni. the linear case, with no biases, the y = Pr where is the product of all the synaptic weights. While the number of parameters can be arbitrarily large, single training example is sufficient to constrain the value of the multiplier. Gradient descent rapidly converges onto an optimal solution where the product of the synaptic weight has the optimal value: P = a/B where Faat)) and 3 [xx²)) (see text).
function given by
of parameters grow to infinity. But what are the requirements on the size of the corresponding training sets?
119
3.1
The Simplest Deep Linear Model
121 To begin with, we consider an architecture A(1, ... 1), with single linear neuron in each layer (Figure 2). For simplicity we assume that there no biases, but the same analysis easily be 123 extended to the case with biases. The weights are W1,.... wy and the neural network behaves as a multiplier, in the sense that given input æ the output simply:
y = Px with P II wi
125
This is deep linear regression architecture with L parameters. The supervised training data consists of input-target pairs of the form (2r () that provide information about what the overall multiplier should be. Taking expectations over the training data, let E(zx) easy to check that the error is convex in P and that at the
126
and E(x²) B. The error
128
the standard least square error. optimum must have 3P 0 or P = a/3. It can be shown (see (3) that, except for trivial cases, given any initial starting point, gradient descent, or even random backpropagation (feedback alignment), will converge global minimum satisfying P =aa3..
130
132
While the architecture has an arbitrary large number of parameters L, in principle a single training example is sufficient to determine the value of the correct multiplier. The value of the overall product P partitions the space of synaptic weights into equivalence classes: produce the same value P are equivalent. The training data need only to provide enough information for selecting one equivalence class, but not the value of the individual weights within the equivalence class. Thus there is manifold of equivalent solutions satisfying the optimal relationship P = a/B and the volume of this manifold grows with the number L of parameters. However the training set remain small as a single training example, a clear violation of the dogma.
134
the architectures which
196
138
140
Of course, here and everywhere else in the following examples, one may wonder what could be the purpose of having L layers, when a single layer could be sufficient to implement the same overall oututt function. There could be multiple purposes. The most obvious one is that the volume of the solutions grows with the depth of the architectures and this may facilitate learning. But in addition, one must also think about the possible constraints that may be associated with physical neural systems, as opposed to the virtualized simulations of neural systems we routinely carry on our digital computers using the likes of Keras, Py PyTorch, and TensorFlow. For example, even in the simplest linear case described above, imagine that the overall desired multiplier is P 210 1024
142
143
144
146

---

148
but that the individual synaptic weights connecting one neuron to the next are bounded in the [-2, +2] range. Then no architecture with less than 10 layers is capable of implementing the optimal input- output function. Deeper architectures are needed to implement the overall optimal function and to robustly distribute the load across multiple synapses.
149
150
151
152
3.2 Deep Linear Models with No Bottlenecks
153 At first sight, one may tempted to think that the example above is due to the fact that there is a single neuron per layer. However, this is not the case and exactly the same phenomena is observed for a linear regression architectures of the form A(n, n...., n) where all the layers have size n and the weights are given by matrices Wi,..., Wt. Again, in vector-matrix form, the input output relationship is given by:
155
156
157
y= Px with P= W-WW-1... W1
158
Again it is easy to see that this architecture has Ln parameters. The overall input-output function corresponds to singlen x n matrix P. But in order to specify such a linear map, we only need to specify the images the canonical basis of R", in other words, n training examples general position sufficient, again violating the dogma.
160
162
Note that this property remains true if the architectures also contains expansive hidden layers of size greater than or if the input and output layers have different sizes and all the hidden layers have size greater than the input and output layer (i.e. the hidden layers do not affect the rank of the optimal overall input-output function).
163
164
185
166
3.3
Deep Linear Models with Bottlenecks
In the previous two examples, all the layers have the same size, expansive. However it is easy to relax this assumption and consider compressive architectures. To begin with, consider a purely linear 168
compressive autoencoder architecture of the form A(n, m, n2), with m (Figure 3). In this case, the bottleneck layer imposes a rank restriction on the overall transformation. It is well known [4] that not only the quadratic error function of such an autoencoder has no spurious local minima, but all its critical points correspond, up to changes of coordinates in the hidden layer, to projections onto subspaces spanned by eigenvectors of the data covariance matrix. The global minima is associated with Principal Component Analysis using projections onto subspace of dimension m. Obviously one can include additional linear layers of size greater or equal to m between the input layer and the bottleneck layer, or between the bottleneck layer and the output layer, arbitrarily increasing the total number of parameters, but without affecting the essence of the optimal solution. The minimal training set to specify the optimal solution consists of m vectors of size n to specify the project hyperplane, providing another egregious violation of the dogma. Again there are large equivalence classes of parameters associated with the same overall performance (e.g. in the linear case with single bottleneck, we have P AB- = ACC-1 B; thus the overall map P is defined up to invertible transformations applied to the hidden layer). The results in 4 7 show that the same observations can be made for arbitrary fully connected deep lincar architectures (i.c. beyond autoencoders) and not only in the real-valued case, but also in the complex-valuee case (6)
170
171
172
173
174
175
178
177
178
179
181
183
185
All the previous examples correspond linear networks. Thus one may be mislead think that the analyses apply only to linear networks. Next we show that exactly the same phenomena can be observed non-linear deep architectures. Among the non- pon-linear model to be discussed, we will examine first the most non-linear model of all which is the unrestricted Boolean model, where each neuron implements a Boolean function, with no restrictions on the kinds of Boolean functions. An unrestricted Boolean neuron with n inputs implements function í with 2n parameters, since one
186
197
188
189
191
must specify one binary value for each of the 2n possible entries of the truth table of f. Then we will consider also the case of Boolean neurons implemented by linear threshold functions, or perceptrons.
5

---

A
m
B
n
Figure 3: A(n, m, n) compressive (m n) autoencoder architecture. In the linear case, the transformations and correspond to matrices the overall linear transformation given by: y ABr.
4
The Non-Linear Regime: Unrestricted Boolean Model
194
4.1
The Simplest Deep Non-Linear Model
We can use the same architecture A(1...,, 1) as in the first example above. In the Boolean unrestricted model, each Boolean function from one neuron to the next either the identity or the negation (Boolean NOT function). So there is binary degree of freedom associated with cach layer and again the number of degrees freedom grows linearly with the depth. The overall input-output function is either the identity, the negation, and single training example is sufficient to establish whether the overall function ought to the identity or the negation of the identity. If the architecture number of negations the overall input-output function is the identity, and if the architecture contains and odd number of negations, the overall input-output function is the negation.
196
198
200
contains
202
203
Thus again the dogma is violated.
204 To get a slightly more interesting non-linear example, we can use the same architecture A(I,... ......... 1) in the first example above, with L weights Wi...., Wy. The difference is that all the neurons have a non- non-lineee linear activation function g(x) = x² (more generally we could use for instance g(z) = z²). Thus the overall input-output function is given by:
206
y = (W (w2w)))1)) .....)² .2. w Wi ... w
2L 2
208 or
= 2L with P=
II
W 2L 26+2
209
Thus in this case the multiplier realized by the architecture is positive. Again the number of parameters is L. and it can be arbitrarily large. As in the linear case, single training example of the form (x, sufficient to determine the multiplier P, with a manifold of equivalent solutions corresponding to parameters satisfying P= w 2L-21+2 a/ with this time a = E(tx²) and = ),, when > 0.. If a < 0, the optimum is obtained for P = 0 which can be achieved by having at least one of the weights of the architectures equal to zero. short, in both examples treated
211
212
214
in this subsection, the dogma is again violated.

---

216
4.2
Deep Non-Linear Models with No-Bottlenecks (Unrestricted Boolean)
217
Consider an architecture A(mo....,, n2) where each neuron can implements any Boolean function of the neurons in the previous layer. The error function is the Hamming distance between target and output vectors. For simplicity, let us first assume that all the layers have the same size n. The overall input-output function is Boolean map from H to Hi where HH denotes the n-dimensional hypercube. This architecture has L parameters, since each unrestricted Boolean neuron with imputs has 2n free parameters. The overall input-output map can be specified using only n2" examples. It can easily be implemented with 0 error through a large class of equivalent networks. As the number of layers L goes to infinity the number of parameters goes to infinity, while the number of required training examples remains fixed and is determined entirely by the size of the input and output layers. This
218
219
221
223
225
226
easily be generalized to Boolean unrestricted architecture of the form A no. nz); as long as there are no bottleneck layers. In such an architecture, the total number of
227
parameters is given by: Σ n122h-1. The number of necessary and sufficient training examples needed to specify the overall input-output funetion is given by: n1,2%0, and thus again the dogma violated. The case with bottle-neck layers is treated below.
229
231
4.3
Deep Non-Linear Models with Bottlenecks (Unrestricted Boolean)
232
For simplicity, consider first unrestricted Boolean compressive autoencoder with architecture A A(n, m, n) and m < n. The error function is the Hamming distance between the input vector and the oulput vector. The hidden layer can have 2nh states. Thus if the number of training examples is at most 2mh it can be realized by the architecture with O Hammiing distortion, since every input can be mapped to unique hidden representation and the corresponding representation can be mapped back to the same input using unrestricted Boolean gates. Obviously if additional layers of size at least m are added between the input layer and the hidden layer, or between the hidden layer and the output layer, the number of parameters can be arbitrarily increased, while maintaining the same fixed training set and the ability to implement exactly with no Hamming distortion. Thus in this regime the dogma is again violated.
233
234
235
236
237
238
239
240
In the more interesting regime where the number of training examples exceeds 2nh then there must be clusters of training examples that are mapped to the same hidden representation. It is easy to see that for optimality purposes the corresponding representation must be mapped the binary vector closest to the center of gravity of the cluster, essentially the majority vector, in order to minimize the Hamming distortion. Thus, in short, in this regime the optimal solution corresponds a form of
243
244
245
246
247
optimal clustering with respect to the Hamming distance with, in general, 2n clusters. As back of the enveloppe calculation, assuming the clusters are spherical, these can be described by providing two points corresponding to a diameter. Thus in principle a training set of size 2 x 2m = 2 could suffice. The number of parameters of the architecture is given by: m22 + n22 which far exceeds the number of training examples. And even without the assumption of spherical clusters, it is clear that the number of parameters far exceeds the number of training examples, and that the gap can be made as large possible, just by adding additional layers of size at least between the input and the hidden layer, or the hidden layer and the output layer. Thus again the dogma is grossly violated.
248
249
250
251
252
254
255
Finally, we turn to deep non-linear architecture where the neurons are linear or polynomial threshold gates. Linear threshold neurons, or perceptrons, are very similar to sigmoidal (e.g. logistic) neurons.
256
5
The Non-Linear Regime: Linear or Polynomial Threshold Gates
257
258
Here each neuron in the architecture is linear or polynomial threshold function of degree d. In the linear threshold case (d = 1). any neuron with inputs x (Z1...., produces an output equal to sign(E, w;2x)) in the -/+ case; or H H(E: w,2;)) in the 0/1 case, where H denotes the Heaviside function. Such a neuron has n synaptic parameters. In the polynomial case of degree d,
259
260
261
the output of a neuron has the form sign(p(x)) in the -/+ case; or Hy(()) in the 0/1 case, where p(x)= = p( ,n)) is a polynomial of degree d. The number of parameters of polynomial threshold neuron increases accordingly. As usual a bias can also be added or, equivalently, one of the
262
264
input variables is considered to be constant and equal to 1.
7

---

286
5.1
The Simplest Deep Non-Linear Model with Linear or Polynomial Threshold Gates
267
We can use the same architecture A(1...., 1) as in the first example above. Linear or polynomial threshold neurons can realize the identity and the negation, depending on whether the corresponding
268
269
incoming weight is positive or negative. So the result here is similar to the Boolean unrestricted
270
case. For instance for linear threshold gates, without the bias, the number of parameters is equal to L.
271
The number of negative weights determines how many negations are present in the chain. A single input-ouput example determines whether the overall chain should be the identity or the negation. Thus again the dogma is violated.
272
273
274
5.2
Deep Non-Linear Models with Bottlenecks (Linear or Polynomial Threshold Gates)
275
We can again start with a compressive autoencoder architecture with shape A(n, m, ni) and m < n and linear threshold neurons with the Hamming emrrr function. In the most interesting case where the number of examples exceeds 2mh then the optimal solution corresponds to the optimal approximation to the optimal Hamming clustering that can be achieved using linear threshold gates. The number of parameters of this architecture is 2nm which is not necessarily less than the number 2 of required in the similar previous examples, the number of parameters can be increased arbitrarily by adding additional layers of size
276
277
279
training examples, under the spherical cluster assumption. However,
281
282
at least m between the input and the hidden layer, or between the hidden layer and the output layer. Thus once again there are large equivalence classes in parameter space (e.g. applying permutations to the neurons in given layer) and the dogma is grossly violated.
283
6
Discussion
285
286
The conventional dogma that models ought to have less parameters than the number of training examples is a mere product of shallow learning. It arises, and should be applied, only in shallow learning situations. As soon as one moves to deep learning situations, the dogma becomes non-sense and all the expectations it creates are simply wrong, even in the linear case. It is simply time to think about deep models in a different way, without the expectation that over pee--araamttriization must necessarily lead to over-fitting. This is not to say, of course, that over parameterized deep learning models cannot overfit, but expecting them to do so just because they are over-parmnn vver-parmaterized unwise and unnecessary.
287
288
289
290
291
292
293
Over- parameterized models tend to partition the parameter space into large equivalence classes. All the parameter settings within one class are equivalent in terms of overall performance. Neural learning can be viewed as communication process where information is communicated from the training data to the synaptic weights. The training data needs to contain enough information to select
285
296
297
298
one of the equivalence classes, but not any particular setting of the weights within that class. Thus the information needed to specify one equivalence class is much less than the information required
299
300
to specify a particular setting of the weights. And this explains why the number of data points can be much less than the number of parameters. Furthermore. the structure of the deep models and the partitioning into equivalence classes is such that it is not even possible for the training data to be able
301
302
303
to specify each individual weight of the architecture. This is because the system cannot distinguish between two different settings of the parameters within the same equivalence class. For instance,
304
once the optimal class is achieved with a particular setting of the weights, the gradient of the error zero and there no way of exploring or distinguishing other optimal architectures in the same equivalence class.
306
307
308
Shallow learning, in particular linear regression, already contains many of the central themes of machine learning: from the use of a parameterized family of models, to model fitting by error minimization, to prediction and so forth. However, when transitioning to deep learning, linear regression is misleading in three major aspects. First, it has an analytic closed-form solution. Second, it is interpretable (or visualizable, at least in low dimensions). Third, requires that the number of training examples be equal or even exceed the number of parameters in order to completely determine
309
310
312
313
314
the solution. The first two points are now well established and accepted. We use stochastic gradient descent for deep learning model fitting and almost no one cares about not having a closed-form analytic solution. Likewise, no one expects to be able to easily visualize complex non-linear surfaces
316
in high nigh-dimensional spaces, although many are still working on various other issues related to
8

---

318
interpretability. However, we are still struggling with the third point. It is time to move on this front too.
319
320
should be clear from the examples presented that one of the emergent characteristies of over- parameterized regimes is the existence of large equivalence classes in parameter space, all associated with roughly the same level of overall performance. The training data needs only to provide enough information select one of the equivalence classes (at the relevant quantization level), and not
322
323
324
to specify the value of each one of the parameters. Reflecting back on the human brain, most mature human brains can pass the Turing test and achieve some form of general intelligence using architectures that are similar, at least at the macroscopic level, and at the level of the basic hardware components (e.g. pyramidal cells), but presumably with significant differences the level of individual synapses.
325
328
327
328
Finally, there is the question of when deep architectures overfit the data. The results presented here provide a clear answer. Consider an architecture with w parameters. At the proper level of quantization of the weights and the error function, the architecture may partition the space of weights into e equivalence classes, Thus log, bits are needed to specify one of the equivalence classes. If the training data provides less than log, e bits of information, then it does not contain enough information
330
331
332
333
334
to select a relevant equivalence class and overfitting may occur. If the training data provides log, bits of information to select an equivalence class, then there is no overfitting and providing more data is not necessary. In the case of a classification architecture with independent binary inputs of length
335
338
337 n, k training examples contain on the order of kn bits of information. Thus the important question
not whether k z w (conventional wisdom) but whether kn Ra log2
References
340
[1] Yaser S Abu-Mostafa. Hints. Neural computation, 7(4):639-671, 1995.
[2] Ahmad Alwosheel, Sander van Cranenburgh, and Caspar G Chorus. Is your dataset big enough? sample size requirements when using artificial neural networks for discrete choice analysis. Journal of choice modelling, 28: 187-122 2018.
342
[3] P. Baldi. Deep Learning in Science. Cambridge University Press, Cambridge, UK, 2021.
[4] P. Baldi and K. Horiik. Neural networks and principal component analysis: Learning from examples without local minima. Neural Networks, 2(1 (1):5355,,, 1989.
346
347 [5] P. Baldi and K. Hornik. Learning in linear networks: a survey. IEEE Transactions on Neural Networks, 644):837-858, 1994. 1995.
348
349
[6] Baldi and Z. Lu. Complex valued autoencoders. Neural Networks, 33:136- 147, 2012.
350
[7] Pierre Baldi. Linear learning: Landscapes and algorithms. Advances in neural information processing systems, 1, 1988.
[8] Abdulkadir Canatar, Blake Bordelon, and Cengiz Pehlevan. Spectral bias and task-model aligmment explain generalization in kernel regression and infinitely wide neural networks. Nature communications, 12(1):1-12, 2021.
353
355
[9] Adrien Marie Legendre. Nouvelles méthodes pour la détermination des orbites des cometes. F. Didot, 1805.
356
[10] D. J. C. MacKay. Bayesian interpolation. Neural Compulation, 4:415-447, 1992.
[1I] J. C. MacKay. A practical Bayesian framework for backprop networks. Neural Computation,
359
4:448 472, 1992.
360
[12] Terrence J Sejnowski. The unreasonable effectiveness of deep learning in artificial intelligence. Proceedings of the National Academy of Sciences, 1 11748))300333300
2020.
382
[13] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Commuiicatinns of the ACM, 64(3):107- 115, 2021.
383
364

---

Checklist
385
366
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
368
contributions and scope? [Yes]
369
(b) Did you descrihe the limitations of your work? [Yes]
370
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
372
373
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
375
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
378
379
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
380
381
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
382
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
384
385
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]
387
(b) Did you mention the license of the assets? [N/A]
388
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
390
(d) Did you discuss whether and how consent was obtained from people whose data you're ro using/curating? [N/A]
381
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
383
394
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
396
387
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
398
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
389
10


Reviews:
[{"review_id": "xC8yt5DgQO", "reviewer": "Reviewer_EpQS", "summary": "The authors revisit the problem of overfitting to data set and construct an example where neural networks overfit to their training data without it affecting their performance. The authors hypothesise that this effect arises because the data only specifies parameters up to a certain equivalence class, rather than specifying all of the parameters exactly.\n", "questions": "See above.", "limitations": "See above.", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Understanding how neural networks can obtain good test error while interpolating their data is a key problem for deep learning theory and has seen a lot of activity recently, so the authors are studying a timely topic.\n\nHowever, I'm afraid there are serious issues with the premise and the presentation of the article. The introduction reads as if over-parameterisation was still considered harmful in machine learning, when in reality the advantage of over-parametrization in large neural networks has long been recognised, for example in the original bias-variance trade-off paper by Neman et al. (Neural computation 4 (1), 1–58, 1992), and of course in the more recent literature on large neural networks (Neyshabur et al. '15, Zhang '16). To say that \"the dogma is routinely repeated and used in myriads applications of statistics to modeling data\" or to talk about a \"widespread aversion for over-parameterized models\" is simply not warranted, especially in the context of NeurIPS.\n\nTo go on and claim that \"many articles have been published in the literature recommending that deep learning models ought to have training sets that are 10 times or 50 times bigger than the number of free parameters\" is downright misleading, even if the authors managed to find two articles supporting these claims (once of which dates from 1995...)\n\nReading the article further, it becomes quickly clear that the authors are not aware of the enormous amount of recent work that analyses benign overfitting and the related double descent phenomenon in neural networks (see the two references above) and in random feature regression, where this effect is well-studied and understood. I am providing a few references with a focus on the theory below.\n\nI would therefore invite the authors to revisit their results in light of the recent experimental and theoretical findings, and to resubmit their article afterwards.\n\n- Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless\nleast squares interpolation. arXiv preprint arXiv:1903.08560\n- Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and\ndouble descent curve. arXiv preprint arXiv:1908.05355\n- Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign over\u001btting in linear regression.\nProceedings of the National Academy of Sciences, 2020\n- Deep learning: a statistical viewpoint. arXiv preprint arXiv:2103.09177, 2021.", "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": "qIlDLrjDpej", "reviewer": "Reviewer_38Gz", "summary": "In this paper, the authors stipulate that a transition from deep to shallow learning **necessitates** discarding the practice of having a larger training set over the number of model parameters. The authors state that this practice is derived from the statistical learning theory work based on linear models. \n\nThe authors then proceed to justify this point through a set of general inspections of simplified deep linear & non-linear models.", "questions": "N.A.", "limitations": "- As noted in the **Weaknesses** section above, the authors do NOT provide a thorough argument for their claim that a transition from deep to shallow learning necessitates the obvious choice of residing in the over-parameterized regime.\n\n- The figures provided are all too rudimentary and add little value to the work itself\n\n- There exists no formal theoretical results on the rate of convergence to a global optima w.r.t. training time and a subsequent analysis of whether attaining such a solution seems feasible under practical settings\n\n- There already exist long-established works on linear models, showcasing the phenomenon of double-descent in the test error. As to how the authors formally unify that seemingly contradictory viewpoint with their claims here\n\n[1] Statistical mechanics approach to early stopping and weight decay, *S. Bös*\n\n[2] Generalization ability of perceptrons with continuous outputs, *S. Bös, W. Kinzel, and M. Opper*\n\n[3] Avoiding Overfitting By Finite Temperature Learning and Cross-Validation, *Siegfried Bös*", "rating": 2, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**: It has been difficult to determine the exact strengths of this work.\n\n**Weaknesses**:  \n1. While the aspect of over-parameterization in DNNs is yet to be fully understood and is a subject of heavy investigation over the past few years, the authors completely fail to acknowledge the vast literature already existent on this topic\n\n2. **Most notably, the authors fail to clarify the novelty of their work over this existent literature**\n\n3. The authors claim that the practice of working in the under-parameterized regime even for DNNs is drawn from the observation that to solve for the values of *p* network weights, one would need an equal no. of parameters. This is to me a highly misconstrued understanding, as the practice is derived from the observed bias-variance tradeoff, itself explained from learning theory perspectives. \n\nSpecifically, given the increasing test error past an optimal model complexity of shallow NNs, it was understood that a continuation of the increase in model complexity can only worsen the generalization performance. In that light, the phenomenon of double-descent was definitely surprising\n\n4. Contrary to the authors' broad claim here, the work of [1] argues that it is still possible for over-parameterized models to perform poorly under certain training circumstances, hence a blanket argument for over-parameterization in DNNs has to be made with some caution, which is not provided in this work\n\n5. The authors provide very limited well-founded empirical and/or theoretical results to back their main claim. For e.g. in their analysis using a highly simplified over-parameterized deep linear network, the authors argue why a single example is in principle *enough* to train the setup. This is an inaccurate claim for the following reasons:\n\n- in an over-parameterized setup, there exists a multitude of network weight choices satisfying the global minima configuration each having a different generalization property. As to which one should be and is selected from this set of choices so as to achieve successful model training is left totally unanswered by the authors\n\n- it is understood and as is noted, that the landscape of a deep linear model does not contain any local minima. Nevertheless, saddle points exist and given the non-linear learning dynamics of the network weights, the authors do not put forth a method of how to escape a saddle point with the widely used gradient-based optimization methods\n\n- In the case of a noisy label, the exact fitting to the single training point is detrimental for generalization purposes and hence arguing for why over-parameterization *makes sense* in such a model regime is quite naïve\n\n- The work fails to provide any new theoretical estimate on the amount of over-parameterization necessary, c.f. [2]\n\n[1] Bad Global Minima Exist and SGD Can Reach Them, *Shengchao Liu, Dimitris Papailiopoulos, Dimitris Achlioptas*\n\n[2] A Convergence Theory for Deep Learning via Over-Parameterization, *Zeyuan Allen-Zhu, Yuanzhi Li, Zhao Song*", "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": "jwuB4ms9-dJ", "reviewer": "Reviewer_6YoB", "summary": "In this work, the authors explore the question of why overparameterized models learn well, despite the fact that classical/traditional statistics knowledge suggests that having more model parameters than datapoints is harmful for generalization. They develop a few cases where overparameterized models provably generalize well:\n\n* Deep linear networks\n* Deep boolean networks\n* Deep non-linear networks\n\nIn some cases, the optimal number of parameters can be shown to be greater than the number of training datapoints.", "questions": "Do any of the \"dogma violating\" situations in the paper have different properties from the ones already reported in the literature?", "limitations": "Limitations and impact adequately discussed.", "rating": 2, "confidence": 5, "soundness": 4, "presentation": 1, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strongest part of the paper is the explicit construction of some of the examples; they would be very good for lectures/problem sets in introductory ML courses due to their simplicity.\n\nHowever, overall the phenomenology of overparameterized networks and generalization has been well studied, particularly in the last few years. The literature on \"double descent\" is one major example. See papers like:\n\nhttps://www.sciencedirect.com/science/article/pii/S0893608020303117\nhttps://proceedings.mlr.press/v119/adlam20a.html\n\nPapers like this investigate some of the root causes of the success of overparameterization, both empirically and theoretically. This literature has not been engaged with in the paper.\n\nSimply developing some specific examples where overaparameterized models have good generalization is not a novel or impactful contribution to the field. This phenomenology has been known since the advent of deep learning, and as discussed above the origins of this phenomenon have been very well (and quantitatively) studied in more detail than this paper.", "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": "a_ERlhoSgSN", "reviewer": "Reviewer_bnfh", "summary": "The paper discusses the widely mentioned heuristic, that the number of parameters of a statistical model should not be larger than the number of training data points. By analyzing a sequence of simple “deep, layer-wise, feedforward” models the paper shows that there is no straightforward relationship between the number of parameters and the functional expressivity (complexity) of a model. Accordingly, deep models can easily be constructed where the number  of datapoints to uniquely determine the input/output function is arbitrarily lower than the number of model parameters. The main idea is that transformations involving many layers can often be collapsed into a transformation with a single layer that is appropriately constructed - the number of parameters of that single layer determines the required number of training data points. Adding more and more parameters via deeper layers then allows to arbitrarily inflate the model’s parameter count. The argument also goes through in essence when layers have different widths (by focusing on the most narrow layer), and in case of non-linearities between layers. The paper contains no empirical evaluation.", "questions": "**Questions and minor comments:**\n\nIt would be great to see the analysis in 5.2 for MSE (regression), not the Hamming error function. How would the clustering argument look like in this case?\n\nThe paper somewhat fails to explain why we tend to see statistical models with eye-watering parameter counts in practice. Following the construction in the paper, many of these parameters should be superfluous (any layers wider than the bottleneck should be more or less reducible to the bottleneck-width). Yet, many rounds of architecture optimization (via humans or automated procedures such as neural architecture search) have left us with models with superfluous and redundant parameters. Work such as the Lottery Ticket Hypothesis, and results in network compression (where often >90% of parameters can be removed after training, but not before) suggest that having more parameters than necessary to implement the desired functional input/output relation might be crucial for learning. This is mentioned in passing in the paper, but I think this question lies at the heart of one of the big riddles in deep learning: the question is not ‘why do we use more parameters than datapoints’ (which is not a very meaningful question as pointed out in the paper), but ‘why do we need way more parameters during training than to implement the desired final function’? I think it would be nice to add a bit more discussion along these lines to the paper.\n\nIn the mathematical examples given in the paper over-fitting is not possible. The examples simply show the required number of datapoints to determine the correct parameter equivalence class for a given model architecture. For over-fitting to be possible the discussion would need to be expanded to e.g. held-out regions in the data manifold (test-set generalization from a training set that is insufficient to fully determine the parameter equivalence class) or noisy training data. This would probably, I think, lead to a formalism similar to SLT.\n\nLines 68-86: Bayesian Occam’s Razor - the discussion in the paper is a bit imprecise (I personally really like the discussion and particularly the illustration in MacKay’s textbook Chap. 28, p. 344, perhaps it can serve as inspiration to overhaul the paragraph in the paper). The discussion could be more clear by associating model complexity with the ability to implement a large set of functions (regardless of the number of parameters, and regardless of the functional complexity of a single function under the model; the latter does not even have a well-defined meaning in the framework). \n * The epistemological reason to prefer a simple model over a complex one in light of few datapoints is then that a small number of datapoints can only be used to select one out of a small number of functions - a small number of possible functions is what corresponds to a simple model. In contrast a complex model can implement a larger set of functions, and selecting the right one necessarily requires more information / data points. This is not to say that the individual functions implementable by the simple model cannot have “complex functional form”. E.g. two models could be polynomials of degree 10, but the simple model only considers coefficients in $[-1, 1]$ whereas the complex model considers coefficients in $[-100, 100]$. The functional complexity of any particular function is the same under both models.\n* The second sentence in line 83 (continuing to 84) contradicts the main message of the paper. The paper generally argues that the number of parameters is not related to the complexity of a model (the set of possible functions implementable by the model) - so the inequality in line 84 would not hold. Again, I think this seeming contradiction can easily be resolved by being more careful: the difference between a simple and a complex model is not the number of parameters, but the set of implementable functions under all possible parameter settings. \n", "limitations": "The paper does not address non-feedforward architectures such as e.g. ResNets and RNNs, but this is a minor detail.\n", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Pro:**\n * The paper is very easy to read and follow and the main argument is built in logical, consecutive steps.\n * The technical arguments in the paper are correct.\n * The paper is self-contained, and does not require extensive knowledge of sub-fields of ML.\n\n**Con:**\n * The non technical writing is highly opinionated, criticizing a perceived “dogma” dozens of times in the text (the word dogma appears 29 times in the paper). This is not a problem per se, but makes the manuscript more suitable for an op-ed or commentary article, which is a format not supported by NeurIPS.\n * The main argument is that functional complexity (expressiveness) of a model is independent of the number of model parameters - unfortunately this is never spelled out with clarity in the paper. This should be obvious after an undergrad course in statistical modeling and ML - however, I agree that the “dogma” has been fairly widely mentioned in the deep learning literature, and to this day the number of parameters is often taken as a proxy for model complexity in deep learning (e.g. in “scaling laws”).\n * The main argument above has been addressed formally in various frameworks, perhaps most relevant to the current discussion in statistical learning theory, where model complexity is measured via the VC dimension (instead of parameter count) and learnability bounds that relate the required number of training datapoints to bounds on test error (in the i.i.d. setting). This is not discussed at all in the paper.\n\n**Verdict:**\nThere is some merit to pointing out the (rather obvious) fact that statistical models, particularly deep, layer-wise, feed-forward architectures can be fully determined from datasets with fewer datapoints than model parameters. This necessarily implies equivalence classes of solutions (which I think is also interesting to point out). However, the current style and tone of the manuscript are more suited for a short opinionated or commentary piece, or perhaps a peer-reviewed blog-post (which another conference recently introduced) - neither of these formats are supported by NeurIPS. I therefore currently argue in favor of rejection because of a lack of novelty, significance, and technical depth that is expected from a typical NeurIPS original research paper. Having said that, I did enjoy reading the paper (though criticizing “the dogma” could perhaps be toned down a bit), and would encourage the authors to find an appropriate outlet.\n\n**Improvements:**\nTo strengthen the work and add technical depth here are some suggestions (though one advantage of the article is that it is very easy to read because it is technically simple; so the suggestions here are aimed at adding enough “meat” for a conference publication, which might not be the right format for this article after all):\n * A thorough discussion of the (non-)relationship between functional complexity (and how to measure that) and the number of parameters of a statistical model, as well as the implications for learnability and generalization. I personally think this is well addressed in statistical learning theory (SLT) for instance.\n * Going beyond an individual model (SLT), and considering families of models (such as in Bayesian learning) and model selection - which lines 68-94 hint at - I think it would be worth discussing the minimum description length framework, where it is also obvious that the description length of a model with probabilistic parameters depends in many cases only weakly on the number of parameters.\n * The main arguments in the paper also lend themselves to some empirical investigation. For instance, one conclusion would be that increasing the width of the bottleneck layer should lead to an increased number of required datapoints, whereas increasing depth (by adding layers) should have no such effect. Though the theoretical arguments in the paper are clear and sound, a simple empirical investigation could add to the paper.\n * Expand on the discussion started in lines 329-338. This is one of the most relevant questions in modern machine learning - given that the number of datapoints is insufficient to fully determine the desired input/output relationship (and thus fully specify the correct equivalence class of parameters), how can desired functional generalization be ensured and why would it be beneficial to not reduce the number of parameters (but regularize through other means instead)? Admittedly, this is beyond the main point of the paper - but building good intuitions for these questions could be very valuable for the community.\n\nSince the paper is written in a scholarly style, discussing SLT (and potentially MDL) as suggested above could add depth to the paper. I personally would also prefer de-emphasizing the “attack of the dogma” a bit, but that is a matter of taste, not technical correctness.\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": {}}]

Author rebuttal:

Decision: Reject