What training reveals about neural network complexity
Authors: Andreas Loukas
Marinos Poiitis
Stefanie Jegelka
Venue: NeurIPS 2021 Poster (2021)
Keywords: neural networks
training behavior
DNN complexity
Lipschitz constants
Benevolent Training Hypothesis

Abstract: This work explores the Benevolent Training Hypothesis (BTH) which argues that the complexity of the function a deep neural network (NN) is learning can be deduced by its training dynamics. Our analysis provides evidence for BTH by relating the NN's Lipschitz constant at different regions of the input space with the behavior of the stochastic training procedure.  We first observe that the Lipschitz constant close to the training data affects various aspects of the parameter trajectory, with more complex networks having a longer trajectory, bigger variance, and often veering further from their initialization. We then show that NNs whose 1st layer bias is trained more steadily (i.e., slowly and with little variation) have bounded complexity even in regions of the input space that are far from any training point. Finally, we find that steady training with Dropout implies a training- and data-dependent generalization bound that grows poly-logarithmically with the number of parameters. Overall, our results support the intuition that good training behavior can be a useful bias towards good generalization.

What training reveals about neural network complexity
Andreas Loukas EPFL andreas. lou.as@epp....c.m ch
Marinos Poiitis Aristotle University of Thessaloniki mpoiitis@csd. .u
Stefanie Jegelka MIT stefje@mit.ce edu
Abstract
This work explores the Benevolent Training Hypothesis (BTH) which argues that the complexity of the function deep neural network (NN) is learning be deduced by its training dynamics. Our analysis provides evidence for BTH by relating the NN's Lipschitz constant at different regions of the input space with the behavior of the stochastic training procedure. We first observe that the Lipschitz constant close the training data affects various aspects of the parameter trajectory, with more complex networks having a longer trajectory, bigger variance, and often veering further from their initialization. We then show that NNs whose 1st layer bias is trained more steadily (i.e., slowly and with little variation) have bounded complexity even in regions of the input space that are far from any training point. Finally, we find that steady training with Dropout implies a training- and data- dependent generalization bound that grows poly-logarthmmically with the number of parameters. Overall, our results support the intuition that good training behavior can be a useful bias towards good generalization.
Introduction
Though neural networks (NNs) trained on relatively small datasets can generalize well, when em- ploying them on unfamiliar tasks significant trial and error may be needed to select an architecture that does not overfit [ Could it be possible that NN designers favor architectures that can be easily trained and this biases them towards models with better generalization?
In the heart of this question lies what we refer to as the "Benevolent Training Hypothesis" (BTH), which argues that the behavior of the training procedure can be used as indicator of the complexity of the function a NN is learning. Some empirical evidence for BTH already exists: (a) It has been observed that the training is becoming more tedious for high frequency directions in the input space (2] and that low frequencies are learned first
3 (b) Training also slows down the more architecture is 3.5x slower to train when used to predict random labels than real ones. (c) Finally, Arpit et al. [6] noticed that the loss is more sensitive with respect specific training points when the network is memorizing data and that training slows down faster as the NN size decreases when the data contain noise.
images/labels corrupted [4] e.g., the Inception
From the theory side, it is known that the training of shallow networks converges faster for more separable classes [ and slower when fitting random labels (8). In addition, the stability of stochastic gradient descent (SGD) implies that (under assumptions) NNs that can be trained with a small number of iterations provably generalize 10 I
Intuitively, since each gradient update conveys limited information, NN that sees each training point few times (typically one or two) will not learn enough about the training set to overfit. Despite the elegance of this claim, the provided explanation does not necessarily account for what is observed in practice, where NNs trained for thousands epochs can generalize even without rapidly decaying learning rates.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

long trajectory
large variance
(
small variance
St(æ)
simple function complex function
6/9
short trajectory
Figure I: Our findings connect training dynamics and NN complexity by showing that the trajectory of the 1tt layer bias reflects the NN's Lipschitz constant near (and far from) the training data: the bias of higher complexity NNs exhibits a longer trajectory and varies more at the end of the training.
1.1 Quantifying NN complexity
This work takes a further step towards theoretically grounding the BTH by characterizing the relationship between the SGD trajectory and the complexity of the learned function. We study neural networks with ReLU activations, i.e., parametric piece-wise linear functions. Though many works measure the complexity of these networks via their maximum number of linear regions [5), is suspected that the average NN behavior is far from the extremal constructions usually employed theoretically [66.
We instead focus on the Lipschitz continuity of a NN at different regions of its input. For networks equipped with ReLU activations, the Lipschitz constant in region is simply the norm of the gradient at any point within it. The distribution of Lipschitz constants presents a natural way to quantify the complexity of NNs. Crucially, NNs with bounded Lipschitz constant can generalize beyond the training data, a phenomenon that has been demonstrated both theoretically [77119] and empirically (20). The generalization bounds in question grow with the Lipsehitz constant and the intrinsic dimensionality of the data manifold, but not necessarily with the number of parameters which renders them ideal for the study of overparameterized networks.
1.2
Main findings: connecting training behavior and neural network complexity
We link training dynamics and NN complexity close and far from the training data (see Figure D
NN complexity close to the training data. Section commences with simple observation: SGD updates the 1st layer bias more quickly if the learned function has a large Lipschitz constant near sampled data point. This implies that the length of the bias trajectory grows linearly with the Lipschitz constant of the NN on its linear regions that contain training data (Theorem T Based on this insight, we deduce that (a) near convergence, the parameters of more complex NNs vary more across successive SGD iterations (Corollary - and (b) the distance of the trained network initialization is small if the learned NN has low complexity (near training data) throughout its training, with the first few high-error epochs playing dominant role (Corollary 3
NN complexity far from the training data. Section focuses on the relationship between training and the Lipschitz constant in empty regions of the input space, i.e., linear regions of the NN that do not contain training points. We first show that the Lipschitz constants in empty regions are linked with those of regions containing training points (Theorem Our analysis implies that NNs whose parameters are updated more slowly during training have bounded complexity in a larger portion of the input space. We then demonstrate how training NNs with Dropout enables us to grasp more information about the properties of the learned function and, as such, to yield tighter estimates for the global I. Lipschitz constant. Our findings yield data- and training- -eeeiinnd-eeedeent generalization bound
Whiie the Lipschitz constant is typically upper bounded by the product of spectral norms of the layer weight matrices (thus yielding an exponential dependency on the depth), the pfoduct-of norms bound is known to be far from the real Lipschitz constant (2] 22

---

that features poly-logaritmmic dependence on the number of parameters and depth (Theorem 3) On the contrary, in typical NN generalization bounds the number of samples needs to grow nearly linearly with the number of parameters 23
25
or exponentially with depth [26 30
All proofs can be found in Appendix B whereas Appendices and thcoretical results, respectively.
A and Contaiin additional empirical
2 Related works
The Lipschitz constant of NNs. Since exactly computing the Lipschitz constant NP-hard [11]
its efficient estimation is an active topic of research 34 22 35) Our work stands out from these works both motivation (i.e., we connect training behavior with NN complexity) and in the techniques developed (we are not employing any complex algorithmic machinery to estimate the Lipschitz constant of trained model, but we bound it as the NN is being trained based on how weights change). Empirically, Lipschitz regularization has been used to bias training towards simple and adversarially robust networks 436422 Theoretically. the Lipschitz constant is featured prominently in the generalization analysis of NNs (e.g., 126 28)). but most analyses depend on sensitivity w.r.t. parameter perturbation, which is related but not identical to the Lipschitz constant.
Dropout and generalization. The Dropout mechanism and its variants are standard tools of the NN toolkit 43 45
that regularize training 46 47 and help prevent memorization 66. The effect of Dropout on generalization have been theoretically studied primarily for shallow networks 48 49 47 as well as for general classifiers (50). The generalization bounds that apply to deep networks are norm- based and generally grow exponentially with depth [51 [2] or are shown to scale the Rademacher
complexity by the Dropout probability (for Dropout used the last layer) [53]. We instead base our analysis on arguments from [18] [9] and exploit the properties of ReLU networks to derive a bound
that features a significantly milder dependency on the NN depth.
Flat and sharp minima. Flat minima correspond to large connected regions with low empirical error in weight space and have been argued to correspond to networks of low complexity and good generalization [54]. has also been shown that SGD converges more frequently to flat minima [55]- (5]. Different from the current work that focuses on the sensitivity w.r.t. changes in the data, flatness corresponds to a statement about local Lipschitz continuity w.r.t. weight changes. In addition, whereas flat minima are regions of the space where the loss is low, our main results account for more complex loss behaviors (by means of an appropriate normalization). Note also that some works argue that the flat/sharp dichotomy may not capture all necessary properties [60-62] as flat minima can be made sharp by a suitable reparameterization 61,, and flat and sharp minima may be connected [61.
Training dynamics of NNs. Many authors have studied the training dynamics of NNs arguing that, with correct initialization and significant overparameteriiztton,, SGD converges to good solution that generalizes. Our work complements these studies by focusing on how the SGD trajectory can be used to infer NN complexity. Arora et al. ( connect the trajectory length and generalization performance via the Neural Tangent Kernel (NTK). Most analyses based on the NTK ("lazy" regime) mean field approximation ("adaptive" regime) focus on 2- 3-layer networks. In contrast to these works, we make no assumptions on initialization or NN size.
3 Preliminaries and background
Suppose that we are given a training dataset (X,Y). consisting of N training points X (x....., an) and the associated labels = ..,).. with Φ; E X C R² and y E e C R.
We focus on NNs defined the composition of layers fa o.... ..... fi, with
fi w) ( + bi) for 1 l....,dd d.
Above, Wi E Ruixm: 1 and b, E TR with no = n and n. = 1, and w = (W1, bi..... .., Wa ba) are the network's 's parameters. For all layers but the last, Pr will be the ReI.U activation function, whereas Pd may either be the identity pa(x) = x (regression) or the sigmoid function pa(x) = 1/(1 + e e))) (classification).
3

---

We optimize w to minimize a differentiable loss function é using stochastic gradient descent (SGD).
The optimization proceeds in iterations and each parameter updated follows:
w Ct; @f(((x!)) w(()),
w (++1))
where (+)) E X is point sampled with replacement from the training set at iteration 4, y is its label, and is the learning rate. It will also be convenient to refer to [(; wl()) as f().
3.1 Linear regions
A well-known property of NNs with ReLU activations is that they partition the input space into regions (convex polyhedra) R R= within which is linear. This viewpoint will be central to our analysis.
There is simple way to deduce this property from first principles. When pa is the identity, each can be equivalently expressed as
f(x, w) = Su(z)(Wa( ...
+ bb) + b2) ...) + ba).
where we have defined the input-dependent binary diagonal matrices
(xx)) == diag(1 c ..... (x. w) > 0)) and Sy(²)= 1,
with 1 > 0] being the indicator function applied element- The key observation is that, when the neuron activations (x) are fixed for every layer, the above function becomes linear. Thus, each linear region RR of contains those points that yield the same neuron activation pattern.
Since the activation pattern of any region is uniquely defined by single point in that region, write Rx to refer to the region that encloses æ.
3.2 Local and global Lipschitz constants
function f is Lipschitz continuous with respect to a norm ||. 1/2 there exists a constant such that for all æ, x' we have [I) -((x')lla < || æ'112. The minimum À satisfying this condition called the Lipschitz constant of and denoted by Ay-
The Lipschitz constant intimately connected with the gradient. This can be easily seen for differentiable functions ʃ X R. in which case Xy suPaex V [2)) where X' is convex set and (x) is the gradient of f at x: (70) 31 34).
Although NNs with ReLU activations are not differentiable everywhere, their Lipschitz constant can be determined in terms of their gradient within their regions. Specifically, the local Lipschitz constant within a linear region Ræ of is
XR(Rz)
| fa, w)ll2
The Lipschitz constant of f is then simply the largest gradient within any linear region '5 suPaEx [ar, w)) The latter is typically upper bounded by Xprid = Ih Will2 which is known be loose bound 21 22]. For a more formal treatment that also accounts for different types of activation functions and vector-valued outputs, the reader may refer to 22
Relating training behavior to NN complexity close to the training data
Our analysis commences in Section 4.1 by deriving general result that bounds the (appropriately normalized) length of the SGD trajectory over any training interval with the Lipschitz constant of the NN close to training data. Our results the distance initialization and weight variance will be implied as corollaries in Section 4.2
4.1 Bounding the length of the SGD trajectory
Theorem formalizes a simple observation: the gradient a neural network with respect to input is intimately linked to that with respect to the bias of the first layer. This implies that, by observing how fast the bias of the network updated, we can deduce what the Lipschitz constant of the leamned function on the linear regions of the input space encountered during training.

---

Theorem (Trajectory length), Let f()) be a dllayer NN being trained by SGD. Further, denote by
Cyts (x. y) [e((ū: y)
(==
the gradient of the loss with respect to the NN's output at iteration t. For any set T of iteration indices within which the gradient is not zero, the (normalized) bias trajectory is upper//lwer bounded
Axce (Re))))
160 1++1)
b 1a
Aytes
Σ tET (W
ag Eyos (z())))))
on (n(
where (W(") 2 2 on (W(1) 0 are the singular values of W(
Theorem shows that lower complexity learners will have shorter (normalized) bias trajectory. Eyts (t) (t) and a remain approximately constant throughout T. the trajectory will grow linearly with the Lipschitz constant of the learner close to the training data.
Why we focus on the first layer bias. It might be originally surprising that the gradient w.r.t. b1 is indicative of NN complexity. While the value of is not particularly informative, turns out that the way it changes over successive SGD iterations reflects the operation of the entire NN: since b and æ are processed by the NN in a similar fashion, the sensitivity of the NN output w.r.f. changes in the bias relates to those induced by changes in the input. Indeed, via the chain rule, we have
V f(x w) W WaSa-1 - = (0f(z, w)
W1.
θb,
where, for simplicity of exposition, we consider here the case which Pa is the identity function and thus Sa(x) 1. The above equation also explains why the singular values of W1 appear in the bound: since the gradient of b, does not yield information about W1, we account for it separately. Alternatively, as explained in Appendix C.2 the first layer Lipschitz constant can be controlled by also taking into account the dynamics of W1 and W2. We also note that an identical argument can be utilized to connect the gradient of bj with the Lipschitz constant of fa ..... fi+1 (z))
Understanding the normalization. The normalization by 0g foo (zx(1) (x()))(()))))))))))))))))))))( renders the bound independent of the learning rate a as well as of how well the network fits the training data. When mean-squared error (MSE) and a binary cross-entropy (BCE) loss is employed
(U y)² and (BC y) = y-yllogg (8) - (1 y) log (1 1))
(M v)
2
with y.ú 0 E R and y, í E [o, 1]. respectively, we have
( v) [f(x) yl and (x
[x)
In both cases, () y) measures the distance between the true label and the NN's output.
Applicability other architectures. Beyond fully-connected layers, Theorem I directly applies to layers that involve weight sharing and/or sparsity constraints, such as convolutional and locally- connected layers, as long as b, remains non-shared. addition, the result also holds unaltered for networks that utilize skip connections or max/average pooling after the 1st layer, as well as for NNs with general dementt-wise activation functions (see Appendix C.I.
Dependence on the singular values of W1. The lower bound presented in Theorem can be expected to be much tighter than the upper bound since the largest singular value is usually reasonably small constant, whereas the smallest may be (close to) zero. Fortunately, the upper bound can be tightened when the data fall within some lower-dimensional space S. In that case, may substitute the minimum singular value with the minimum of w æ ||l for all æ E S of unit norm.
4.2 Corollaries: steady learners, variance of bias, and distance to initialization
Suppose that after some iteration our NN has fit the training data relatively well. We will say that the NN is "steady learner" if its 1st layer bias is updated slowly:
5

---

Definition (Steady learner). A NN f()) trained by SGD is (T, steady if
1b (b(+t) (++1) 112
S P for all 22T. T.
ax Eftt) (x(1), y(t))
The following a simple corollary:
Corollary 1, Let f( (T, -t--aaddy Consider an interval T of iterations after T and suppose that 01 (W(()) S B for every t T. Select iteration t T random. The Lipschitz constant X will be bounded by y (Rx) S B p, generically, i.e., with probability that converges to 1 as [T' grows.
of f(t) at every training point
Crucially, the bound of Corollary can be exponentially tighter than the product-of-norms bound Xpoul whereas 3yp does not generally depend on depth, 2 (Rz) wd when |Will2 = w.
We will also use Theorem to characterize two other aspects of the training behavior: the parameter variance as well as the distance to initialization. The following corollary shows that the weights of high complexity NNs cannot concentrate close to some local minimum:
Corollary (Variance of bias). Let f(t) be d-layer NN with ReLU activations being trained by SGD. Let be a set of iteration indices and write
Charm (T)
V
/harm (xx(1)) y(t))2
tET
for the square-root of the harmonic mean of the squared loss derivatives within T.. Then, the bias of the first layer will exhibit variance at least:
2
at Apus (R Charm (T)
avg ET
|6
avg b1 1 LET
avg IET
(1)
2 201(W
Therefore, a larger complexity NN will need to fit the training data more closely (so that Cuamn (T) decreases) to achieve the same variance that of lower complexity NN.
We can also deduce that the bias will remain closer initialization for NNs that have a smaller Lipschitz constant:
Corollary (Distance to initialization). Let f(() be d-layer NN being trained by SGD with an MSE loss and fix some iteration T. The first layer bias may move from initialization by at most
Egt (2x (1)
(1) ()) Xyen (R.:))
| 11
a
Tx (W
The latter result is only meaningful in regression setting. When using the BCE loss, the loss derivative can grow exponentially when the classifier confidently wrong. On the contrary, with an MSE loss in place the loss derivative grows only linearly with the error, rendering the bound more meaningful.
When a and cyco) ( (()) decay sufficiently fast, the bound depends on o, ",,, (W( and the (normalized) Lipschitz constant at and close to initialization. Therefore, the corollary asserts that SGD with an MSE loss can find solutions near to initialization two things happen: the NN fits the data from relatively early in the training while implementing low-complexity function close the training data.
NN complexity far from the training data
Our exploration on the relationship between training and the complexity of the learned function thus far focused only on regions of the input space that contain at least one training point. natural to ask how the function behaves in empty regions. After all, to make generalization statements we need ensure that the learned function has, with high probability, bounded Lipschitz constant close to any point in the training distribution.

---

Next, we provide conditions such that a NN that undergoes steady bias updates. as per Definition [ also has low complexity linear regions that do not contain any training points. Our analysis starts in Section 5.1 by relating the Lipschitz constant of regions in and outside the training data. We then show Section 5.2 how learners that remain steady while trained with Dropout have bounded generalization enror.
A central quantity in our analysis is the activation sx associated with each æ::
$t (z) ==
diag
5 (z)
1lf oi w) 0] {0, [0.1)" 1
Lmd-1
I=d-1
Thus, 8x (x) is the Kronecker product of all activations when the NN's s input is æ.
We will also assume that the learned function f(()) eventually becomes consistent on the training data: Assumption 1. There exists 7,7 0 such that s((x)) sy (ar) and (Rx) S (1
7) X MyeeyRaa for all x E X and t 2
Assumption D weaker than requiring that the parameters have converged: the parameters are allowed to keep changing long the slope and activation pattern each training point remains similar. We also stress that the NN can still have different activation patterns at different points (and thus be highly non-linear), long as these activations stay persistent over successive iterations. Naturally, it is always possible to satisfy our assumption by decaying the learning rate appropriately.
5.1 The Lipschitz constant of empty regions
As we show next, the Lipschitz constant of a NN can be controlled for those regions whose neural activation can be written as a combination of activations of training points.
Theorem 2. Let T be any interval of SGD iterations that satisfies Assumption 1 and suppose that (W1 (0) S for all i T. Furthermore, denote, respectively, by
1 (++1) 104) Ci E (t) y()))
ST = (x) IET
PT :=
JT = min EE
EE
the binary matrix whose columns are the neural activations of all points sampled within T, the vector containing the normalized bias updates, and the distance to integrality if a sigmoid is used in the last layer. Select a point x E IR" that not in the training set. For all t E T, the Lipschitz constant of f(t) in Ra is bounded by the following Basis Pursuit problem:
(Ra)) S (1 min ||a ④ sprll1 subject to 84(xr) = ST a,
(Rz))
a
0.25 where @ is the Hadamard product, { = prr (1-br)
if a sigmoid is used and 5 = 1, otherwise.
To grasp an intuition of the bound, suppose that we are a regression setting ($ = 1) and that the interval T is large enough so that have seen all training points. Theorem 2 then implies:
2 .....,,, Tig E X, sx(x)) sx( +.... (x
2 (R,) S 3 + 7) lbo
By itself, Theorem 2 does not suffice to ensure that the function is globally Lipschitz because the theorem does not have predictive power for points whose activation 8i (xr cannot be written linear combination Sra of activations of the training points. A sufficient condition for the theorem to yield a global bound is that ST is full rank, but the latter can only occur for N 2 Ri- .. quantity that grows exponentially with the depth of the network. Section 5.2 will provide significantly milder condition for networks trained with Dropout.
5.2 Learners that remain steady with Dropout generalize
Dropout entails deactivating each active neuron independently with probability p. We here consider the variant that randomly deactivates each neuron independently at the end of the forward- with
Tyyicallyy the neurons are dropped during the forward pass and not at the end as we do here. However, for networks with < 2. the mechanisms are identical.
7

---

probability 1/2. We focus on binary NN classifiers
1 (x) 1 [()()
0.5
trained with BCE loss, and with the NN's last layer using a sigmoid activation. The empirical and expected classification error is, respectively, given by
emp er
N avg
g (ct.) + y/
and er, = ((e,)) 1 g0 + +w]
Theorem 3 controls the generalization error in terms of the number N (X;; 22, re (X)) of &g balls of radius r, needed to cover the data manifold X. The radius is shown to be larger for more steadily trained classifiers (through 1/(p) and depend logarithmically on the number of neurons:
Theorem 3. Let f(t) be depth d NN with ReLU activations being trained with SGD, a BCE loss and 1/2 /a-rropout.
Suppose that f(t) is (r, -te-ddd and that for every 2 T the following hold: (a) Assumption 7 (b)
(x)) S E (a.) for every x X, (c) 01 (W S B. and (d) f (xx(1)) E [m, 14]. Define
(x) min |1 (2(((()))
and (1 + 7) B 1101+00 +())
op log - mi
p (1 p)) Pmin
where Pmin minted,ssmm... Javgeex diag(S)) ((( (x))]: > neuron is active before Dropout is applied.
is the minimum frequency that any
For any 8 > with probability least ô over the Dropout and the training set sampling, the generalization error is at most
(( (
+ log (1/0)
ler( -ee-eer 1
N
where (X2;22, is the minimal number of fa-balls of radius needed to cover X.
Intuition. Recall that the bounds derived in Section Jnny concern the regions of the NN that contain at least one training point. However, due to the geometry of these regions, it is possible (and likely) that small empty regions will be located near those that have training data inside them. Deriving generalization bound would require upper bounding the Lipschitz constant of the NN on these empty regions. Unfortunately, to our knowledge, the latter is not possible without resorting loose product-of -romums-of-norms bounds or imposing strong additional assumptions that assert that the training regions are sufficiently diverse (as Theorem does). Here is where Dropout comes in. Dropout introduces stochasticity in the training procedure that provides information of the NN function in the gaps between training data. This allows us infer the Lipschitz constant of the function in larger portions of the space from the training behavior and thus to relax the assumptions of Theorem Specifically, the proof approximates the global Lipschitz constant as follows:
A
steady fro
c
log
Σ
d-
with Aycs S steady < Apen
o log
Σ
m
It then invokes a robustness argument [8 19 to control the generalization error. The bound above comes in sharp contrast with the product-of-norms bound Xprod which grows exponentially with d and can be arbitrary larger than Ayc, since there exists parameters for which 'y = 0 and Apraa > 0.
Understanding the assumptions made. The strongest requirement posed by Theorem 3 is that every neural pathway activated for each training point: sy (xx < >.V 8y (2x) for every x E X. In contrast to Theorem 2 the latter can be satisfied even when N = e.g. if there exist some training point for which all neurons are active. However, the assumption will not hold when some entries of (x)) are never activated after iteration 7. Little can also be said about the global behavior of f(t)) when there neurons that are not periodically active (which would also imply Pmiie 0). We

---

Blgg traeccom bergth (per epochi
frog=10
froge10
Froq=0:75
tregm2.5
Trpp0.55
Tain bas
frag
frape0
Test
0.10
0.4
0.0
500
1000
1500 Epoch
2000
2500
3000
500
1000
1500
2000
2500
3000
500
1000
1500 Epoch
2000
2500
3000
(a) Training loss (regression)
(b) Bias trajectory (regression)
(c) Test loss (regression)
Bigg tratecery porrryyy for fper epoch
0.4
cer 0.
comuption0..
0.4
oor 0.4
0.6
comuptinw 4
0.3
comuptin-02 2 comupticn-0.3
0.3
0.4
Test
0.1
0.2
0.1
0.0
0.0
20
40
80
100
20
60
80
100
40
60
100
Epoch
Epoch
Epoch
(d) Training loss (CIFAR classif.)
Bias trajectory (CIFAR classif.)
(f) Test loss (CIFAR classif.)
Figure 2: Training behavior of MLP (top) and CNN (bottom) solving task of increasing complexity (green->red); fitting a function of increasing spatial frequency (top) and classifying CIFAR images with increasing label corruption (bottom). In accordance with Theorem I the per epoch bias trajectory (middle subfigures) longer when the network is asked to fit a more complex training set.
argue however that such neurons can be eliminated without any harm by definition, they are not affecting the NN's output after т.
Dependence on the classifier's confidence. According to Theorem the best generalization is attained when the classifier has some certainty about its decisions the training set (so that |1 (xx) = (2)1)) while also not being overconfident (so that μ (1 11) 0(1).
Dependence on the data distribution and the number of parameters. A interesting property of the bound is that it depends on the intrinsic dimension of the data rather than the ambient dimension. For instance, if X is Cм -regllr A k-dimensional manifold with CM ((1) it is known 71 that
Cas
N(X;
implying that N ((r(())
training points suffice to ensure generalization. This sample complexity bound grows poly- logarithmically with the number of neurons On the contrary, since the radius r of the &2 balls used in the covering grows inversely proportionally bound was used our proof, then the sample
n1 and the number of parameters when cp O(1).
the Lipschitz constant, if the product-of-nonee complexity would be exponentially larger: if WWll2 = w then r = Oww-a and N = Owwd)).
As remarked by Sokolić et al. [19], other data distributions with covering numbers that grow polynomi- ally with & include rank-k Gaussian mixture models [72] and k-sparse signals under a dictionary 773
6 Experiments
We test our findings in the context of two tasks:
Task 1. Regression of sinusoidal function with increasing frequency. In this toy problem, multi-layer perceptron (MLP) is tasked with fitting randomly-same sampled 2D sinusoidal function with increasing frequency (0.25, 0.5, 0.75, 1) isometrically embedded in a 10-dimensional space. More details can found Appendix A. The setup allows us to test our results while precisely controlling the complexity of the ground-truth function: fitting low-frequency function necessitates a smaller Lipschitz constant than a high-frequency one. We trained an MI. with layers consisting entirely of ReLU activations and with the 1st layer weights being identity. We repeated the experiment

---

Veraacee biss (nomma
30
Disance to Intolllgg Inbalicgeos
0.8
Vertance biss (normal
10-4
0.6
20
30
02
10-1
0.0
20
0.25
0.75
1.0
0.25
0.5
0.75
1.0
0.0
0.2
Frequency
Frequency
Corruption rate
(a) Variance (regression)
(b) Distance to init. (regression)
Variance (CIFAR classif.)
Figure 3: A closer inspection of how the bias is updated. The variance is computed over the last 10 epochs. As seen, the bias of higher complexity NNs varies more close to convergence (Corollary 2
Further, with an MSE loss, high complexity NNs may veer off further from initialization (Corollary
10 times, each time training the network with SGD using a learning rate of 0.001 and an MSE loss until it had fit the sinusoidal function at 100 randomly generated training points.
Task 2. CIFAR classification under label corruption. In second experiment, we trained convolutional neural network (CNN) to classify 10000 images from the 'dog' and 'airplane' classes of CIFARIO (74) The classes were selected at random. We focus on binary classification remain consistent with the theory. Inspired by 4]. we artificially increase the task complexity by randomly corrupting a (0, 0.2, 0.4, 0.6) fraction of the training labels. Thus, higher corruption implies larger complexity function. Differently from the first task, we used a CNN with 2 convolutional layers featuring ReLU activations first layer identically with the regression experiment. We repeated the experiment 8 times, each time training the network with SGD using BCE loss and a learning rate of 0.0025.
intermediate layers and a sigmoid activation in the last. We set the
In agreement with previous studies 4. 6 2], Figure 2 shows that training slows down as the complexity of the fitted function increases. Figures 2b and depictt the per-epoch bias trajectory:
ExeTapa [|b] (((11) ((0) (le/a (x((), (0) According to Theorem 1 this measure captures the
Lipschitz constant A yes (Ra()) of the NN during each epoch and across all training points. In agreement with our theory, the bias trajectory is significantly longer when fitting higher complexity functions. The length of the total trajectory is the integral of the depicted curve, see Appendix [A.4] Moreover, as shown Fig 2c] the trajectory length also correlates with the loss of the network on held-out test set, with longer trajectories consistently corresponding to poorer test performance.
We proceed to examine more closely the behavior of b(" during training. Figures 3a and 3b corroborate the claims of Corollaries and MSE loss is utilized, the bias will remain more stable (here we show the variance in the last 10 epochs) and closer to initialization. The same variance trend can be seen Figure 3cl for image classification. The distance-to-initialle to-initillizationn analysis is not applicable to classification (due to the BCE gradient being unbounded). but we include the figure in Appendix A.2 for completeness.
respectively: when fitting a lower complexity function
Additional results. The interested reader can refer to Appendices A.3 and A.4 for visualizations of And
A.6 the Lipschitz constants within linear regions and of the total bias trajectory length. Appendices A.6
and An. test test how our findings are affected by the batch size and architecture, whereas Appendix A.7 examines the training dynamics associated with deeper layer biases.
7 Conclusion
This paper showed that the training behavior and the complexity of a NN are interlinked: networks that fit the training set with small Lipschitz constant will exhibit shorter bias trajectory and their bias will vary less. Though our study is of primarily theoretical interest, our results provide support for the Benevolent Training Hypothesis and suggest that favoring NNs that exhibit good training behavior can be a useful bias towards models that generalize well.
At the same time, there are many aspects of the BHT that we do not yet understand: what is the effect of optimization algorithms and of batching on connection between complexity and training behavior? Does layer normalization play a role? What can be glimpsed by the trajectory of other parameters? We believe that a firm understanding of these questions will be essential in fleshing out the interplay between training, NN complexity, and generalization.
10

---

Acknowledgments and Disclosure of Funding
We are thankful the anonymous reviewers, Giorgos Bouritsas, Martin Jaggi, Nikos Karalias, Mattia Atzeni, and Jean-Baptiste Cordonnier for engaging in fruitful discussions and providing valuable feedback. Andreas Loukas would like thank the Swiss National Science Foundation for supporting him in the context of the project "Deep Learning for Graph Structured Data", grant number PZ00P2 179981. Stefanie Jegelka acknowledges funding from NSF CAREER award 1553284, NSF BIGDATA award 1741341 and an MSR Trustworthy and Robust AI Collaboration award.
References
[1] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. In International Conference Learning Representations, 2021.
[2] Guillermo Ortiz-Jiménez, Apostolos Modas, Scyed-Mohsen Moosavi-Dezfoolii and Pascal Frossard. Neural anisotropy directions. In NeurlPS 2020, 2020.
[3] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville. On the spectral bias of neural networks. In International Conference on Machine Learning, pages 5301-5310. PMLR, 2019.
[4] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv:1611.03533 2016.
[5] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEFE conference computer vision and pattern recognition, pages 1-9,
2015.
[6] Devansh Arpit, Stanistaw Jastrzęhski, Nicolas Ballas, David Krueger, Emmanuel Bengio, Maxinder S Kanwal, Tegan Maharaj, Asja Fischer, Aaron Courville, Yoshua Bengio, et al. closer look memorization in deep networks. In International Conference on Machine Learning, pages 233-242. PMLR, 2017.
[7] Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwart. Sgd learns over- parameterized networks that provably generalize on linearly separable data. In International Conference on Learning Representations, 2018
[8] Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterrzze two-layer neural networks. In International Conference on Machine Learning, pages 322-332. PMLR, 2019.
[9] Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 1:499-526, 2002.
[10] Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225- 1234. PMLR. 2016.
[11] I1ja Kuzborskij and Christoph Lampert. Data-dependent stability of stochastic gradient descent. In International Conference on Machine Learning, pages 2815-2824. PMLR, 2018.
[12] Guido Montúfar, Razvan Pascanu, Kyunghyun Cho, and Yoshua Bengio. On the number of linear regions of deep neural networks. In Proceedings of the 27th International Conference on Neural Information Processing Systems- Systems-Volume Volume 2, pages 2924 2924-2932, 2014.
[13] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein. On expressive power of deep neural networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2847- 2854, 2017.
11

---

[14] Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. In International Conference on Learning Represen- lations, 2018.
[15] Thiago Serra, Christian Tjandraatmadja, and Srikumar Ramalingam. Bounding and counting linear regions of deep neural networks. In International Conference on Machine Learning. pages 4558 4566. PMLR, 2018.
[16] Boris Hanin and David Rolnick. Complexity of linear regions deep networks, In International Conference on Machine Learning, pages 2596-2604. PMLR, 2019.
[17] Ulrike von Luxburg and Olivier Bousquet. Distance-based classification with lipschitz functions.
J. Mach. Learn. Res., (6669-695, 2004.
[18] Huan Xu and Shie Mannor. Robustness and generalization. Machine learning, 86(3):391-477 2012.
[19] Jure Sokolić, Raja Giryes, Guillermo Sapiro, and Miguel RD Rodrigues. Robust large margin deep neural networks. IEEE Transactions on Signal Processing, 65(16):4265 4280, 2017.
[20] Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: empirical study. In International Conference on Learning Representations, 2018.
[21] Patrick L. Combettes and Jean- San-Christoppe Pesquet. Lipschitz certificates for layered network structures driven by averaged activation operators. SIAM Journal on Mathematics of Data Science, 2(2):529-5537 257-577 2020.
[22] Matt Jordan and Alexandros G Dimakis. Exactly computing the local lipschitz constant of relu networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, 2020.
[23] Vladimir N Vapnik. An overview of statistical learning theory. IEEE transactions neural networks, 10(5):988-999, 1999.
[24] Shai Shalev-Shwariz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
[25] Peter Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc- dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):2285-2011, 2019.
[26] Peter L Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normalizee normalized margin bounds for neural networks. In Proceedingy of the s1 International Conference Neural Information Processing Systems, pages 6241 1-250, 2017.
[27] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to margin bounds for neural networks. In International Conference on Learning Representations, 2018.
[28] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299. PMLR, 2018
[29] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference Machine Learning. pages 254-263. PMLR, 2018.
[30] Konstantinos Pitas, Andreas Loukas, Mike Davies, and Pierre Vandergheynst. Some limitations of norm based generalization bounds in deep neural networks. CoRR, hass/1905.09677, 2019. URL
httpp:/aar/i http::///xxxvv.or/aaa// wwwp///gg/bbb//oooeee 1905. 09677
[31] Kevin Scaman and Aladin Virmaux. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 3839-3848, 2018.
12

---

[32] Mahyar Fazlyab, Alexander Robey, Hamed Hassani, Manfred Morari, and George J Pappas. Efficient and accurate estimation of lipschitz constants for deep neural networks. In NeurIPS, 2019.
[33] Dongmian Zou, Radu Balan, and Maneesh Singh. On lipschitz bounds of general convolutional neural networks. IEEE Transactions on Information Theory, 66(3):1738-1759) 2019.
[34] Fabian Latorre, Paul Thiemyy Yves Rolland, and Volkan Cevher. Lipschitz constant estimation for neural networks via sparse polynomial optimization. In 8th International Conference on Learning Representations, 2020.
[35] Tong Chen, Jean Lasserre, Victor Magron, and Edouard Pauwels. Semialgebraic optimization for lipschitz constants of relu networks. In Advances in Neural Information Processing Systems, pages 19189-19200, 2020.
[36] Yusuke Tsuzuku, Issei Sato, and Masashi Sugiyama. Lipschitz-marge training: scalable certification of perturbation invariance for deep neural networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 6542-6551 2018.
[37] Guang-Ho Lee, David Alvarez-Melis, and Tommi S Jaakkola. Towards robust, locally linear deep networks. In International Conference on Learning Representations, 2018.
[38] Cem Anil, James Lucas, and Roger Grosse. Sorting out Lipschitz function approximation. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 291-301. PMLR, 09-15 Jun 2019.
[39] Patricia Pauli, Anne Koch, Julian Berberich, Paul Kohler, and Frank Allgower. Training robust neural networks using lipschitz bounds. IEEE Control Systems Letters, pages 1-1, 2021.
[40] Zac Cranko, Simon Kornblith, Zhan Shi, and Richard Nock. Lipschitz networks and distribu- tional robustness. arXiv preprint arXiv:1809.01 129, 2018.
[41] Adam M. Oberman and Jeff Calder. Lipschitz regularized deep neural networks converge and 09540
generalize. CoRR, 0a//1808.0540) 2018. URL
[42] Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. Machine Learning. 1002))393-416,, 2021.
[43] Geoffrey Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever. and Ruslan R Salakhut- dinov, Improving neural networks by preventing co-adaptation of feature detectors. arXiv preprint /207.0580 2012.
[44] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):19291198, 2014.
[45] Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pages 1050-1059. PMLR, 2016.
[46] Colin Wei, Sham Kakade, and Tengyu Ma. The implicit and explicit regularization effects of dropout. In International Conference on Machine Learning, pages 10181-10192. PMLR, 2020.
[47] Raman Arora, Peter Bartlett, Poorya Mianjy, and Nathan Srebro. Dropout: Explicit forms and capacity control. arXiv preprint arXiv:2003.0333 033997 2020.
[48] Wenlong Mou, Yuchen Zhou, Jun Gao, and Liwei Wang. Dropout training, data-dependent regularization, and generalization bounds. In International Conference on Machine Learning, pages 3645-3653 PMLR, 2018.
[49] Poorya Mianjy and Raman Arora. On convergence and generalization of dropout training. Advances in Neural Information Processing Systems, 33, 2020.
13

---

[50] David McAllester. A pac-bayesian tutorial with dropout bound. arXiv preprint 187.2:1307.2118, 2013.
[51] Wei Gao and Zhi-Hua Zhou, Dropout rademacher complexity of deep neural networks. Science China Information Sciences, 59(7):1-12, 2016.
[52] Ke Zhai and Huan Wang. Adaptive dropout with rademacher complexity regularization. In International Conference on Learning Representations, 2018.
[53] Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropeonnect. In Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, pages 1058-1066, 2013.
[54] Sepp Hochreiter and Jargen Schmidhuber. Flat Minima. Neural Computation, 9(1):1-42, 01 1997.
[55] Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprini arXiv: (60.6043994 2016.
[56] Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generalization gap in large batch training of neural networks. In NIPS, 2017.
[57] Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711.0462. 2017.
[58] Samuel L Smith and Quoc V Le. A bayesian perspective generalization and stochastic gradient descent. International Conference on Learning Representations, 2018.
[59] Chiyuan Zhang, Qianli Liao, Alexander Rakhlin, Brando Miranda, Noah Golowich, and Tomaso Poggio. Theory of deep learning iib: Optimization properties of sgd. arXiv preprint arXiv: 1at.:1801..2444 2018.
[60] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pages 1019-1028. PMLR, 2017.
[61] Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. arXiv preprint arXiv: 04454, 2017.
[62] Haowei He, Gao Huang, and Yang Yuan. Asymmetric valleys: Beyond sharp and flat local minima. In Advances in Neural Information Processing Systems, 2019.
[63] Itay Safran and Ohad Shamir. On the quality the initial basin overspecified neural networks. In International Conference on Machine Learning, pages 774-782. PMLR, 2016.
[64] C Daniel Freeman and Joan Bruna. Topology and geometry of half-rectified network optimiza- tion. In 5th International Conference on Learning Representations, ICLR 20/7, 2017.
[65] Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In NIPS, 2017.
[66] Quynh Nguyen, Mahesh Chandra Mukkamala, and Matthias Hein. On the loss landscape of class of deep neural networks with no bad local valleys. In International Conference Learning Representations, 2018.
[67] Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over- paratetraeeri neural networks. In International Conference on Learning Representations. 2018.
[68] Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- preerparamttiiittionn International Conference on Machine Learning, pages 242-252. PMLR, 2019.
14

---

[69] Chao Ma, Qingcan Wang, Lei Wu, et al. Analysis of the gradient descent algorithm for deep neural network model with skip-connections. arXiv e-prints, pages urXiv-1904, 2019.
[70] Remigijus Paulavičius and Julius Zilinskas. Analysis of different norms and corresponding lipschitz constants for global optimization. Technological and Economic Development of Economy, 12(4):3013306 2006.
[71] Nakul Verma. Distance preserving embeddings for general n-dimensional manifolds. In Conference on Learning Theory, pages 32-1. JMLR Workshop and Conference Proceedings, 2012.
[72] Shahar Mendelson, Alain Pajor, and Nicole Tomozak-Jaegermann. Uniform uncertainty prin- ciple for bernoulli and subgaussian ensembles. Constructive Approximation, 28(3):277-289, 2008.
[73] Raja Giryes, Guillermo Sapiro, and Alex M Bronstein. Deep neural networks with random gaussian weights: A universal classification strategy? IEEE Transactions on Signal Processing. 64(13):3444 3457, 2016.
[74] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
15


Reviews:
[{"review_id": "uIWm-S2-84x", "reviewer": "Reviewer_KizT", "summary": "The paper deals with the following question: does the behavior of the NN during training indicate anything about the complexity of the learning function? The authors tackle this question in the case of a deep ReLU network in the case of regression/classification and using SGD. They show that the (average over the training points) Lipschitz constant of the learned function lower and upper bounds the bias trajectory. As a consequence, they deduce that i) large complexity NN need to better fit the training data to have similar variance as the one of low complexity NN ii) the bias will remain close for NNs that have smaller Lipschitz constant. Then, the authors derive a bound on the Lipschitz constant in a region that is not in the training set and finally, derive a generalization bound when dropout is used. They add some numerical experiments to verify the theoretical claims.", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: This paper tackles a very exciting question in deep learning theory that is about the relationship between training and the complexity of the learned predictor. I am not aware of a lot of works tackling this question (apart the ones in the NTK regime).  Th tools that are used are from statistical learning theory but i think that they are used in a novel way.  I am not an expert in the field, so I cannot really assess whether the related work has been well cited.  \n\nQuality: The paper seems technically sound. I think it is a high quality paper and even for a non-expert, it is easy to understand. The claims are well-interpreted. The numerical experiments well support the theory and the authors are honest about the limitations of their work. I am not an expert in the intersection between statistical learning and deep learning so I am unable to compare this paper with existing papers in the field. However, I would like to raise some points: \n\n1) What I always found puzzling in the \"statistical learning\" papers for deep learning is the fact that they rely on generalization bounds that depend for instance on the Lipschitz constant of the learned function. This is why the authors seem to desire low complexity function obtained through training. However, it is not obvious for me that networks getting the best generalization are ones with low Lipschitz constants. For instance, it has been numerically observed that some networks that generalize well (CNN) have large Lipschitz constant [1] and therefore are complex. I have some doubts about the fact that the Lipschitz constant is a valid indicator on the generalization ability of the learned predictor.\n\n\n2) I did not manage to fully understand why the authors focus on the 1st layer bias (and not on the 1st weight W_1) in line 150. I think that this paragraph should be clearer.\n\n3) I have some trouble to understand the impact of the optimization algorithm here. How does the algorithm influence the result in Theorem 1? Is it an algorithm specific result? \n\n4) Does your Theorem 1 cover the case of NTK? If we initialize the parameters such as the lazy training paper [2], I expect that my neural network behaves as the NTK. The bias trajectory is going to be short (since my parameters don't move too much from the initialization) and yet, to my knowledge, the NTK can have arbitrary large Lipschitz constant with respect to the input [3]. Therefore, Theorem 1 seems to not hold in this case.\n\n5) In NN, we know that the eigenvalues of a neural network are extremely spread [4]. Does it mean that the bound can be vacuous in some cases? \n\n6) In theorem 2, it is not clear: you need the condition that \"activation of any point in the space can be written as a linear combination of the training points\". Am I correct? Because this is what you say after the regression setting example below the theorem. \n\n7) The paragraph from Line 231 to 234 is a bit unclear to me. According to what I understood, you need the condition \"N \\geq \\prod_{l=1}^{d-1} n_l\" in order to have the following property: the activation of any point in the space can be written as a linear combination of the training points. Is this correct? I think that it should be clearer.\n\n8) Regarding the numerical experiments, do you think that it would be possible to estimate an average Lipschitz constant as done in [1]? It would be interesting to see whether the Lipschitz constant matches with the distance to the bias. \n\nClarity: The paper is well-written and well structured. I enjoyed reading it. \n\nSignificance: The paper tackles an important question and I believe that this is a first interesting step to solving it.\n\nMinor comments: \n\na) Is there a way to simplify Corollary 2? It is a bit hard to skim it.\n\n\n[1] Scaman, K., & Virmaux, A. (2018). Lipschitz regularity of deep neural networks: analysis and efficient estimation. arXiv preprint arXiv:1805.10965.\n\n[2] Chizat, L., Oyallon, E., & Bach, F. (2018). On lazy training in differentiable programming. arXiv preprint arXiv:1812.07956.\n\n[3] Bietti, A., & Mairal, J. (2019). On the inductive bias of neural tangent kernels. arXiv preprint arXiv:1905.12173.\n\n[4] Sagun, L., Bottou, L., & LeCun, Y. (2016). Eigenvalues of the hessian in deep learning: Singularity and beyond. arXiv preprint arXiv:1611.07476.\n\n----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\n\nI would like to thank the authors for their reply. I still believe that this paper is good. If this paper gets accepted, I would like to ask the authors to be transparent on the fact that a small Lipschitz constant is sufficient but not necessarily for generalization. Besides, I think it is important to be more explicit on why the analysis depends on the bias of the first layer. What if the network does not have any bias? Except these two points, I am happy about this paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention the limitations of their work in Section 5 which is definitely an advantage of this paper.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "WgScGrXo3DY", "reviewer": "Reviewer_BRU5", "summary": "The paper studies the relation between the distribution of Lipschitz constants in a neural network during training, the trajectory of gradient descent and the generalization of the network. The authors relate the change in the bias of the first layer to the Lipschitz constant of the network around the training data. Then, it is shown that when if the bias changes slowly enough, this implies that the network has small Lipschitz constant, which can then be used to derive generalization results, assuming the data has small covering number. The theoretical results are complemented with some experiments.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Exploring the relation between the training dynamics and various properties of the network seems like a worthy direction to study, and the setup studies in this work seems highly relevant for this effort. It seems that the authors have some positive and novel results that can be utilized to advance our understanding of generalization in neural networks.\n\nThat said, I have some concerns about the results presented in the paper:\n\n- The main result shows the relation between the change in the bias of the first layer and the average Lipschitz constant of the network, and all other theoretical results build on this simple observation. However, it seems to me that there is nothing specifically interesting in how the bias of the first layer behaves, beyond the fact that it captures the Lipschitz-ness of the network. This makes all the arguments seem somewhat circular - you define \"steady learner\" using a bound on the change of the bias in order to enforce a bound on the Lipschitz constant, and then prove that this means that the Lipschitz constant is bounded. Why is it more natural to assume a \"steady learner\" the way you define it? Why not simply give your assumptions on the Lipschitz constant? \nTo put things another way, suppose we don't use a bias term in the first layer, or for other layers along the network. Does this mean your analysis is vacuous?\nIt seems to me that studying the generalization through the Lipschitz-ness of the network is a very promising direction, but using the change in the bias seems unnecessary.\n\n- Generalization bound for learners with \"dropout\" (section 5.2): I found it hard to follow the results and specifically to validate how \"sane\" are the assumptions of Theorem 3. Generally, any function that is L-Lipschitz around a large enough sample will generalize well if the support of the distribution has a small r-covering number (depending on L and r), because you are likely to sample every r-ball of the covering, and the Lipschitzness guarantees that the function is well-behaved inside each ball. Then, why does this generic argument not apply to the case studied in the paper? Why is the dropout necessary for the generalization argument?\n\n- It seems that the theoretical analysis focuses on the complexity (i.e., Lipschitz constant) of the function being learned, while the experiments focus on the complexity of the target function. What is the connection between the theoretical and empirical results? Do you assume that a network trained on a target function with large Lipschitz constant will also be non-Lipschitz?\n\nMinor comments:\n- In line 45, you write: \"NNs that are everywhere Lipschitz continuous can generalize\". All NNs are typically everywhere Lipschitz continuous, I guess you should add \"with a bounded Lipschitz constant\".\n- You refer to the \"length of the optimization trajectory\" in various places, but it is not properly defined.\n- In Line 70, you write that the sample complexity of neural networks needs to grow exponentially with depth, however this is not true for the basic VC dimension sample complexity, as the VC dimension grows only linearly with depth.\n-  You write \"with high probability\" in several places, I assume you mean with probability at least 1-delta.\n- Line 207: \"MSE loss can find near solutions...\", meaning - solutions near the initialization?\n\n\n-------------------------------------------------------------------------------------------------------------------------------------------\nReading the author feedback, I still think that the fact that the analysis relies heavily on the \"bias of the first layer\" is a major limitation of the paper. My concern is that the fact that the result breaks when removing the bias of the first layer hints that the overall result is very fragile. The observation that the bias of the first layer corresponds to the gradient w.r.t. the input is not very surprising, and the fact that the analysis of the whole paper relies on this observation makes me feel that the results are not very strong. Therefore, I maintain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "ChFrYJOxeYK", "reviewer": "Reviewer_9MLt", "summary": "The paper studies the connection between the complexity of a function fitted by a neural network and the complexity of the training trajectory. The paper is mostly theoretical and contains several main results. The first main theorem gives bound on the length of the weight trajectory in terms of the Lipschitz constant of the network. The second theorem gives a bound for the Lipschitz constant of the network at a point away from the training set. The third result gives a bound on generalization error. Some experiments are provided to illustrate the conclusions of the paper.", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I'm not sure that I understand this paper. My general impression is that it poses reasonable questions and makes some interesting analysis, but somehow I don't see a clear picture resulting from it. For example, already after Theorem 1 the authors state that this theorem  \"shows that lower complexity learners will have a shorter bias trajectory\". This is debatable for many reasons. First, the choice of the Lipschitz constant as an indicator of complexity is questionable (is a linear function with a large Lipschitz constant more complex than a nonlinear function with a small Lipschitz constant but many different local variations?). Second, the established inequalities only concern the biases, which are often not even used in practical networks. Third, the inequalities involve singular values of the weight matrices, which may vary in a very wide range and be quite different for different learners. So Theorem 1 doesn't really clear things up for me. I also have similar impressions from the other results of the paper. The experiments presented in the end of the paper demonstrate some natural effects of complexity (more complex functions take longer to learn, have higher test losses, correspond to a higher distance from initialization, etc.) that agree with the results of the paper but could be anyway expected even without the developed theory, just on general grounds.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "-", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "9E4t1aX_khA", "reviewer": "Reviewer_8FRD", "summary": "This paper studies the connection between the network’s complexity, its weight’s trajectory during training, and its generalization capabilities. Theorem 1 shows that the trajectory length of the biases in the first layer is both lower and upper bounded by terms that depend on the average Lipschitz constants close to the data points. Next, in Theorem 2 it is proven that the Lipschitz constant close to points outside of the training set is upper bounded by the trajectory length of the biases in the first layer. In Theorem 3 the authors give a generalization bound (when training with dropout) which depends on the data manifold dimensionality, instead of growing exponentially with the depth. Finally, several experiments are made to validate the theoretical claims.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think this is a very interesting paper, giving several good results about the behavior of neural networks during training, and their generalization capabilities. First, bounding the trajectory length of the parameters (in this case, the bias of the first layer) by the Lipschitz constant of the network close to the dataset is an interesting result by itself. Next, the result in Theorem 2 is interesting for extrapolation analysis, where we want to study the behavior of the network outside the training set. Finally, the generalization bound which depends on the data manifold dimensionality and the steadiness of the function is very interesting in my opinion, as it does not grow exponentially with the depth, like previously known generalization bounds.\n\nThe experimental part is satisfactory in my opinion, testing on a synthetic dataset, and a subset of CIFAR-10. To this end, the correlation between the trajectory length and the generalization capabilities is very interesting.\n\nA couple of minor issues:\n1) Theorem 1 requires a lower bound on the number of iteration T. Is there some guarantee that this bound can always be achieved? e.g. what if \\sigma_n(W_1) goes to zero as fast as 1/T, this would require that T=Omega(T^2), no?\n\n2) I think the authors should explain in more detail the reasoning behind the focus on the bias in the first layer. This is a crucial part of the paper, and the explanation is a bit shallow. A derivation of how in general the Lipschitz constant of the network without the first layer depends on the bias and the singular values of the matrix in the first layer.\n\n3) I think it would be more natural to phrase Theorem 3 where the bound depends on the local Lipschitz constant of the data instead of the \\varphi parameter connected to the steadiness of the network. Maybe this can be done by using a similar setting to Theorem 1 and deriving \\varphi in terms of the local Lipschitz constants.\n\n4) The choice in CIFAR-10 of separating 'dog' and 'airplane' is a bit weird. Is there a reason these two specific classes were chosen?  It would be more convincing if more classes are considered - i.e. keeping it a binary classification task, but having several experiments for several other classes. Otherwise, it makes one wonder if there is something different for the two chosen classes.\n\n5) Just a suggestion, there are several experiments made in the appendix which are not even mentioned in the main text (MNIST, total trajectory length, effect of batch size and architecture on the trajectory). I suggest mentioning all the experiments made in the appendix, even in a single sentence, and referencing to them in the main text. This would give a better view of the empirical contribution of the paper.\n\nTo summarize, I think this is a good paper with interesting results, and it should be accepted to NeurIPS.\n\n----- Post rebuttal update-----\n\nI am satisfied with the author's response and retain my score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The majority of reviewers were positive about this paper, commending the connection it makes between generalization and training dynamics.  Nonetheless, several technical concerns were raised, in particular:

* The paper equates "complexity" with "small Lipschitz constant".  Obviously small Lipschitz constant is sufficient to ensure generalization, but as far as the committee is aware of it is not necessary.  Identifying the two will potentially mislead the uninformed readership.

* The learned parameter to which the analysis mostly applies is the bias in the first layer.  It is perhaps a bit trivial to associate Lipschitz constant with the first layer bias, as the gradient with respect to this bias and with respect to the input are equal.  Reviewers felt that this might be an indication of the analysis being somewhat fragile and not representing overarching phenomena.

Despite the above, the paper was deemed interesting and significant enough to warrant acceptance.  I encourage the authors to be more transparent with regards to the above points and clearly highlight the limitations of their framework in the text.
Decision: Accept (Poster)