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
C 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)) 12. The latter is typically upper bounded by Xprid = Ih Will| 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//loerr 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
16 (b(+t) (++1) 112
S P for all 22T. T.
ax Eytt) (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 eus (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 11 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
(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( - 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 < Apan
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 14) 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- calance-to-initalle 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.03523 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///g//bbb//oooeeeeeeeeg 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 03399700000303...00 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.:..01..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": "kHWePgx5QUeL", "reviewer": "Reviewer_juSM", "summary": "Note: this is a light review\n\nThe paper makes the hypothesis that the complexity of the function learned by DNNs depends on the convergence rate of its parameters (with special focus on the bias of the 1st layer) and other factors (variance of the bias, and distance from initialization).\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Clarity: The paper is not clearly written. For instance, the meaning of the term \"steadily\" is not clear in the abstract (it is defined formally later in the paper). The statements of theoretical results are not explained in text to provide an intuitive understanding.\n\nMajor problems:\n\nSome of the claims made by the authors are not concrete (but are rather casual). For instance, the first line of introduction says \"Though neural networks (NNs) trained on relatively small datasets can generalize well, often significant trial and error is needed to select an architecture that does not overfit.\". This statement has 2 problems:\n\n1. typically using a ResNet architecture works out-of-the-box for image datasets and yields SOTA performance on classification tasks.\n2. the claim that a proper selection of architecture can result in a model avoiding overfitting all together in practice is simply not true.\n\nThere is a mismatch between the claims made in the abstract/introduction section and the experimental results. The claims are mainly talking about the connection between behavior of the training process and the complexity of the DNN function learned (line 21). This suggests that the authors are considering the case where given a fixed dataset, if we change optimization hyper-parameters (or other factors), it will result in a change in the behavior of the training process which should be indicative of the complexity of the learned DNN function. However, the experiments use datasets with different levels of corruption or target functions with varying complexity (as measured by their frequency components). These experiments do not shed light on whether the behavior of training process can be indicative of the learned hypothesis (because to study that, one would have to fix the target function). Another problem is that these experimental findings are not novel. It has been shown in [1] that the complexity of the target function impacts the speed of convergence of DNN training. The additional plot provided by authors involving the converge rate of the bias of the first layer of the DNN is not surprising because of this simple reasoning: if the training/test loss has not converged, the parameters of the DNN must not have converged also.\n\nFurther, I find the choice of making the bias of the 1st hidden layer of a DNN the main object of analysis (viz complexity of the learned function) debatable. Any useful information/structure about the data is captured by the DNN weights, not biases. Biases merely act as threshold values (when using ReLU activations).\n\n[1] Arpit, D., Jastrzębski, S., Ballas, N., Krueger, D., Bengio, E., Kanwal, M. S., ... & Lacoste-Julien, S. (2017, July). A closer look at memorization in deep networks. In International Conference on Machine Learning (pp. 233-242). PMLR.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "please see the main review", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4-5 hours"}, "extra_text": {}}, {"review_id": "a7s8zEqF7XO", "reviewer": "Reviewer_AHNy", "summary": "This paper investigates how certain properties of the training trajectory such as its length relate to the complexity of functions learned by ReLU networks. Complexity is quantified by way of the network's distribution of the Lipschitz constants on the linear regions of its input space. The key finding is that networks that fit the training data with a smaller average Lipschitz constant exhibit a shorter trajectory and their parameters vary less near training convergence. For training with dropout, the authors also give a data-dependent generalization bound that features a polylogarithmic dependence on the number of parameters under certain assumptions.\n", "questions": "", "limitations": "", "rating": 7, "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 found the paper reasonably well-written and the results presented coherently. The techniques used in the paper in relation to bounding the Lipschitz constant by exploiting certain properties of ReLU networks appear novel.\n\nThe authors quantify neural network complexity by way of the Lipschitz continuity of the learned function on the linear regions of the input space. For ReLU networks, locally the Lipschitz constant is given by the norm of the gradient at any point within that region. The authors build on the observation that if the learned function has a large Lipschitz constant near an input datum, then SGD updates the bias of the first layer more quickly. Thus, for linear regions close to the training data, one can infer the average Lipschitz constant of the learned function by observing how fast the bias is updated. The authors show that the length of the optimization trajectory (with high probability over the SGD sampling) grows linearly with the average Lipschitz constant of the network. \n\nSimple experiments studying the training behavior on two tasks, namely, fitting sinusoids of increasing frequency and classifying CIFAR-10 images with increasing label corruption lend support to the theory: given two networks that fit the training data equally well, the one implementing a higher complexity function exhibits a longer trajectory with the weights having bigger variance near training convergence. The authors also show how the analysis can be extended to regions of the input space that are outside the training data. \n\n\nThe proof for the upper bound in Theorem 1 assumes that the smallest singular value $\\sigma_n(W_1^{(t)})$ is positive. This condition is missing in the statement of Theorem 1.\n\nMinor:\n\nl.123 (Sentence): that yield same activation pattern --> that yield the same activation pattern\n\nl.229 (Sentence) \"Furthermore, denote by ... used in the last layer.\" -- add, respectively: Let $S_T$, $\\varphi_T$, $\\mu_T$ denote, respectively, ...\n\n\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Addressed by the authors. I do not foresee any potential negative societal impact of this work.\n", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "Zs9JnlKw-bL", "reviewer": "Reviewer_i77r", "summary": "The paper attempts to understand the complexity of the function learned by a model from the training behavior of its weights. The authors consider neural networks with ReLU activation. The 3 main results are:\n\n(a) The length and variance of the trajectory of the bias of the first layer can be bounded by a function of the Lipschitz constant close to training data.\n\n(b) The Lipschitz constant (for steady learners) can also be given for regions not present in the training data, provided the activation pattern in the region is covered by the activation patterns of the training data.\n\n(c) The authors give a data-dependent and training-dependent generalization bound for steady learners with Dropout. The proof involves bounding the global Lipschitz constant, which requires a simplified assumption that all the neurons have non-zero activity without Dropout in the training set.\n\nThe authors corroborate their findings with an experimental study.", "questions": "", "limitations": "", "rating": 7, "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": "The paper tries to understand the relationship between the SGD trajectory and the complexity of the learned function. The authors come up with a novel strategy to look at the trajectory of the bias of the first layer. The novelty of the technique comes from cleverly utilizing the fact that a ReLU network divides the input space into multiple linear regions and then connecting the bias to the Lipschitz constant of the linear classifier in each region. A couple of previous works try to connect the trajectory of weights of the model to the complexity of the function learned. However, most of the analyses were in the NTK or the mean-field regime. The strength of this work is that it assumes nothing on the initialization of the neural network. \n\nHowever, I have a couple of questions and few suggestions:\n\n(1) In theorem 1, the assumption to keep the upper bound finite is $\\sigma_n (W_1^{(t)}) > 0$. I think the authors should explicitly mention it in the theorem statement. What happens when the data comes from a low dimensional space $k < n$, and the input layer weights have to fit that subspace? Can the bounds then be changed to $\\sigma_k(W_1^{(t)})$ in some trivial way? \n\n(2) What do the authors mean by the statement \"a larger complexity NN will need to fit the training data more closely to achieve the same variance as that of a lower complexity NN\" (line 189)? What parameters in Corollary 2 do I need to compare to get this statement (e.g. $\\epsilon^{\\mathrm{var}}_{ f^{(t)} }$, and the Lipschitz constant)?\n\n (3) I believe you need more conditions to claim Corollary 1. I think the result that you can claim from theorem 1 and definition 1 is that given a set of iteration indices $T \\ge \\tau$ for a $(\\tau, \\varphi)$-steady learner, with $|T|$ large enough, $\\frac{1}{T} \\sum_{t \\in T} \\lambda^{avg}_{f^{(t)}} (X) \\le \\beta \\varphi$.  How is this related to the Lipschitz constant of every training data point after $t \\ge \\tau$, provided you don't assume how the Lipschitz constant changes for a steady learner? \n\n(4) Can the authors explain how Dropout helps in Theorem 3? I guess, Claim 1 in the appendix is the main underlying tool. However, the proof contains multiple notational issues (e.g. what is the meaning of $\\sum_{i=1}^{k} s_{ t, l }(x)$?). But I can guess the strategy is that since Dropout drops neurons with a probability of $1/2$,  and the assumption that all the neurons have some activity in the training set, one can show that the activation patterns of the training set (along with Dropout masks) can form a basis of the activation pattern of the entire region with some non-zero probability. That will now help to get a bound on the global Lipschitz constant from Theorem 2. \n\nIt will be great if the authors can mention 2-3 lines on how dropout helps in the main paper.\n\n(5) In the experiments on regression of a sinusoidal function, the authors have set the first layer of the MLP to Identity. How do the experimental observations change if they don't fix it to Identity? \n\n(6) It will be interesting to see if the experimental observations stay the same for trajectories of biases of the other layers. \n\n**Notation issues\n\n$\\lambda_f^{\\mathrm{steady}}$ has never been defined in the main paper.\n\nI enjoyed reading the paper since it makes a novel attempt at understanding the connection between the trajectory of neural networks and the complexity of the function learned. The proofs are simple to understand (baring notational issues in the appendix), which is a strength of this paper. My scores are slightly lower since I need to make sure I understand the use of Dropout in theorem 3. I am happy to increase my score after discussing it with the authors and other reviewers.\n\n\n***After Rebuttal***\nI have increased my score to 7. I would request the authors to make changes to the paper to address the different clarity issues mentioned by the reviewers.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors mention the limitations and the future directions of their work. Since the paper discusses a theoretical connection between trajectory and the Lipschitz constant of the neural network, I don't foresee a potential negative impact (to the best of my knowledge).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 - 7 hours"}, "extra_text": {}}, {"review_id": "ROwmvafA4bO", "reviewer": "Reviewer_j63f", "summary": "The paper presents an analysis of learning dynamics of neural network that relate the trajectory of changes in the first layer bias of neural network to bounds on Lipschitz constant, and thus the complexity of the model.   In other words, the authors establish that behaviour of first layer’s bias during training is a good predictor of the trained model’s complexity. ", "questions": "", "limitations": "", "rating": 7, "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": "Though the main logic of the argument is somewhat straight forward – Lipschitz constant of a network is linked to complexity, gradient of the entire network is linked to Lipchitz constant, therefore the trajectory of first layer bias, which depends on that gradient, is linked to complexity of the entire model – I think a rigorous mathematical treatment and the results presented are worth of notice.  The paper is written well and the ideas are presented clearly. \n\nI think the results in Ch 4 for complexity around the training points are interesting, though it is clear that from practical point of view, trajectory of bias alone is not sufficient to gauge complexity, as one also has to take into account singular values of W_1, which would change during training.\n\nI do have a bit of an issue when it comes to complexity analysis when “far from training data”.  Specifically, if my understanding of Assumption 1 in Ch 5 is correct,  it allows changes of parameters in the model as long as long as the activation patterns (which ReLU neurons switch on and which one stay off)  stay the same.  Doesn’t that make the neural network essentially a linear model?  While this makes the analysis possible, it throws away the thing that makes neural networks useful…and I suspect, the Assumption is not likely to hold in practice \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "Oi9usGtPum", "reviewer": "Reviewer_7TvM", "summary": "The authors measure the complexity of the learned function of NN by the distribution of an approximation of its Lipschitz constants. They analytically show that the average of the Lipschitz constants at the beginning of the learning process can predict various aspects of the entire learning process, which could possibly allow picking the right architecture in a faster way.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper tackles an interesting topic, from a theoretical approach. As far as I can tell, this approach is new and can shed light on several aspects of NN training dynamics, which could be beneficial to the community.\n\nHowever, this paper also has many faults:\nThe paper is very hard to read and even harder to understand. It is composed of many equations, with a stunning amount of notations and abbreviations. The paper introduces a large number of bounds, and the distinctions between them could be better explained. The paper lacks some high-level overview, which can better explain the motivation and usage of each bound.\n\nThe empirical part of the work feels premature. The authors merely explain the settings of each experiment, without clear motivation or analysis, which again makes it very hard to follow. The experiments are done mostly in toy settings, and it is unclear if they could be extended to real problems, raising concerns about the validity of the motivation.\n\n\nSince this work is not directly in my field of studies, some of my concerns may be due to my unfamiliarity. Therefore, I tend to accept this paper, but as I can not give it a higher score than \"marginally accept\" with its current issues.\n\n\n----------------------------------------------------------\n\nPost rebuttal:\nAfter reading the authors' response and the other reviews, I'm more confident than my original review that this is indeed a good paper, which should be accepted. As other reviewers also mentioned the readability issues, which in my opinion, are a significant problem with this version, I'll keep my score as \"6: Marginally above the acceptance threshold\", and raise my confidence score to 3.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not relevant", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Five knowledgeable reviewers recommend this paper for acceptance. Most concerns from the reviewers were addressed during the discussion and some reviewers increased their score after the discussion. One reviewer comments that this submission presents very concrete strong theoretical contributions, with a simple empirical study supporting them. I agree with the reviewers. Hence I recommend this paper for acceptance. For the preparation of the final manuscript, I encourage the authors to take the reviewers comments carefully into consideration. In particular: One reviewer is still concerned about the clarity of the paper. One reviewer mentions s/he doesn’t think the lack of experiments in the large scale setting is a primary weakness of this paper, but that having them would be great. Another reviewer still thinks that the quality of the paper could be greatly improved if it included some experiments (even if toy) to confirm the theoretical findings more directly and provided concrete suggestions. Another reviewer found that his/her questions were well addressed, but s/he still has some reservations about Assumption 1 and is not sure there is any chance it would hold in practice (although s/he does not see this as a major problem for the purposes of the theoretical analysis). 
Decision: Accept (Poster)