A Generalization Bound for Nearly-Linear Networks
Authors: Eugene Golikov
Venue: Accepted by TMLR ()

Abstract: We consider nonlinear networks as perturbations of linear ones. Based on this approach, we present a novel generalization bound that become non-vacuous for networks that are close to being linear. The main advantage over the previous works which propose non-vacuous generalization bounds is that our bound is *a priori*: performing the actual training is not required for evaluating the bound. To the best of our knowledge, it is the first non-vacuous generalization bound for neural nets possessing this property.

Published in Transactions on Machine Learning Research (12/2024)
A Generalization Bound for Nearly-Linear Networks
Eugene Golikov
enyensi.golkkkodeeppp...
Choir of Statistical Field Theory
École Polytechnique Fédérale de Lausonne (EPFL)
Reviewed on OpenReview: https: // optnr/veew.eeeeeeee net/ forum? id= tRpwak3phhh
Abstract
We consider nonlinear networks as perturbations of lincar ones. Based this approach, present novel generalization bound that become non-vacuous for networks that are close to being lincar. The main advantage over the previous works which propose non-vacuous generalization bounds is that our bound is priori: performing the actual training is not required for evaluating the bound. To the best of our knowledge, it is the first non-vacuous generalization bound for neural nets possessing this property.
1 Introduction
Despite huge practical advancements of deep learning, the main object of this field, neural network, is not yet fully understood. As we do not have a complete understanding of how neural networks learn, we are not able to answer the main question of deep learning theory: why do neural networks generalize on unseen data?
While the above question is valid for any supervised learning model, it notoriously difficuult to answer for neural nets. The reason is that modern neural nets have billions of parameters and as a result, huge capacity. Therefore among all parameter configurations that fit the training data, there provably exist such configurations that do not fit the held-out data well (Zhang et al. 2021). This is the reason why classical approaches for bounding generalization gap, i.e. the difference between distribution and train errors, fall short on neural networks: such approaches bound the gap uniformly over a model class. That is, if weights for which the network performs poorly exist, we bound our trained network's performance by performance of that poor one.
As we observe empirically, networks commonly used in practice do generalize, which means that training algorithms use (i.c. gradient descent its variants) choose "good" parameter configurations despite the existence of poor ones. In other words, these algorithms are implicitly biased towards good solutions.
Unfortunately, implicit bias of gradient descent is not fully understood yet. This is because the training dynamics is very hard to integrate, or even characterize, analytically. There are two main obstacles we could identify. First, modern neural networks have many layers, resulting in a high-order weight evolution equation. Second, activation functions we use are applied to hidden representations clementwise, destroying nice algebraic structure of stacked linear transformations.
If we remove all activation functions, the training dynamics of gradient descent can be integrated analytically under certain assumptions (Saxe et al.) 2013). However, the resulting model, a lincar network, is as expressive as linear model, thus loosing one of the crucial advantages of neural nets.
Idea. The idea we explore in the present paper is to consider nonlincar nets as perturbations of lincar ones. We show that the original network can be approximated with a proxy-model whose parameters can be computed using parameters of a linear network trained the same way as the original one. Since the proxy- model uses the corresponding lincar net's parameters, its generalization gap can be meaningfully bounded with classical approaches. Indeed, if the initial weights are fixed, the result of learning linear network minimize square loss dataset (X Rddm Y Redu Xm) is determined uniquely by Y E Rddu Xd and

---

Published in Transactions on Machine Learning Research (12/2024)
XXT E Bddd where d, dout are the input and output dimensions, and m is the dataset size. The number of parameters in these two matrices is much less than the total number of parameters in the net work, making classical counting-base based approaches meaningful.
Contributions. Our main contribution is a generalization bound given by Theorem 5.2 which is ready to apply in the following setting: (1) fully-connected networks, (2) gradient descent with vanishing learning rate (gradient flow), (3) binary classification with MSE loss. The main disadvantage of our bound is that it diverges training time goes to infinity. We discuss how to choose the training time in such way that the bound stays not too large while the training risk diminishes significantly, in Section 5.3 We validate our bound on a simple fully-connected network trained on a downsampled MNIST dataset, and demonstrate that it becomes non-vacuous in this scenario (Section [). We list advantages and disadvantages of our bound over that of existing generalization bounds in Section 2 We discuss the assumptions we use, as well as possible improvements of our bound, in Appendix [ Finally, we discuss how far the approach we choose in this work, i.e. generalization bounds based on deviation from specific proxy models, could lead in the best case scenario (Appendix B
2 Comparison to previous work
Advantages.
The bound of our Theorem 5.2 has the following advantages over some other non-vacuous
bounds available in the literature (e.g. Biggs & Guedj (2022); Galanti et al. (2023 Dziugaite & Roy (017):
Zhou et al. (2019)):
1. It is priori bound, i.e getting the actual trained the model is not required for evaluating it. To the best of our knowledge, it is the first non-vacuous priori bound available for neural nets. All works mentioned above, despite providing non-vacuous bounds, could be evaluated only on a trained network thus relying on the implicit. bias phenomenon which is not well understood yet.
2. Related to the previous point, to the best of our knowledge, our bound is the first to incorporate the implicit bias of gradient flow explicitly. This done by demonstrating that the model does not. deviate much from a specific proxy model. The class of realizable proxy models has a small number of effective parameters. Informally, this indicates that this class is "simple"; hence the gradient flow is biased towards this simple class, and our bound exploits this property.
3. It docs not require hcld-out dataset to evaluate it, compared to Galanti et al. 2023) and coupled bounds of Biggs & Guedj (2022). Indeed, if one had held-out dalaset, they could just use it directly to evaluate the trained model, thus questioning the practical utility of such bounds.
4. It does not grow with network width. In contrast, PAC-Bayesian bounds, Biggs & Guedj 2022 Dziugaite & Roy 2017): Zhou et al. (2019), might grow with width.
5. Similarly to Biggs & Guedj (022)) Galanti et al. (202)), we bound the generalization gap of the original trained model, not its proxy. In contrast, Dziugaite & Roy (2017) introduces a Gaussian noise to the learned weights, while Zhou et al. (2019) crucially relies on quantization and compression
after training.
Related to the second point, we bound the generalization gap for the proxy model with simple parameter- counting bound (similar to that of Vapnik & Chervonenkis (1971)), thus demonstrating that, contrary to a common judgement, such bounds could be useful in the context of models with many more parameters than data points.
Disadvantages. For fair comparison, we also list the disadvantages our present bound has:
The bound of our Theorem 5.2 becomes non-vacuous only when the following two conditions hold.
First, a simple counting-based generalization bound for a lincar model evaluated in the same sctting should be non-vacuous. Such bound is vacuous even for binary classification on the standard MNIST dataset, but becomes non-vacuous if we downsample the images.
2

---

Published in Transactions on Machine Learning Research (12/2024)
2. Second, the activation function has to be sufficiently close to being linear. To be specific, for two-layered leaky ReLU neural net trained on MNIST downsampled to 7x7, one needs the negative slope to be not less than 0.99 (1 corresponds to a linear net, while ReLU corresponds to 0).
3. One may hope for the bound to be non-vacuous only for partially-trained network, while for a fully-trained network the bound diverges.
4. Even in the most optimistic scenario, when we manage to tighten the teriss of our bound as much as possible, our bound stays non-vacuous only during the carly stage of training when the network has not started "exploiting' its nonlinearity yet (Appendix B). However, the minimal negative ReLU slope for which the bound stays non-vacuous is much smaller, 0.6.
3 Related work
Non-vacuous generalization bounds. While first generalization bounds date back to Vapnik & Chervo nenkis (171)), the bounds which are non-vacuous for realistically large neural nets appeared quite recently. Specifically, Dziugaite & Roy (2017) constructed a PAC-Bayesian bound which was non- non-vacuous for small fully-connected networks trained on MNIST and FashionMNISST. The bound of Zhou et al. (2019). also of
PAC-Bayesian nature, relies on quantization and compression after training. It ends up being non-vacuous for VGG-like nets trained on large datasets of ImageNet scale. The bound of Biggs & Guedj (2022) is the first. non-vacuous bound that applies directly to the learned model and not to its proxy. It is not obvious whether their construction could be generalized to neural nets with more than two layers. The bound of Galanti et al.) (022) is not PAC-Bayesian in contrast to the previous three. It is based on the notion of effective depth: it assumes that a properly trained network has small effective depth, even if it is deep. Therefore its effective capacity is smaller than its lotal capacity, which allows for a non-vacuous bound. See the previous section for discussion of some of the features of these bounds.
A priori and a posteriori generalization bounds. Most of the generalization bounds available in the literature are a posteriori. That is, some PAC-Baycsian bounds (Dziugaite & Roy 2017 Neyshabur itt al. 2018 Biggs Guedj] 2022), as well as Rademacher complexity-based bounds (Bartlett et al. 2017],
depend on norms of learned weights, or distances between the learned weights and their initializations, so they cannot be computed before these norms distances are known. The bound of Zhouu et al. (2019)
depends on the trained model size after compression and quantization, which cannot be predicted before training and compression. That is, this bound implicitly relies on the fact that the training procedure prefers well-compressible models; to the best of our knowledge, this fact does not have a solid explanation yet. The bound of Galanti et al. 2023) depends on a so-called effective depth of a learned model, which also cannot be predicted in advance.
The only a priori bounds we are aware of are the classical uniform bounds based on VC-dimension and Rademacher complexity, see Vapnik & Chervonenkis (1971). These bounds grow with model expressivity, hence with both width and depth, which make them vacuous in most of the practical scenarios involving neural nets. The reason they are vacuous is also related to the fact that among all models that interpolate the data, one can often find a model that does not generalize well, see empirical results of Zhang et al. (2021). Uniform bounds bound the generalization gap in the worst case, hence a 'bad' model exists in our model class, the whole generalization bound has no chance be good.
Overall, generalization bounds that use some complexity of the whole function class fall short due to the trade-off they impose: low complexity provably good generalization, high complexity maybe poor generalization. Modern neural architectures are deep and wide, hence they have high complexity, while they still generalize well. The reason is that the training procedure we often use is likely to be implicitly biased towards well-generalizing solutions. If we bound the generalization gap uniformly over the whole function class, we ignore this effect. The a posteriorí bounds we discuss above do take some form of implicit bias into account (i.c. low weight norm, compressibilityy etc.). So does our bound: we exploit the fact that a nearly linear network is close to a proxy which uses only weights of linear network. In their turn, the trained weights of linear network depend only few parameters long as their initialization is given. The
3

---

Published in Transactions on Machine Learning Research (12/2024)
difference is that our bound does not need any prior info about the learned weights (only on their initialization and the optimization procedure); hence it is a priori.
Linear networks training dynamics. The pioneering work that integrates the training dynamics of a linear network under gradient flow to optimize square loss is Saxe ct al. (2013). This work crucially assumes that the initial weights are well aligned with the eigenvectors of the optimal linear regression weights Y X*, where (X,Y) is the train dataset. As the initialization norm approaches zero, the learning process becomes more sequential: components of the data are learned one by one starting from the strongest. Li et al. (2021) conjecture that the same happens for any initialization approaching zero excluding some set of directions of measure zero. They prove this result. for the first, the strongest, component, but moving further seems more challenging. See also Yun et al. (2021); Jacot et al. (202I). We note a recent result of Tu et al. (2024) who propose a so-called mixed dynamics for two-layered linear networks that does not suffer from this issue.
Nearly-linear neural nets. Our generalization gap bound decreases activation functions get closer to linearity. While nearly-linear activations do not conform with the usual practice, nearly-linear networks have been studied before. That is, Li et al. (2022) demonstrated that when width n and depth L go to infinity with constant ratio, the hidden layer covariances al initialization admit a meaningful limit as long as the ReLU slopes behave as 1 S/, i.e. become closer and closer to linearity. Noci et al. (2024) explored a
similar limit for Transformers ( (Vaswani et. al. 2017). Another example is Kumar et al. (0024) who used a toy small- model to explain the phenomenon of grokking (Power et al. 2022) as delayed feature learning.
Linearized training of neural networks and NTK. It is important to emphasize that linear networks we consider in the present work are fundamentally different from the NTK model introduced by Jacot et al. (2018) resulted from linearized training of neural network. That is, by linear network we mean network fo(z) who is linear in its imput, z, but not necessarily in its weights 0. Whereas if we linearize the training procedure, the trained model becomes linear in 0, but not in x. Jacot et al. (018)) demonstrated that training a neural network becomes equivalent to training a kernel method under specific (non-standard) parameterization as width goes to infinity (NTK limit). Since training a kernel method is equivalent to training a random feature model with sufficiently large number of features, the corresponding training procedure is indeed linear in weights. See also Yang & Littwin (2021) for proving NTK limit for general architectures, and Chizat et al. (2019) for demonstrating linearized training for large weight initializations.
As in the NTK limit training neural net becomes equivalent to training a kernel method, features the model uses stay the same over the whole process of training. In other words, the model does not enjoy fealure learning when training is linearized. In contrast, even a linear network with two layers trained with gradient descent does demonstrate feature lcarning: see Saxe et al. (2013); Tu et al. (2024). The feature learning it exhibits is kernel alignment and a so-called momentum effect: the associated kernel (NTK), or equivalently, the features the model uses, aligns over strong components of the data and extends along them Tu et al., (2024). This way, these strong components get learned first, before weak components, often resulted from data noise.
We also emphasize that the proxy models we use to prove our results, while exploiting weights of a trained linear network, are not linear themselves; neither in æ, nor in weights. Therefore they do not suffer from expressivity issues as linear networks (which are all functionally equivalent to linear models x - Wr), while they do enjoy feature learning (since linear networks do).
Therefore our approach is quite orthogonal to NTK and generalizability of kernel methods. In terms of high-level methodology, the closest paper we could mention is Arora et al. (2019), where they consider a two-layer NTK- parattraaetteri MLP, and prove a generalization bound for it when width is sufficiently large. For this, they combinc a generalization bound for the infinito-width limit when the kernel is constant, and a term that takes into account the fact that the kernel for finite width deviates from the limit one. Whereas what we do is we combine a generalization bound for a proxy model that exploits the weights of a linear network and a proxy deviation bound. The bound of Arora et al. (2019) becomes good when the width is large (hence the finite-width NTK is close to the limit NTK), while our bound becomes good when the activation functions are close to be linear (hence the proxy does not deviate from the original model much).
4

---

Published in Transactions on Machine Learning Research (12/2024)
4 Our approach
Before formally stating our main bound, we present the high-level approach for constructing generalization bounds we take in our work.
Genoralization bound based on proxy models. Let f be model trained on a binary classification lask. We will look for a proxy model that satisfies the following properties: (1) it is close enough to J, and
(2) the generalization gap for g could be bounded well enough. Given such g, we bound the distribution risk of f as follows:
11 + BBwo)(())) - g(x)) +
m
Rifl S R
Σ - 9(xx))
(1)
7 m k=1
where y > 0 and we used three different risk functions:
Misclassification risk: r(y, 9) = [v0 < 0],
2. Margin risk: (u 0) [vú ?),
3. Continuous margin risk: r-((:) ú) = lv0 < 0] + (1- 4) l&0 E 1l,
giving rise to the distribution risk R[f] = E z.y>Dr(y. f(x)), and similarly Ry[f] and RYIf), and its empirical counterpart R[s] # >m-,r(u- f(x)),, and similarly [f] and RG[5]. Here D is the data distribution, and (It, 1k) is the training dataset samled from D in an iid manner.
We derived Equation [I simply from the fact that (- 3) is 1/7-Lipschitz, and r S S S r-,, see Equation 22
below for more elaborate derivation. The first term on the right hand side of Equation (1) is the empirical margin risk the original model f. The second term is the generalization gap of the proxy-model (with respect to continuous margin risk) which we assume to be easy to bound. The two remaining terms are deviations of g from f averaged over the whole data distribution D and the dataset, divided by 7. The parameter y controls the trade-off between the first term and the other three: the first term increases with y (eventually reaching 1), while the other three decrease.
Proxy models for a nearly-linear network. The problem now boils down to finding good proxy that approximates the trained model f well, and whose generalization gap could be well-bounded. Let fā(x) be a neural network with parameters 0, imput x E Idd scalar output, and activation functions d=()) = z + ex)(2, & is a positively homogeneous map (e.g. ReLU). That is, fg (z) is linear in x (but not necessarily in 0). and characterizes the deviation from linearity.
Let fūr be the trained model whose generalization gap we would like to bound, and let fú be a linear model trained the same way. We consider the following proxies: 91(x) for (z) and 92(x) 91 (1)) + (fz. (X) 91 (X)) Xtx, where X E Bdxm is matrix with rows (xx) and X+ is its Moore-Penroed pscudo-inverse.
In words, the first proxy is a nonlinear network that uses weights the trained linear one, while the second proxy results from linearly correcting the first one on the train dataset. These proxies deviate from the original model as follows: (gx(z) fz. ( O(e") for R E (1,2) and any given z E Rdd
Under certain assumptions, 00 the trained línear model weights, depend only Yx+ E Rdd where Y E Rixd is a row-vector of targets. Since 91 is fully described by 09, the class of models realizable by it has only d parameters. Since 92 is merely 91 plus lincar correction, its respective class of models has only d d d 2d parameters. In both cases, the number of parameters the proxy has is much smaller than the total number of weights of the network, which is (d + 1)n + (L - 2)n?. Then classical uniform bound techniques (Vapnik
& Chervonenkis 1971; result in a generalization bound for proxy models that grows as depends neither on width of the network,
ud This bound
its depth.
5

---

Published in Transactions on Machine Learning Research (12/2024)
5
Main result
Notations. For integer L 2 0, [L] denotes the set (1...., L}. For integers 1 1 L, [I,]] denotes the set (l...., LJ. For a vector 2, ||=||| denotes its Euclidean norm, while ||=]]] denotes its 4-norm. For a matrix X, [X]] denotes its maximal singular value, while ||X]] denotes its Frobenits norm.
5.1 Setup
Model.
The model we study is a fully-connected LeakyReL.U network with I layers:
(x(x) W
=8,0(2) = x, (0) = de (Wirh.-1(1) v [1-11 1},
(2)
where I denotes the vector of weights, i.e. = cat((vec(Wi))HE.) Wi E R" E [4]. and of is
Leaky ReLU with negative slope 1 e, that is:
(z) eminn((.x))
33)
Since we are going to consider only binary classification in the present work, we take nt. = 1. We also define d = no to denote the input dimension.
Data. Data points (x,y) come from a distribution D. We assuine all from D to lie on a unit ball, ||^|| S 1, and y 1-, During the training phase, we sample set of m points iid from D to form dataset (X, Y), where X E Rdxm and Y 11xm
Training. Assuming rk X = d (which implies m 2 d, i.e. the data is abundant), we train our model on X, where
(X,Y) with gradient flow to optimize square loss on whitened data, ie. on (X, Y) for X xx//2x Σx 1 XXX Iddd is an empirical feature correlation matrix. That is,
Y fo (o (1))
dW)
2m
E [4].
(4)
dt
OW,
Note that X mla.
Inference. To conform with the above training procedure, take the model output at point to be Ji (D-1/2x), where Σ is a (distribution) feature correlation matrix: Σ = E (xxx))D(xxx E Raxd, We assume this matrix to be known; in practice, we could substitute it with Σx.
Slightly abusing the notation, we define the empirical (train) risk on the dataset (X, Y) and the distribution risk the model trained for time as
Performance measure. Recall the definitions of r, ry, and r from Section 4
R (t) 1.-1-n
Σ (un
R*(t) = E (aa))Dr' (u. (1.
(5)
We define (1) and (C)(() analogously to (e),), and Pes and RC)=(1) analogously to Pe (1).
5.2 Generalization bound
We will need the following assumption on the training process:
[[ (ē (8)) | < (r (0) XT] F
Assumption 5.1. 11 2 0
Note that Y Y fg (x)| < -2 (x) since we minimize the loss monotonically with gradient
flow. This implies that the above assumption holds automatically, whenever X is (scaled) orthogonal matrix

---

Published in Transactions on Machine Learning Research (12/2024)
(which happens when = d). It is easy to show that it provably holds for linear network (e 0), see Appendix B and we found this assumption to hold empirically for all of our experiments with nonlinear networks too, see Figure 7
We are now ready to formulate our main result:
Theorem 5.2. Fir 3,y 0, t 0, 8 e (0, 1), E [0,1], and {1.2}. Let p be the floating point arithmetic precision (32 by default). Under the setting of Section 5.1 and Assumption 5.1 for any weight initialization satisfying [|W] (0)1l S B vI E [L], w.p. 2 11- - over sampling the dataset (X.Y).
R³(1) S (t) T. + (n,(())
(6)
for the terms in the rhs defined
kadd In 2 + In(1/6)
Yx
Ax, (x
(7)
2m
where
Lvd+1+ 1)p,
1;
2 (L- (I 1)p) 2(1 (L (L- 1)p) (1))
(8)
2,
where I (O)lE is the square rool of the stable rank of the inpul layer al initialization, and the definilions [W[[ of ug and ug are given below. Define
-=||rxTxx"
1=1+ 1 pBL;
For given
2 0, Sy (1 e)(s + (orr(L11)(C p34);
31;
$ 1+(L 1)p
1
B B=
We have
Beer
L= 2;
(t)
(9)
( - 101--(1-- -(I-2)31) +
2 3;
L- 1 2- 1- ( w( 1/:0
(t)
8
u
(10)
L
where
2 I.
u
2 4b
w(u)
T
(11)
L
8
L
$
This theorem gives priori bound for the generalization gap R Re. i.e. it could be computed without performing the actual training.
Dimension dependency. Our bound docs not depend on width n, Al E [L [L 1], in contrast to the bounds of Dziugaite & Roy (2017): Zhou et al. (2019); Biggs & Guedj] (2022). However, both penalty terms of
Theorem
Y, and A (t), grow as d with the input dimension.
IT upper-incomplete fanctinnnction defined T(,, f 1 15-1e-t
7

---

Published in Transactions on Machine Learning Research (12/2024)
5.3 Choosing the training time
go-t
As we see, At,a(t) diverges super-exponentially as f + co for L = 2 and as t + (L-2)3 for L 2 3, so the bound eventually becomes vacuous. For the bound to make sense, we should be able to find L small enough for (t) to stay not too large, and at the same time, large enough for the training risk (2,(t) to get considcrably reducod.
In the present section, we are going to demonstrate that for values of l which correspond to partially learning the dataset (i.e. for which (t) E (0, 1)), the last term of the bound, ot, admits finite limit B 0
We do not know how (1) decreases with / in our case. However, when the network is linear, this can be computed explicitly when either the weight initialization is properly aligned with the data, or the initialization norm 3 vanishes. We are going to perform our whole analysis for L = 2 in the main, and defer the case L 2 3 to Appendix D.2
That is, consider an SVD: YX-
vm Y PSQ where P and Q are orthogonal and s 1 since y #1. Saxx al. 2203 have demonstrated for linear nets (c 0) and L == 2 2 that when the weight initialization is properly a aligned with P and + [[P((]] = [1] = ū((), where ū satisfie 5
is diagonal; note that S11 = s. Observe also that s = 1| S ||||||*
dā(t) ast) (t))
a(0) 3,
(12)
which gives the solution in implicit form:
/
du
(t) (s -89 32 u²(1))
t
In
(13)
u(s u²)
28
One could resolve explicitly to get
2et
ū(t)= = 2 1 + 8/
(14)
Saxe et al. 2013) observed this expression to hold with good precision for random (not aligned) initializations when 3 is small enough. This is supported by further works (Li et al. 2021: Jacot et al. 2021 when linear
network is initialized close to the origin and the initial weights do not lie on a 'bad" subspace, the gradient.
flow nearly follows the same trajectory as studied by Saxe et al. (2013).
Plugging (t) = as into Equation 13 we get the time required for a linear network to learn a fraction a of the strongest. mode:
(3) = 2s In a(s - 32)
1
(15)
(1 a).32
Clearly, the learning time (3) diverges whenever 8 + 0, or + 1.
Since t (8) is the time sufficient to learn a network for c = 0, we suppose it also suffices to learn a nonlincar network. Thus, we are going to evaluate our bound at L = E- Since we need (,, < 1 for the bound to be non-vacuous, we should take y small relative to a. We consider y = a" for v.
Since the linear network learning time t, (B) is correct for almost all initialization only when / vanishes, we are going to work in the limit of B + 0. Since we need E (82/s,11 1), otherwise the linear training time is negative, we take a _ for À E (0, 2] and r r>> 1.
IIn the linear case (c 0), this corresponds to the saddle-to-saddle regime of Jacot et al. 2021
Saxe et al. (2013) assumed X.X T = La and X = while not introducing the lactor easy to see that the our gradient flow has exactly the dynamics the studied by Saxe al. 2013).
we do in Equation 4 It is
"That is, when W2(0) = PS)/2 RT, Wi(0)= Rs!/2QT, where It is orthogonal, and S and S2 are constructed from S by adding removing rows and columns.
5 &Our a corresponds (N(())1) of Saxe al. 2013
8

---

Published in Transactions on Machine Learning Research (12/2024)
Let us compute the quantities which appear in our bounds, at t (3):
u 3 a(ss B²)
*
5 (
(16)
(1 - a=332
81
where we omitted the argument to (3) for brevity.
Since r((,,)) Ei( x) = - In r + (1) and r(1, = = 02- we have w(3) = In( ) + O(1).
Similarly, whenever 1 + 8 1) > O, we have u = o(B), and w(u) In (52+5(1-2) 0(1).
Consider first A < 2 and suppose v In this case, w(u) w(3) = = 1) In 13( + 0(1), and
2uv
52 qr -
( (1+
())
(17)
g 122-))
Since 5 2 8, this expression diverges B O. Note that we get the same order divergence even also for 1 ++3 (á 1) 0. Clearly, for 1, we get even faster divergence.
On the other hand, if X 2 then w(u) - (3) = In (2r+)++ + 03)), and
2uv
5 p
qr
In
m pa
B20
(1))
(18)
7 si
We get finite limit only for 1, i.c. when a. In this case, the last term of the bound Equation (6) becomes
Ax.
1852 p
pr 28
-,::-1,,,, In
0 2
c (03)))
(19)
7
Summing up, we expect the empirical risk (15)) be smaller than for large enough q (i.e. for small y compared to a), and the last term to stay finite B - 0 and vanish as e". Therefore long as T. is not large enough (i.e. when kpd is small compared to m), the overall bound becomes non-vacuous for small enough at least at the (linear) training time ta We are going to evaluate our bound empirically in the upcoming section.
6 Experiments
Setup. We consider an L-layer bias-free fully-comnected network of width 64 and train it to classify 0-4 versus 5-9 digits of MNIST (i.e. 60000). In order to approximate the gradient flow dynamics, we gradient descent with learning rate 0.001. By default, we take 7, = 2, the floating point precision to be 32, downsample the images to 7x7, and initialize the layers randomly in standard Pytorch way (plus, we rescale the weights to match the required layer norm B). For some experiments, we consider deeper networks, half-precision p = 16, downsample not so aggresively, or enforce the input layer weight matrix to have rank
Observations:
When we take == 2 and 3 0.1, the bound becomes nonvacuous up to 0.001 (Figure I and up to 0.01 if enforce p (Figure 3);
We can have a non-vacuous bound also for 14x14 MNIST if we take e 0.001, half-precision (p = 16), and enforce p = (Figure 5]; the bound slightly exceeds the random guess risk for the full-sized, 28x28 MNIST:
The bound for 2 is much stronger than that for (Figure
9

---

Published in Transactions on Machine Learning Research (12/2024)
7x7 MNIST; _I 1e-05, p
MNIST; 0.001, 3.93,
1.2
1.2
train
train risk, R
1.0
risk.
1.0
test
-acurary
full bound, lay (- 12, 11, 100
full bound, lay -7.
random guess risk
random guess risk
=1
0.6
0.6
0.2
0.2
training time, c
training time, C
7x7 MNIST: 0.1, 0.001, 3.93, x
7x7 MNIST: P 0.S, 0.001, 3.93,
train risk,
train risk, A
1.0
test risk,
1.0
test risk.
risk -accurecy
full bound, loyc [- 4, 3, 23
full bound, ggyc (- 3, 2, 13
random guess
random guess
0.8
0.6
0.6
risk
0.2
0.2
training time,
training time, C
Figure 1: We consider 7x7 binary MNIST, T= 2, K = 2, c= 0.001, and vary B. The bound of Theorem 5.2 converges as 3 vanishes and increases as 3 grows. The bound stays non-vacuous for a small enough 8 and a properly choosen y. We consider y = ///9 for E (1, 100}.
7x7 MNIST; f - 0.001, 0.001. pm 3.93,
7x7 MNIST: f 0.001. c - 0.001. p 3.93,
train risk,
1.0
test risk, R
1.0
risk -ccuracy
full bound. loyE (- 8, -7
random guess risk
0.8
train
test
full bound, 1gy (- 77 random guess risk
0.6
0.6
0.2
0.2
training time,
training time, t
Figure 2:
We consider 7x7 binary MNIST, L 2, 8 = 0.001, c = 0.001, and compare different kappas of The bound for R = 2 is much stronger than that for x = 1.
Theorem 5.2
0.001.
AMI
Lol
bound,
quees
04
3.0
04
0.6
love -0 randere puess
2
traiing time. 2
training 2me. c
train time. C
Figure 3: We consider 7x7 binary MNIST, 2, 0.001, = 0.01, k 2, and vary the stable rank at initialization P and floating point precision p. Initializing the input layer with a rank one matrix considerably improves the bound. Moreover, it also improves the convergence speed.
10

---

Published in Transactions on Machine Learning Research (12/2024)
1est risk,
04
Fanddrrs QUIEA 182
(GA
8
08
2 tminnng ng 200
tmainng tmm.
mmnn time
Figure We consider 7x7 binary MNIST, - 0.001, e 0.01, 2, and compare different components of the bound. The left figure corresponds to the full bound, while for the central one forget about the generalization gap bound for the proxy model Yx, and for the right one, forget about the deviation term Am.e", We see that both terms are of the same order; one therefore has work on reducing both in order to reduce the overall bound.
10
1.0
'ull bound,
Ibund. Caw.llyccccc
'ull bound, (- 7
04
014
nuinig
Eraining 2mc
brain
Figure 5: We consider binary MNIST, L 2, 3 0.001, 0.001, k= = p 16, rank one input layer initialization, and vary image dimensions. In this "gentle" scenario, the bound stays non-vacuous for 14x14 MNIST, and only slightly exceeds the random guess risk for the full-sized, 28x28 MNIST.
1.2
357 WBASTT - EIOOL, 0.000, 2 600.0.2222
767 MNIST. 10.00..
WRST.
A4
box riA.
full baans loye (-1 13,-133
0.8
randioe SUMEE
tendom risk
bunnmak
Seet nilk
killbaure
guest
02
12:00
1403
1005C0
200020
300000
400003
505000
tranigg tmc.
2aining 1in..
23lning Uni.
Figure
We consider binary 7x7 MNIST, 3= 0.001, e = 0.001, K = 2, 2, p 16, rank one input layer initialization, and vary depth. Even this 'gentle" scenario, the bound gets considerably worse with depth.
11

---

Published in Transactions on Machine Learning Research (12/2024)
0.0,
7<2 MUEET: 20,
2008 MMST.
12-1
50
10.7
12-1
10-1
10-11
23-1
10"1
10-
12-
10-
9-9.00
$-9.1
13.1
R=15,00-5
1am
P=10
12-4
12144
10
14-1
10:7
13-4
10:4
10-4
Figure 7: We consider binary MNIST, I= 2, 3 0.001, = 0.001, and measure the differences L()) L(1) (solid lines) and Lx (x) (t) (dashed lines). Here L(t) = 2m | Y ( is the loss at time t, while
XT || the "projocted' loss at time While L(t) should clearly decrcase for gradient descent with small enough steps, it not priori clear that Lx also docs. As we see from the plots, it does for 3 large and small, and for up 1, which corresponds to conventional ReLU activations. These results validate our Assumption 5.1 Note that we added small quantity 10- in order to make zero visible.
(t( 2m ( for (o (8))
The bound improves and converges 3 vanishes (Figure !
Assumption
5.1 holds empirically (Figure
The bound improves we enforce p = 1; this also results in faster convergence (Figure 3
The bound slightly improves for the half floating point precision (Figure
For e 0.01 the training time, all components our bound are of the same order, while for larger e, the last one starts dominate (Figure
The bound deteriorates consideraly when we increase depth (Figure 0
7 Proof of the main result
7.1 Proof of Theorem 5.2 for =
We start with approximating our learned network fü. with fgo: ie. with a nonlinear network that uses the weights learned by the linear one. This approximation deviates from the original network the following way: Vo Rd,e [0, 1].
1 [1z (2)(1)
1
0fg- (x) θr
Ōfg- (x) Or
Owm Or
dr
<
sup rE[0.e]
sup TE(O.e]
WZ
|||>]|||
(20)
1=1
since we use Leaky ReLUs. We omitted the argument for brevity. We get similar deviation bound on the training datasot:
OWTX X
SWT Ør
[X) -f0 {8)1
sup rE(0.e]
II [[]
sup re(0.e]
IT
II
[WII- (21)
Ør
1=2
We complete the above deviation bound with bounding weight norms and norms of weight derivatives:
Lemma 7.1. Under A Assumplion
VT [0, 2 0 (IWT S pu(l),
aw, X
(1)
S v(1),
ym
8r
F
and VI E [L] [[WT()) < w((),
(1)
< v(() for v defined in Theorem 5.2
12

---

Published in Transactions on Machine Learning Research (12/2024)
See Section 7.3 and Appendix D.1 for the proof.
Now we can relate the risk of the original model with the risk of the approximation. Since S Sr, and (. v) is 1/y-Lipschizz for any fixed y:
R(fb.) (F - (f (f6-)
< (70) Re (Soo) + B 7 - + |1 (X)
- 7m
Soo (X)I1
(22)
where the expectation is over the data distribution D, and ā = 1/2p is the actual input of the network.
As for the last lerm, the deviation on the train dataset, we use that ||=||| < /mlla1 for any 2 E R", and
Equation (1]. As for the deviation on the test dataset, due to Equation (20) and Lemma in order == [xx 1, we get
bound the last term, it suffices to bound E | Since E
E 1/22121 = E [x E x]
E tr ÆT " tr|[al = d.
(23)
This gives E B|E--//2/|1 < /R S Vd.
The first two terms is a generalization gap of the proxy-model. We use simple counting- based bound:
Ry (Fo()) -ne (fio(s) - In
Ind
(24)
2m
w.p. 2 1 - over sampling the dataset (X,Y), where (t; 0(0)) denotes the set of functions representable with (g)()) for a given initial weights A(0), where (1) a result of running the gradient flow Equation (4) for time f. As long as we work with finite precision, this class finite:
Lemma 7.2. VO(0), e 2 0, (t; ((0)) < 2nd
Proof- Since we run our gradient flow Equation 4 on whitened data to optimize squared loss, the initial weights are fixed, and the network we train is linear, the resulting weights depend only on YXT which has d parameters. Since cach function in our class is completely defined with the resulting weights, and each weight occupies bits, we get the above class size.
We could have used a classical se-dimension-baseed bound instead (Vapnik & Chervonenkis, 1971 However, we found it to be numerically larger compared to the counting-bast -based bound above.
This finalizes the proof of Theorem 5.2 for = 1.
7.2 Proof of Theorem 5.2 for
What changes for proxy-model. Consider the following:
f (x) = (x) + (fo- (X) fōo (x)) Xtx.
(25)
That is, we take the same proxy-model as before, but we add linear correction term This correction term aims to fit the proxy model to the original one, fg., on the training dataset X. We prove the following lemma in Appendix C.1
Lemma 7.3. Under the premise of Lemma 7.1 Vt
0 Ve E [0, 1] Vr Rdd we have
[ (x)) Tio (i)0))))0))(()))
< (L - () + 1 + pLL (0))0
(26)
|| (8)) - 100(0, < 2 1)(1 + p(L (0)(0=mm
(27)
13

---

Published in Transactions on Machine Learning Research (12/2024)
The deviation now scales e² instead of
What remains is to bound the size of (2(t; which denotes the set of functions representable with our new proxy-model (1)))) for given initial weights 0(0). Since (o) is a sum of (() and a linear model, its size is most 2nd times larger:
(1; 0(0)) S (1; ((0) S 2
(28)
This finalizes the proof of Theorem 5.2 for 2.
7.3 Proof of Lemma 7.1
Below, we are going present the proof only for 2, and defer the case of to Appendix D.1
7.3.1 Weight norms
Let us expand the weight evolution Equation
4
dWT
dWz dt
D
o
W
ET
XT,
= = D o w7x]"
(29)
dt
where we define
( W D o WI
(30)
and D = (6EY (WTX) a x m matrix with entries equal to 1 or 1 - T. We express it as D (1-7)lnxm + TA, where A is x m 0-1 matrix.
Lot us bound the evolution of weight norms:
d dITTI
dWi
(1-7) + A W E |
(1
(31)
dt
dt
Since multiplying by 0-1 matrix clementwise does not increase Frobenius norm, we get
TE < A W [ ||
(32)
Noting that E and E² X are row matrices, this results in
dl < ((1-)) + + - |[
(33)
By similar reasoning.
d W ||
(1 (1-7) X ||]]
(34)
dt
Consider the following system ODEs:
dg1 (t)
dg2(t)
(t),
(t), (0 = 3spi 92(0) = 3.
(35)
dt
dt
We then make use of the following lemuna which prove in Appendix C.2
Lemma 7.4. ||,|| = || & J (1 + pB²). If we additionally take Assumption 5.1 then |,
| < 8 + p
This lemma implics gx(t) 2 (1 - (s + p WT (+) + 7(1 + ()) and g2(() 2 [W] (t)l
The above system ODEs could be solved analytically:
)
81
92(1) = V 32 sinh zt tanh-1 -1
81
(1) = 3 / - 5 cosh øt + tanh-
(36)
3,
5,
14

---

Published in Transactions on Machine Learning Research (12/2024)
where 3 3= B This gives the bound for the input layer weight norms:
[WT SB+ S. ge(t) dt 3 3-
3 v 32 B cosh
+ tanh
(37)
For further analysis, we will need simpler-looking bounds. Consider looser bound: g2(() S u(l) and g1( & su(t), where
du(t)
su((), u(0) c
(38)
di
This ODE solves as u(t) Be
So, we have | (f)l S u(t). As for the input layer weights, we get
|W7 5 SB+ S u(t) u(t) dt = 3 - u(()
(39)
Similarly, - 7m [WT 3 B u(l). u()()).
As we do not want additive terms, bound from above:
[t]( S u(t) and 3_ (T pu(t).
7.3.2 Norms of weight derivatives
In Appendix C.3, follow the same logic demonstrate that bounded by the same which satisfies
dWi
dWi dr
X
and
dwa dr
are all
7m
de
v [(1 (11+ p)u? + s] + [1 + pu²], v(0) 0.
(40)
di
It is linear ODE in v(), and u(l) is given: u(l) = ae We solve it in Appendix C.4 to get v(l) from Theorem 5.2
8 Conclusion
We have derived a novel generalization bound for LekyReLU networks. Our bound could evaluated before the actual training and does not depend on network width. Our bound becomes non-vacuous for partially-trained nets with activation functions close to being linear.
Broader Impact Statement
This is theoretical work studying generalization in neural nets; its main result is form of a generalization guarantee. Having good generalization guarantee is necessary to make the models we use in practice more reliable. We do not foresee any negative societal or ethical impact our research could polentially cause.
References
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis optimization and genoralization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322 332, 2019.
Peter Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normalliie margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240 6249, 2017.
Felix Biggs and Benjamin Guedj. Non-vacuon generalisation bounds for shallow neural networks. In International Conference on Machine Learning, pp. 1963 1963-1981. PMLR, 2022.
15

---

Published in Transactions on Machine Learning Research (12/2024)
Blake Bordelon, Alexander Atanasov, and Cengiz Pehlevan. A dynamical model of neural scaling laws. In Forty-first International Conference on Machine Learning, 2024a. URL httpps://openrevier nwt.:/rummm
1d=nb0Y10mtRc
Blake Bordclon, Alexander Atanasov, and Cengiz Pehlevan. How feature learning can improve neural scaling laws. Xiv preprint urXie:2409.1153 2024b.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in neural information processing systems, 32, 2019.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochas- tic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703. 11008, 2017.
Tomer Galanti, Liane Galanti, and Ido Ben-Shaul. Comparative generalization bounds for deep neural networks. Transactions on Machine Learning Research, 2023.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural informalion processing systems, pp. 8571 8580, 2018.
Arthur Jacot, François Ged, Franck Gabriel, Berfin Şimşek, and Clément Hongler. Deep linear networks dynam- ies: Low-rank biases induced by initialization scale and 12 regularization. arXiv preprint ar ar 15933, 2021.
Tanishq Kumar, Blake Bordclon, Samuel J. Gershman, and Cengiz Pehlevan. Grokking as the transition from lazy to rich training dynamics. In The Twelfth International Conference on Learning Representalions, 2024. URL httppp///ppaaeerreee..ee/rrrrrrp wtt.:/oooorrriiieee/ssm
Mufan Li, Mihai Nica, and Dan Roy. The neural covariance sde: Shaped infinite depth-and-width networks at initialization. Advances in Newral Information Processing Systems, 35:10795 10808, 2022.
Zhiyuan Li, Yuping Luo, and Kaifeng Lyu. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. In International Conference on Learning Represenlations, 2021. URL https://openrrviee/ wwwpaarreweeee.eeeeeeeeeeeeeeeee httt:/forumiiddee AHt.rummmi.dHAAASSSSSS5.H
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally- normalized margin bounds for neural networks. In International Conference on Learning Representations, 2018. URL httpa://openrevier http:///ppeenereeee.eeeeefrrrrrs WfbbZ
Lorenzo Noci, Chuning Li, Mufan Li, Bobby He, Thomas Hofmann, Chris J Maddison, and Dan Roy. The shaped transformer: Attention models in the infinite depth-and-width limit. Advances in Newral Information Processing Systems, 36, 2024.
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkii,, and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXio preprint arXin:2201.00 007777, 2022.
Andrew M Saxe, James L McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. ar preprint arXiv:1312.66 6120 2013.
Zhenfeng Tu, Santiago Aranguri, and Arthur Jacot. Mixed dynamics in linear networks: Unifying the lazy and active regimes. Advances in Newral Information Processing Systems, 2024.
V N Vapnik and A Ya Chervonenkis. O ravnomernoj skhodimosti chastot pojavlenija sobytiy k ih veroyalnos- tiam. Teorija verojatnostieej i jejo primenenija, 16(2):264-27) 279, 1971.
Ashish Vaswani, Noam Shazoer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
16

---

Published in Transactions on Machine Learning Research (12/2024)
Greg Yang and Etai Littwin. Tensor Programs IIb: Architectural universality of neural tangent kernel training dynamics. In International Conference on Machine Learning, pp. 11762-11772. PMT.R, 2021.
Chulhee Yun, Shankar Krishnan, and Hossein Mobahi. A unifying view on implicit bias in training linear neural networks. In International Conference on Learning Representations, 2021. URL https://openrevier (iwtoorrnmiddd--2------a
Chiyuan Zhang, Samy Bengio, Moritz Hardi, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107-115, 2021.
Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, and Peter Orbanz. Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach. In International Conference on Learning Representations, 2019. URL httppp///ppprrriiieoooofoooooooo
A Discussion
A.1 Assumptions
Whitened data. Overall, the assumption whitened data is not necessary for result similar to Theorem 5.2 to hold. We assume the data to be whitened for two reasons. First, it legitimates the choice of training time (3) since it is based on the analysis of Saxe et al. (2013), which assumed the data to be whitened. Tf we dropped it, we could st.ill evaluate the bound of Theorem 5.2 at t = (8), but it would be less clear whether the trainining risk R, becomes alrcady small by this time.
Second, we had to bound ||A||] throughout the proof of Theorem 5.2 and ||*+[] in the proof of Lemma 7.3 For whitened data, these are simply vm and 1/ym, which is clear dependence on m, making the final bound look cleaner. Otherwise, they would be random variables whose dependence m would be less obvious.
Third, if we considered training on the original dataset X) instead of the whitened one, (Y, we would have to know YXT and XXT in order to determine (t) for a given t and initialization (0). These two matrices have d + 1(d+1) parameters, compared to just d for X This way, Y, would grow d instead of Vd.
Gradient flow. We expect our technique to follow through smoothly for finite-step gradient descent. Introducing momentum also seems doable. However, generalizing to other training procedures, e.g. the ones which use normalized gradients, might pose problems since is not clear how to bound the norm of the elementwise ratio of two matrices reasonably.
Assumption 5.1 We use this assumption to prove the second part of Lemma 7.4 If we dropped it, the bound would be X le < || I p&4 instead of + p34. This would result in larger
exponents in the definition in Theorem 5.2
As an argument in favor of this assumption, we demonstrate empirically first (Figure 7 and we prove it for the linear case after, see Appendix
A.2 Proof
We expect the bounds weight norms u(t) to be quite loose since use Lemma 7.4 to bound the loss. This lemma bounds the loss with its value at the initialization, while the loss should necessarily decrease. If we could account for the loss decrease, the resulting u(t) would increase with a lower exponent, or even stay bounded, as u(t), which corresponds to a linear model, does. This way, we would not have to assume to vanish as B vanishes in order to keep the bound non-diverging for small B at the training time (5). Also, the general bound of Theorem 5.2 would diverge with training time much slower. We leave it for future work.
17

---

Published in Transactions on Machine Learning Research (12/2024)
As see from our estimates, xx becomes the main bottleneck of our bound for small The bound we used for Yx is very naive; we believe that better bounds are possible.
Indeed, since the proxy corresponding to k = depends only on 0,, the trained linear model weights which one could obtain explicitly, this proxy, fgg; is also given explicitly. One could try to estimate its generalization gap explicitly, as done for kernel methods (Bordelon et. al. 2024a) and for more complex models, which are closer realisic neural nets (Bordelon al. 2024b). We leave this direction for future work.
A.3 Other architectures
As becomes apparent from the proof in Appendix C.1 the proxy-model for K 2, Equation (25 deviates from the original model fg. as O(e²) for any map (c,0,z) - fā (2) long the following holds:
1. (z)) is linear in a for any 0:
2. a (()) is continuous as function of (e, (e,),)); 0:80
3. the result of learning (t) is differentiable ble in for any t.
This is directly applicable to convolutional networks with no other nonlinearities except for ReLU's; in partiular, without max-pooling layers. One may introduce max-poolings by interpolating between average- poolings (which are linear) for = and max-poolings for e = This is not applicable to Transformers (Vaswani al. 2017) since attention layers are inherently nonlinear: queries and keys have to be multiplied.
Compared to the fully-connected case of the present work, bound might become even tighter for convolutional nets since d becomes the number of color channels (up to 3) instead of the whole image size in pixels. However, the corresponding proxy-models might be over-simplistic: the linear net they will deviate from is just global average-pooling followed by a linear Rd - R map. We leave exploring the convolutional net case for future work.
B How far could we get with our approach?
Recall our general prsxy-based generalization bound of Equation
11 1 m
RJS < Ru, + (nG feG(ol) + + BZ-D)((()) g(x)) + 7 m Σ (((m)))
(41)
Informally, we say that performance of worse than that of g at most by some deviation term.
The bound ends up to be good whenever (a) the generalization gap of g could be well-bounded, and (b) g does not deviate from much. That is why considered proxy-models based on linear learned weights: their generalization gap could be casily bounded analytically and they do not deviate much from corresponding leaky ReLU nets as long as ReLU negative slopes are close to one.
The biggest conceptual disadvantage of this approach is that, given both f and g learn the training dataset, we have no chance proving that f performs better than g, we could only prove that f performs not much worse than g. Do the proxy-models we use in the present paper perform well, and how much do they deviate from original models? Our main theoretical result, Theorem 5.2 bounds the proxy-model generalization gap and the deviation from above. These bounds arguably not optimal. It is therefore instructive to examine how well the bound would perform if we could estimate Equation exactly.
B.1 Empirical validation
Setup. We work under the same setup as in Section but instead of evaluating the bound of Theorem 5.2 we actually train linear model with exactly the same procedure as for the original model, in order to get
We also downsample MNIST images 14x14 instead of 7x7. The reason why we do is that on hand, we wanted to our bounds more realistic scenarios, while on the other, X does not appear be full-rank for the original 28x28 MNIST.
18

---

Published in Transactions on Machine Learning Research (12/2024)
14x14 0.1.p
J6x14 MMIS f IUDUI, U.I.
124
10
20TM
22-
12-4
10
10
10'1
107
127
10'
10
10
10'
10
14x24 MNIST, $ 2.001, C.L.
14x14 MNIST: 2 5.001, C.L. < 32
R teath
model tran
0.6
moddel train
02
10
training Emm.
trainig tmm.
Figure 8: We examine the optimistic bound of Equation for the proxy-models proposed in our paper: the x 1 one, foo, the one of Equation 25 and also linear proxy, fq. The bottom row demonstrates the full bound (green lines), while the top depicts the two com components of the bound, namely, the proxy model generalization gap R& (g) RC and the proxy model deviation E ff(x) 9(x)) + É [f(x) g(x)), separately. Different lines of the same color (e.g. solid green and dashed black lines on the bottom row) correspond to different values of 7. Proxy generalization gap stays low during the whole training (lop left figure), while the train risk and the model deviation over gamma contribute significantly (bottom row, two groups lines correspond to the minimal and the maximal y we considered). The optimistic bound for the Ist-order proxy (bottom left) gets non-vacuous only the moment when GF escapes the origin and reaches the linear model loss. The bound for the 2nd-order proxy (bottom right) becomes non-vacuous soon after the original model becomes non-vacuous (but still stays near the origin), and stays non-vacuous until the model starts exploiting its nonlinearity to reduce the loss below the optimal linear model loss level (the last drop of purple and black lines).
16x24
6.4.
3.0
3.0
rOk accorac
0.6
0.6
10a
10'
10
10
10a
10a
107
10'
training Emp,
trainin tme.
Figure 9: The optimistic bound of Equation 41 based on our K = 2 proxy stays non-vacuous up to = 0.4 until the gradient flow starts "exploiting" the nonlincarity (the last drop of purple and black lines).
19

---

Published in Transactions on Machine Learning Research (12/2024)
trained linear weights 8 We then evaluate the proxy-models considered in the present work: (1) the one for = 1, fūo, (2) the one for 2, see Equation (25). and also (3) the linear network, fg.. We then evaluate the rhs of Equation (41) using a test part of the MNIST dataset. For this 'optimistic" bound, we consider much larger values of epsilon: 2 0.1, i.c. our model much less 'ncarly-lincar' now than before.
Figures. We present the results on Figures and Dashed lines correspond to the train set, while solid ones correspond to the test set. Black lines risks of the actual trained model Sorte) R(t) and (t), respectively. Green lines are our 'optimistic' bound Equation lines denote MSE loss of the actual trained model.
41 evaluated at different values of 7, Purple
We also put three baselines on the plots. The dotted black line is the classification risk (and the MSE loss) of zero model f = O. The brown dashed line is the MSE (train) loss of the optimal linear model, f f:a: > +X+x. z. Finally, the red dashed line is the (train) classification risk of the optimal lincar model.
Training phases. As we observe on risk plots (Figure 9 and the bottom row of Figure 8), the training process could be divided into three phases. During the first phase, the risk decreasos until reaches the risk of the optimal linear model, while the loss stays the level of f f 0. This indicates that while the weights stay very close to the origin, the network outputs already align with the outputs of the optimal linear model. During the second phase, both the loss and the risk stay at the level of the optimal linear model. As for the following phase, both the risk and the loss drop below the optimal linear model level. Therefore from this point on, the network starts to "exploit' its nonlinearity in order to reduce the train loss.
Obscrvations:
The generalization gap stays negligible for all models and y's considered (Figure top left);
The proxy-model for к = 2 approximates the original model best among all three proxies considered (Figure g top right):
While the lincar approximation deviates from the original model more than the one for x = 2 during the first phase, their deviations are similar during the subsequent phases;
At the same time, the 1 approximation deviates more than that of k during the second phase;
The transition between the first and the second phases results in a nonmonotonic behavior of the deviation from the original model for
and lincar proxy-models;
The resulting optimistic bound for 2 (green lines of Figure g during the first two phases for c = 0.1, while this is not the case for (green lines of Figure bottom left);
bottom right) stays non vacuous
The optimistic bound for k = 2 stays non-vacuous up to = 0.4 (green lines of Figure
It is tempting to assume that the weights 0s follow the same trajectory the weights of the linear model, 0", during the first two phases. However, if it the case, the = mooey-model, fāa, would coincide with the original one, f during this period. Then their quality would be the same; however, Figure X top right, demonstrates the opposite.
C Missing calculations in Section
C.1 Proof of Lemma 73
We have:
1
(z) = 1 1./0
0ff (X)X+x x
Off
Ofz
0fg (8) Gr
2 [T) Je
dr < sup
x+
x
dr
Ør
rE[0,c]
(22)
20

---

Published in Transactions on Machine Learning Research (12/2024)
Since fg- is a linear network and rk X d, we have f8- (a) = for (X)) x and implics
(ffr(x) (x)
0fa- (X)x
This
8r
Ör
1
05
(x)
(X)
8 S (1)
8 8 (X)X+x
x 2
dp
c
Opår
Opôr
8 88 (x)
886- (x))
s sup (
x
(43)
Opår
Opôr
J& (1)) Opor
02 fg. (X)
sup pE(U.c]
+ sup pEt0,e]
Opor
|| x/|-
Since we use LeakyReLU,
02 fg- (x) Opor
aWT
< (L - 1) Σ
|
(44)
8 fz- (X)
< <(L - 1)
|
WW1 X θT
II kE[2.
I + (L- (L-1))
OW? ŌT
II
IWIII-
(45)
Opor
kE|Z.LIV(U)
Finally, since XXT mId, we have ||*||=
Combining everything together, we arrive into
vm
Jā. (x)) -50,00(0 (w))
OW? θT
< sup rE(0.c]
W II
(L - 1)12
ow? Ør
sup E
I[T
|
(46)
mm
kE(2.0]M()
1
aWT X
II |
sup rE(0.c]
kE(22
Plugging the bounds from Lemma 7.1 then gives
f (x) - fo 0- (z)] s (L- 1 (L 1)0)/t~-u1lz11
(47)
By a similar reasoning.
[ (X) - Júm ge (8) (L 1)c2
OW?
2 2 sup rE(o,]
| X ||
II
I
(48)
@WT X 0r
sup rE(0.c]
|
Plugging the same bounds,
(X) Po (X)]l < 222 1)(1 [1 (L 22
(49)
C.2 Proof of Lemma 7.4
Recall the definition of E7:
(t) = (Y (t(()) (t) (T-1(0) [...W. (T(()
x
(50)
21

---

Published in Transactions on Machine Learning Research (12/2024)
Since 1| is the loss function we optimize, it does not increase under gradient flow. Hence, since multiplying by Dj elementwise does not increase Frobenius norm,
mll=" & (l)l S || [[]
II W (0)I.-
(51)
1=2
We have (0) ||T WT (O)II| Since all y from supp D are +1 and XXT mld, we - p33)
get | (4)l
Due to Assumption
ml = X 5.1
| does not increase under gradient flow:
m| ml | ml = || V 1 + | IIT( (0)I
(52)
1=2
Since YX+ = s, we have YXT ms. Therefore (t) T |F = + ps
Finally, since E" E R ||||| = | and
| E X pr
C.3 Bounding derivatives in the proof of Lemma 7.1
Let us start with WT:
de deWT dtdr
o
(d?? dr
E' W WT..TEE dE
]]
xT-
XT XT-
A
WT. E XT;
(53)
dr
d'
dW2
(1
dtdr
dr
((1-)) X + [EE]]
dr
||
(54)
We need a bound for
d="
dr
dET
dWT
dW1
W
A
1 W
W
D
X
[D
WTX]:
(55)
dr
dr
dr
dE dr
dWT X
dW7
m
< W W7 X F + ||
+
|
dr
dr
1r
(56)
dWi X
dW/
< u² Ppmm=
m - u
+ upym
dr
dr
F
This results in d
dWT <
dWT dtdr
< u (1+ p3² + pu² +u
1
ddW
x x||
x||)
1)+ +
|W3
(s (1 ((1-srr-0 + p.8 + pui))
dt dr
vm
dr
dr
(57)
Similarly, we have an evolution of WTX:
dWT dt dt
dWz
(1=-_)
X
<
((1-)) X
|| ||==
+ +|
+ ||
+ +1E5)l
|| 1x X11
dr
dr F
I u 1 - p + pru
+ -
dWI X
)
Vm
dW3
(s + (1 3)7 + p + pr) v
dt F
dr
(58)
Finally, consider Wi::
dWI d D 0 W
dWI,
x dOW7X| :
+
D
(59)
dtdr dr
dr
22

---

Published in Transactions on Machine Learning Research (12/2024)
de dW
dWI dr
d= |
))
<
((1
(11>))
I X ||ms
(60)
dtdr
dr
d
dWi
dt
dr
dtdr
(61)
1
dWT
Fr ) +
dWi dr
dW2 dr
S
1 - pB² + pri
+ u
x
(s + (1 - s)r + p3²) + pu?
vm
dr
We see that
dWi
dWI
x]
and
awI di
are all bounded by the same v which satisfies
dr
m
dr
pr
dv(t)
(5 (1 + p)) + u(t)(I (t(()))
c(0) 0,
(62)
dt
where 5 5= 8
(1 (1- 8)T + p3 and I + p3².
C.4 Solving the ODE for vtt)
Recall u(l) = Be We solve the homogeneous equation to gel
(t) = C( 2 C(t)e(4-1)inutt)) +u 1e nn ((1))--'u())) # (0))
(63)
where C(t) satisfics
dC(()
dt u(t)e 20 420) =Bu(l) [1 (1]]
(64)
Recall for I 2, 8
2 5. Then 1+p
C(I) = 3 /
pu? (1)] dl
e
(65)
(²(1)
82
12
Ei
- p
c
2
8
This gives the final solution:
2310
(t)) (w())(((u())) w(B)le
(66)
where we took
i Ei n²(()
2p
w(u)
(67)
p
D Deep networks
D.1 Proof of Lemma 7.1 for L 3
Bounding weight norms. For I E [2,
dWT
Dj 2 WTl
Di_, o ow [ [P_ WT,.... [D] o WT WTX T
(68)
dt
dWT dt
< I| + -
II IIZII-
(69)
kE(2.A]M1)
For 1 -=1 1,
dWr
DJ o W.
o xT:
(70)
dt
23

---

Published in Transactions on Machine Learning Research (12/2024)
dW7
((1 X
II [W
(71)
dl
kE|2.4]
dWp X
$ ((1- X
|| || + -
I
(72)
dt
kE
Using Lemma 7.4 where
we get (1 11-7) (1-r)|[E"> X [1- - 9n (t) and | || S g2(() 4A [2 L.,
dgi(t)
dg2(t)
52 1- (t),
91 (t)g2 (t),
91 = 0(10==0((1-1100-00)~----1111-11- (2(0) = 3.
dt
dt
(73)
We have the following first integral:
d
(oi(t) ( 3²g)(t))
0, g:(0) ((0)) B (((1-) 3²) + T(L 1) pp) 8²). (74)
dt
Therefore
92 (t) 1. (t)/
+ (f), 92(00) 3. g2 (
(75)
dt
Suppose p > 1. Then (f(00) - 5² (0) > 0 and the solution is given in the following implicit form:
(1)2f 22 t
3-4 5-h g92(0
B2
B
5-
3282
2' 2 2 97
52
2 2
2
--0
(76)
(3- (0)
52
The above expression cannot be made explicit for general I (but. could get explicit expression for L E (2)3,4)). As an alternative, consider looser bound u(t):
du(l) = Fy 2 (1),
(0)) = B 80
(77)
dt
51
where 3p = (1 (1- -1--) (s + 3h) + T(L - 1)(1 + 3²) note that 31 = 3. We have u(t) 2 (a()) and su(t) 2 91 (t)
1L 2 0. This ODE solves as
utt (s(2 L)t + 32-2)=+
(78)
where B = S Note that the solution exists only for t < (1-22)
72-1.
For the input layer weights, we get
d (t)l dl < su (1).
(79)
The solution given by
[WT (B+t) S/" (5(2 (5(2- L)t 30-L) + dt = B 3 (5 L)t 32-1 3-
3 +u()).
(80)
Similarly, we have
|I & 8p ( (5(2 L)t (5 32 3
dt = 3p 3 + u(t).
(81)
For brevity, we define
B 1)(p 1) + gt
b= 3 - 3 =3 31-
8p = (1))
(82)
and
b,= = 3p - 3 = 3 (p-
8 = 3(1 - 3(1-))(p - 1) 3
BL
(83)
81
As simpler option, we could just say [[ (t)]l < u(t) and J.t (1) S pol(t.
24

---

Published in Transactions on Machine Learning Research (12/2024)
Bounding norms of weight derivatives. Recall the definition of E":
1
=== m
(Y
W7. P 2 WT-1..... [D] o wwxx]):
(84)
d= dr
dWT X
dW
$ (T.
WW71l +
[T || - | X11
II
dr
dr
1=2
l=2
(E(2.L])(R)
ddTT
S Lub-l
(L 1-1//mmu +
+
pm
dr
dr
(85)
For 1 E [],
ddW7 dtdr
+ - -))-)))) ||T F
IWTI
dr F
Σ ((1-)) + + 1) E (ITTX() IF)
II
IWZ
dr
,E(2-1]111}
(E(2
dWI
XWTx X dr
(1
(1-
+ 1 (\
II
IW
(86)
dr
kE(2
dw7
L
dW dr
< 1-1
- (L-1) + vm
+
k
+ I(L - 1) pu
dr
k=
dWT
dwT X dr
suL 2-2
+ (1-
34)
-IIIL- 1) mm
1/) 26-2
dr
dr
jEP-L]M(1
For 1=1, 1,
dWW dldl
+
(1-1)]|E11 |FF) || II |
dr
F
kE[2,]]
L
JW3
((1-t)| = x
+ TL 1)] ||+*||)
II I
dr
j=2
kE
< 4-11
(L (L- 1)pu +
1
dwTX
+p>
L
dwE
+ I(L I(L--1) 1) w + su -2
Σ
dW,
vm
dr
dr
dr
k=2
j=2
(87)
dWT dr
vI E [L), as well as
dW7 X
F² are all bounded by e(t) which satisfies
vmm
dr
dr
[L 1) + (1
(L-1)p)u -11 + (L- 1)]] - + 5(L 11)-1 2-2
dl
(88)
= [11 + (I - 1)p) 3(L - 1)ut + (L - 1)u [1 + putt.
v(0)= = 0.
where T= + BL
Solving the ODE for v(t). Recall
u(t) (s(2 L)t + 32
(89)
We solve the homogencous equation to get
v() = C( In L)1+ 32 |+ (3(2 (3(2-L))+-2-1))
(90)
= C(0))(--))aa0)) ملمم af (1) = C(t)u - (t)e _ (()
25

---

Published in Transactions on Machine Learning Research (12/2024)
where (t) satisfies
dC(t) u (t)e 1 =LL (t) [I pu (t).
(91)
Let us introduce 8 1)( Then
C(t) = (L 1) / -==
=5(0
[] + pu (t)] dt
L --1 - r
,
2 L
84
2 (2-
L
+P -
r
(r(
2 34
( 2 u
ut(t)
(t)
))
-
- r
L
3
L 8
L
L
3
(92)
This gives the final solution:
L L- g² 1 - - w(3)]e -
u(t)
(93)
where we took
w(u) = - 1 2 (2- u² )
Lp
2 u²
r
(94)
I+ (L 1)p
L'
D.2 Evaluating the solution at the learning time
For a properly initialized lincar network, E [L] [[))()) = a(t), where u(t) satisfies (Saxe et al. 2013
dū(()
π - (1)s
m(0) = B,
(95)
dt
which gives the solution in implicit form
(B) / 1 u4)
du
(t)
2
2 a (t)
32-L
(
2 3h
s(2 s22 L)
2F
1,
-
L
s(2 - L) 2F1
[1 - 1,
L' (96)
Suppose we are going to learn a fixed fraction of the data, i.c. take ū(() = (as) /T. for a E (0, 1). Then
B2 L 2 1 - 1, 2. gz - (as) 2F (1, - 1, a:
I
(3)
(97)
s(T. 2)
Since t (B) is the time sufficient to learn a network for e = 0, we suppose it also suffices to learn a nonlinear network. So, we are going evaluate our bound at t= f Since we need (t,t)) < 1 for the bound to be non-vacuous, we should take 7 small relative to a. We consider 7= a² /q for v, 1.
Since the linear network learning time (B) is correct for almost all initialization only when & vanishes, we are going to work in the limit of B + 0. Since we need a E (3t/s, 1), otherwise the lincar training time is negative, we lake a = = for À E (0, L] and > 1.
Consider first A < L:
B2-L s(L - 2)
(b)
+ OBBAAT))
(98)
Let us evaluate at this time:
2-1
22-1
(()) 8 _ +0(3)//1))
g2-
=
(99)
2-1
2 is hypergeometric function defined as series
(a,
1+ D
(a) ck (c)x क..
where (9), = g(9+1) (9+k-1).
km
26

---

Published in Transactions on Machine Learning Research (12/2024)
Apparently, this expression does not make sense for p and even close to it, switch to À L, which we expect to be the right exponent:
(3) = 82-L - -
+ 0(8))
(100)
s(L. - 2]
Let us evaluate at this time:
(3) = 82 (1 (1-r2-1) 12- -0(33)+00((3))
ztz
= 3
1 I.
(1-r2-1)
(1+0(8*))
8 2-L
(101)
12 7- - _/2 (1 (1- (1-rž-1) > 0, ie. when r is close enough to 1.
This expression makes sense whenever
Let us evaluate at the training time now. Since ((,, = [(a)= - =-- + +(a++t), we get
L
w(u(tt - w(8)
[u 2 (3)) - B2-L) + 0(33).
32 -
(102)
L
8
1-2
B2
2--h
3 (1- (1-r -1) + +0(8))
82 T.
81
Then the quantity of interest becomes
Lu (ta (3)) (B))
L
2L
2L- (1)
L
32-L
pp
2-L
8
1 (1-r -1] -1 (1 (1+0(84))
"
7
32 I
31
2-T
26-2
98" I L(L -1 1) pd
31(1-u)
2-
3
-1- 1 )
2-
g
(1 -1)=-))-11--0000
5 2- T
5
2-
5
2-L
(103)
This expression does not diverge as + 0 when 1. We will also have a finite lim,,+o0 lim whenever 1)-1
x
E Proving Assumption 5.1 for linear nets
We have for 1 - 1,
1 1 Y
fz. (x)
V
Diows
[Di-1 o w XT.
(104)
2m
OW
For I E [2, L.],
1 0 Y
fg. (x))l
Dj Wow...... ... o
o on T=|== [D o [ wi.... [Di o [Poo";"]]".
2m
OWf
(105)
We also have
a aal(Y fo. (X)) TT 1|
1
D ... [_[____- Of x XT.
(106)
2m
aW:
a ll - Ig (8)) XT 1
V
2m
OW
(107)
Dj WaT ... O T x [D__ o wf.... [Diow;x]]]
The statement of Assumption 5.1 follows from
27

---

Published in Transactions on Machine Learning Research (12/2024)
Conjecture E.1. Ve [0, V E tr V 2 0.
Indeed, the above conjecture states that loss gradients wrt weights and 'projected' loss gradients wrt weights are positively aligned, so, whenever loss does not increase, neither does projected loss. Since gradient flow, loss is guaranteed to not increase. Below, we prove the conjecture for lincar nets.
Proof of Conjecture E.1 for = 0. Since is zero, we omit the corresponding sup-index:
tr [
= tr [W2 WI X X X [W2 .e...... w
tr [W.] .......WXX W w[=xT]'] tr [W W.W. WT tr [X X=
(108)
by the circular property of trace, and the fact that is a matrix with a single row. Since dow = 1, both traces are just squared Euclidean norms of vectors, hence they are non-negative: ir [V]V]]] 2 Let us do the same for the other layers:
tr V [ tr [WT.. WTEX X [W-11... W1X] [Wi-1... WiX [ ... W
tr [W [WI WT. WiLi] [W [411-- ...... W/ WT ... W.TT] ']
(109)
tr [Wz... W... WTr W ur [=XTW] ... WT_, Wi- W..W-....WW.E" wix= 20
for the same reasons as before.
Clearly, Conjecture E.1 should also hold for small enough whenever it holds for However, the bound for the maximal for which we were able guarantee the conjecture statement, vanishes with time as our weight bounds are too loose. For this reason, we do not include it here. See Section 0 for empirical validation of Assumption 5.1
28


Reviews:
[{"review_id": "O8HnRv7Dk0", "reviewer": "Reviewer_tWuH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength. The generalization bounds derived in the paper are not seen in existing literature.\n\nWeakness. The last term in Theorem 4.2 exhibit several aspects of weakness.\n- The bound grows exponentially with number of layers. Note that using standard tools of Rademacher complexities and norm-based bounds, we can already derive an exponentially-growing bound. But the norm-based bound does not suffer from other weakness and does not require early stopping.\n- The bound grows exponentially with time (for 2 layers) and blows up within finite time (for more than 3 layers). This requires the training time to be very short. Within such as short training time, the neural network can still be far from convergence to a local minimum.\n- This term does not decrease with sample size.\nMoreover, the paper establishes the generalization bound based on approximating a non-linear NN with a linear NN. This approach does not seem to be able to yield good bounds. In particular, if there is a regime where the bounds derived in this paper are small, that means the nonlinear NN is well-approximated by a linear model, and the approximation error appears in the final excess risk bound. In such a case, why don't we simply use a linear model? (The linear model may approximate the true model worse than NN, but here we are paying for approximation error anyway).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies generalization error for multi-layer fully-connected neural networks by studying its approximation by linear neural networks. Upper bounds are derived for the gap between training and test error, for multi-layer neural networks trained by gradient flowm, within a fixed total training time. The bound contains two terms, corresponding to the generalization of a linear neural network, and the approximation error between NNs with linear and nonlinear activation functions.\n\nThe generalization error of neural networks is a central question in machine learning theory. However, the results derived in the paper are relatively weak. In particular, the last term in the generalization bounds in Theorem 4.2 grow very quickly as the training epoch and model size increases, effectively making it vacuous. With a reasonably long training time for the neural networks, it is not clear why the proposed bounds could be better than usual bounds derived using VC dimensions and Rademacher complexities. Moreover, the method of linear approximation for proving generalization bounds is fundamentally limited (see weakness below). Therefore, I don't think this paper could be publishable at TMLR.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "More comparison with existing literature might help. Also, the authors need to explain why we don't use a linear model directly since they bound the difference between NN and a linear model.", "broader_impact_concerns": "No ethical concerns are involved.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "S51hwmK6qJ", "reviewer": "Reviewer_5zEF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Some advantages we can observe:\n1. The bound does not depend on a held-out dataset, which is a novelty among existing generalization bounds.\n2. It does not scale with network width, unlike some other bounds that exhibit such growth.\n3. It focuses on the generalization gap of the original trained model rather than relying on proxies or external alterations to the model weights.\n\nSome limitations:\n1. The bound becomes useful only under specific conditions, such as when the functions are close to linear, and when a simple linear model's generalization bound is non-vacuous in similar settings.\n2. The application might be limited as these conditions are not always met, such as for binary classification tasks on high-dimensional data like MNIST without modification.\n\nThe paper clearly outlines that certain assumptions, such as whitening of data, make the theoretical analysis cleaner and simpler. However, it acknowledges that this assumption might not always hold in practical scenarios.\n\nThe authors compare their approach to existing literature, highlighting how their improvements offer practical benefits like eliminating the need for a trained model to compute bounds and not being affected by network width. In some degree, NTK can be also viewed as a type of linear neural network (or linear surrogate of neural network). Have you compared your results with NTK?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors aim to present generalization bounds that become meaningful for networks that approximate linearity. This is particularly valuable as it does not require the actual training of the model to evaluate these bounds, making them a priori—an approach not previously used for neural networks to this extent.\n\nThe paper emphasizes the difficulty in understanding why neural networks generalize well on unseen data despite their massive capacity and complex training dynamics. It aims to address the shortcoming of classical methods that uniformly bound performance over model classes, which often prove inadequate for networks with poor parameter configurations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Comparisons with some key previous work are missing. \n\n1. Such as neural tangenet kernel, which is also a linear surrogate of neural networks for analysis purpose. \"Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31.\"\n\n2. Ridgeless regression can also interpret the generalization gap of over-parameterized networks (under certain assumption, this result could also extend to DNNs). Liang, Tengyuan, and Alexander Rakhlin. \"Just interpolate: Kernel “Ridgeless” regression can generalize.\" The Annals of Statistics 48, no. 3 (2020).\n\nCould you please compare your results against them.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OjA2VRSuWQ", "reviewer": "Reviewer_6Ktd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nAt its core, the paper proposes a simple and powerful idea of leveraging the similarity of non-linear networks to linear networks to show their generalization ability. The theory is not only strong and well-motivated, it's also intuitively appealing. Experiments are also adequately conducted to back up the theory. Optimistically, bounds using the core idea of this paper could potentially produce the next generation of empirically-relevant generalization bounds.\n\nBeyond technical aspects, the paper overall is generally well-written, with concepts presented at the appropriate depth. \n\nAlso, the authors are open about their bound's strengths and weaknesses, which is great to see.\n\n**Weaknesses**\n\nThe primary weakness in my view is that the practical significance of the work remains unclear. It seems fairly obvious that if a nonlinear network is sufficiently close to a linear network, then a generalization bound for a linear network can be applied to the nonlinear network with some added error constant. The key to whether this kind of bound can be significant is the size of the error constant. Unfortunately, it's unclear whether the error constant derived by the authors should be considered large or small for practical networks. The authors show that with leaky ReLU with a slope of 0.99, the bound can be non-vacuous, but I'm not sure whether this provides much insight into most neural networks (which have significantly more non-linear activations).\n\nAnother way to phrase this is as an empirical question: do general nonlinear networks generalize well because of their similarity to linear networks or due to some other factor? The results in this paper hint at the exciting possibility that the answer might be yes, but the results merely suggest this rather than demonstrating a step in this direction. One way the authors could actually show this is by doing the following: take a nearly linear network and show that several other modern generalization bounds provide vacuous results on the network while the authors' proposed method provides a non-vacuous bound. Another approach is to show that practical neural networks can be approximated with nearly linear networks under a similar number of parameters (perhaps a constant multiple of the original network's parameter count).\n\nAnother question that I think will be important to address: wide neural networks in the neural tangent kernel (NTK) regime can be viewed as linear models in the limit of infinite width. Correspondingly, we may derive generalization bounds for wide neural networks as a function of their width (with the generalization bound approaching that of the linear model in the infinite-width limit). In this work, instead of infinite width, the authors consider the limit of infinitesimal nonlinearity to produce an alternate generalization bound based on another linear network. Could the authors comment on 1) the difference in the generalization bounds of the linear models in the two cases (I think the same parameter counting bound can't be applied in the NTK case), 2) the difference between the linear and nonlinear bound in the two cases as a function of width and activation nonlinearity level respectively?\n\nOverall, while I'm not sure *how* significant this paper is yet, I'm inclined to believe that is more likely to be of interest to the community than not.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a new form of generalization bound for deep networks that are *nearly* linear. The generalization bound roughly proceeds as follows: the authors demonstrate that nearly linear networks behave similarly to linear networks, then apply known generalization results for linear networks. The authors empirically demonstrate that the bound can be non-vacuous on real-world tasks for sufficiently linear networks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Critical for acceptance**\n- Please make the font sizes in the figures larger; they are not legible at this size\n\n**Would strengthen**\n- Do practical neural networks generalize well because of their similarity to linear networks or due to some other factor (I understand that a complete answer is outside of the scope of the paper)?\n- Do other generalization bounds provide vacuous results on nearly linear networks?\n- All practical neural networks close to nearly linear networks of similar size?\n- Could the authors comment on the relationship between their work and NTK-type linear analysis (see above)?", "broader_impact_concerns": "No broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides an a-priori generalization bound for nearly-linear neural networks. The bound is shown to be non-vacuous under certain conditions, and is investigated empirically. Generally, the reviewers did not raise issue with the correctness or rigor of the results, but were divided about whether the approach and the findings were useful and interesting. The topic receiving the most discussion was the focus on near-linearity and the reliance on linear models, and whether this focus rendered the results uninteresting in the context of previously-established related bounds. The authors replied that this paper provides a first non-vacuous a-priori bound useful for neural networks, and that other prior bounds cannot exploit near-linearity. This rationale seems to solidify the current contribution as a useful and interesting one, and as such I recommend acceptance.
Decision: Accept (poster)