Generalization Bounds for Rank-sparse Neural Networks
Authors: Antoine Ledent
Rodrigo Alves
Yunwen Lei
Venue: NeurIPS 2025 poster ()
Keywords: Learning Theory
Generalization Bounds
Schatten Norms
Low-rank
Primary area: theory
TL;DR: We prove generalization bounds for neural networks which exploit approximate low-rank structure in the weights.

Abstract: It has been recently observed in much of the literature that neural networks exhibit a bottleneck rank property: for larger depths, the activation and weights of neural networks trained with gradient-based methods tend to be of approximately low rank. In fact, the rank of the activations of each layer converges to a fixed value referred to as the ``bottleneck rank", which is the minimum rank required to represent the training data. This perspective is in line with the observation that regularizing linear networks (without activations) with weight decay is equivalent to minimizing the Schatten $p$ quasi norm of the neural network. In this paper we investigate the implications of this phenomenon for generalization. More specifically, we prove generalization bounds for neural networks which exploit the approximate low rank structure of the weight matrices if present. The final results rely on the Schatten $p$ quasi norms of the weight matrices: for small p, the bounds exhibit a sample complexity $ \widetilde{O}(WrL^2)$ where $W$ and $L$ are the width and depth of the neural network respectively and where $r$ is the rank of the weight matrices. As $p$ increases, the bound behaves more like a norm-based bound instead. The proof techniques involve a careful interpolation between the parametric and norm based regimes. We also demonstrate in experiments that this bound outperforms both classic parameter counting and norm based bounds in the typical overparametrized regime.

Generalization Bounds for Rank-sparse Neural Networks
Antoine Ledent
School of Computing and Information Systems (SCIS) Singapore Management University (SMU)
aledent simeentsmu... edu.
Rodrigo Alves
Yunwen Lei Department Mathematics The University of Hong Kong 1eiywChku. hk
Department of Applied Mathematics Czech Technical University in Prague (CTU) rodrigo alvesêfit. crresffitt.uut.c. cvut.cz
Abstract
It has been recently observed in much of the literature that neural networks exhibit a bottleneck rank property: for larger depths, the activation and weights of neural networks trained with gradient- based methods tend to be of approximately low rank. In fact, the rank of the activations of each layer converges to fixed value referred to as the "bottleneck rank", which is the minimum rank required to represent the training data. This perspective is in line with the observation that regularizing linear networks (without activations) with weight decay is equivalent to minimizing the Schatten p quasi norm of the neural network. In this paper investigate the implications of this phenomenon for generalization. More specifically, we prove generalization bounds for neural networks which exploit the approximate low rank structure of the weight matrices if present. The final results rely on the Schatten p quasi norms of the weight matrices: for small p. the bounds exhibit sample complexity Ö(WrL²) where W and L are the width and depth of the neural network respectively and where r is the rank of the weight matrices. As p increases, the bound behaves more like norm-based bound instead.
Introduction
The success of neural networks in many applications during the most recent artificial intelligence boom has driven substantial research efforts into understanding their generalization behavior [
2
3
5
6
Whilst early work 7 focused on traditional approaches such as VC dimensions and parameter count, the increasingly evident ability of DNNs to generalize well (even in massively overparametrized regimes) has shifted the community's focus beyond purely architectural bounds {8] 91 is now accepted that satisfactory explanation of Neural Networks' generalizing abilities must incorporate more refined information about the training process and properties of the representation functions, which spontaneously arise from training DNNs natural data [I]
One of the simplest ways characterize the 'simplicity' of functions learnt by neural networks through the geometry of weight space is by considering norms of the weight matrices. Indeed, several works have provided various bounds with reduced or absent explicit dependence on architectural quantities, preferring to express neural network capacity through various functions of the weight matrices. Such generalization error bounds, which primarily rely on the norms of the weight matrices to express function class capacity are generally referred to as 'norm-based bounds'. The earliest attempts include many bounds obtained through various vector contraction inequalities and the
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

"peeling technique' [2 [13. In this subcategory of bounds, the Rademacher complexity is bounded iteratively by peeling off layers, resulting in a product of norms of the weight matrices. For instance, the Rademacher complexity bound in [13, which extends earlier work from [12] scales as [
2 _2_1 A N
(1.1)
Here, .N is the number of samples, 2 is an upper bound on the norms of the samples and AI...., Ar are the network's weight matrices. A remarkable feat of this bound the complete lack of explicit dependence on architectural parameters (i.e., depth, width, etc.). However, the implicit dependence introduced by the product of Frobenius norm large: even assuming that each weight matrix has unit spectral norm, if the rank of each A₂ is r and each matrix has homogeneous spectrum, then the sample complexity of r", an exponential dependence on the depth
bound will still correspond
Later norm- based bounds have largely favored alternative approaches via covering numbers, which yield less dramatic exponential depth dependence. The most recognizable examples of such results include the bounds of [3] and M. which were independently discovered through two approaches:
LWW VN
L II [Ael)
|
Melly Aell
δ
(1.2)
[I Mc) T
δ
Arl
(1.3)
||Ae|| A
Here the Mys are arbitrary reference matrices chosen in advance The implicit exponential depen- dence in depth is reduced to product of spectral norms which, at least in theory, could be expected to scale as O()) or forced to be a unit value [4]. With this interpretation, it becomes clearer that the bounds improve when the networks stay close initialization, especially if the number of updated weights is sparse, which would make the norm ((A, M,) 2,, small.
Such observations can begin to explain some of DNNs successes, in particular with respect to the lottery ticket hypothesis [13] However, they do not paint a complete picture, and are largely vacuous by large margins. In fact, the most impressive recent bounds in the theory of neural networks tend to implicitly incorporate data dependence. For instance, in 55 6, [6] various upper bounds on norms of activations of intermediary layers and Lipschitz constants of gradients equivalents through a powerful technique called loss function augmentation, greatly attenuating the implicit exponential dependency on depth. Pushing it to the extreme, [11] prove bounds which incorporate a notion of confidence for intermediary concepts learnt at each layer.
replaced by empirical
The discovery of the Neural Tangent Kernel 17 [8 is certainly one of the biggest breakthroughs in deep learning theory in recent years. Indeed, the underlying theory demonstrates that Neural Networks behave approximately like kernels at the overparametrized regime, and are able to characterize the model's s generalization behavior directly in terms of the alignment between the labels and the NTK features of the data distribution. However, such bounds rely very strict overparametrizationn assumptions. Furthermore, it has been shown that the NTK regime does not outperform the moderate overparametrrization regime 19 20).
Another tremendous advance towards understanding the generalization power of neural networks occurred with the gradual understanding that depth induces low-rank representations (21 23 24
25 26
In other words, the training dynamic of DNNs through gradient based methods naturally encourages low-rank representations, converging to a bottleneck intrinsic dimension which captures the data's 8 features parsimoniously. particular, the connection between weight decay and implicit Schatten quasi-norm regularizaion has been made in (26 24). There has been a lot of recent interest in this phenomenon, which has been demonstrated experimentally in various contexts spanning both DNNs, CNNs and even LLMs [27]. The phenomenon can most easily be understood by initially considering the case of linear neural networks. In this case, we have the following powerful result:
I For simplicity, we assume that the nonlinearities are 1-I-ipschizz in this related works section.
For instance, they can be set or the initialized values of the weights

---

Theorem 1.1 (cf. (24]. Theorem 1), Let w 2 min(C, d) and let Bi...., BL be matrices such that B1 E Rxxd Br E Cx B2 By-1 E RRxx For any matrix RCxd we have
L| 2 = min Σ B
subject to
BL- A.
(1.4)
SC,
For any matrix Z and any 0 < p 2, our notation
|2 refers to the Schatten quasi norm of 2
Z _h_ = L.)(
(1.5)
where 7;(2) (2) refers to the ith singular value of Z (listed in decreasing order). Thus, p approaches zero, the quantity / & approaches the rank the matrix Z. Slightly larger values of p induce softer form of rank sparsity. Thus, Theorem 1.1 implies that simple weight decay constraint on factor matrices B By is equivalent to a saak-itasstty inducing constraint on | where
0 when L - oc. Deep results 24 22 in optimization theory demonstrate that under specific circumstances, the above described implicit rank-sparsity inducing effect of weight decay at large depth occurs even in the presence of activation functions: the ranks of each layer's 's post activation representations converges to a single quantity referred to as the "bottleneck rank", which can be understood as the minimum dimension required to effectively represent the data.
In this work, we characterize the effects of rank-sparsity in the weight matrices in terms of generaliza- tion. We provide bounds which interpolate between the norm-based and parametric regimes at each layer with the parametric interpolation technique originally developed for matrix completion (28). This allows us to control the L (cf. Prop. F.2 or L (cf. Prop. [.3) covering number of each layer in term of the Schatten p quasi norms of the weight matrices. Treating Lipschitz and boundedness conditions on the loss function as constant, our contributions are summarized as follows.
We prove new generalization bounds for linear networks which incorporate the implicit low-rank effects of depth by incorporating the Schatten p quasi norm of the weight matrix.
As p 0, the bound provides sample complexity of Ô (IC d d[)an((A)). To the best of our knowledge, this is a new characterization of the generalization behavior of multi-class linear classification with low-rank dependencies between the classes.
For fully- fully-connected neural networks, prove (cf. Theorem 3.2) bounds of the order of
3FL x
B BT pol 1
[ Me 1.6..e [tel
[we + we-
Pr PC
Our results hold simultaneously over every sequence of Schatten indices pes, which we tune 2pr/ 2pt/[pc+2] and the low rank
to balance the effects of the norm-based factor 23 I1= Ax]
structure in the term |Ae / /|/e| Pe (for Mt- = 0).
We also provide extensions of those results relying Loss Function Augmentation to replace the norm- bose-based factor 2 11 P: ||]] by By B-
B _ A:] where B A
the maximum norm of convolutional patch at layer e 1.
To the best of our knowledge, the proof technique, parametric interpolation, has only been previously used in the context of matrix completion (28), a substantially different setting.
2 Related Works
Deep Learning Theory is a vast and active area of research spanning various topics from optimiza- tion 229 30 31
generalization 11 1.32 and the intersection between both [7 33). In this section,
we focus on norm-based and parameter-counting bounds for neural networks satisfying certain norm
but refer it quasi-norm cover the casesp and > 1. 'Whilst the low-rank properties of the activations and weight matrices are not exactly equivalent, they are closely related. Indeed, consider N input activations ...,, Tyy lying on subspace of dimension then for any weight matrix W e gm there exists matrix W mgd of rank Wa Wz for all i.
For p 1. Illl is
3

---

constraints. Indeed, this is the branch of literature closest to our work. A more mathematically
detailed deseription of the related works is available in Sections B
and C
Norm-based Bounds by peeling techniques were established for Deep Neural Networks in
12
and 13, resulting in bounds involving products of Frobenius norms of the weights (cf. equation (1.]
In [34] further norm boom- bounds were proved involving the products of the L norms of the columns of the weight matrices. Recently, the technique has also been ingeniously extended Convolutional
Neural Networks (CNNs) in [32] which elegantly exploits the sparsity of connections to achieve in
bounds of the order L, IT
I _ where w, is the spatial dimension of the convolutional vN
patches at layer and B is the maximum L norm of any convolutional patch. The results in [32 are not directly comparable to ours, and are especially well adapted to the case where the spatial dimension is very small. Indeed, as long as the convolutional filters are not one dimensional, the bound depends exponentially on depth. [16] also proves generalization bounds for CNNs which take weight sharing into account, and the bounds form the basis for the treatment of the norm based components in our proofs. However, the bounds in those works cannot incorporate rank-sparsity into the analysis and scale unfavorably with depth. There is also a variety of works which applies generalization
analyses to non-standard learning settings or loss functions, including pairwise [35] 33 37 learning
or triplet-based learning and contrastive learning [38 39 40 41 42
45 46
47
48). However,
such works usually focus the effect of the loss function. In addition to the above fundamental
works, many works provide non-vacuous bounds for practical architectures through various post processing techniques including data-dependent priors 49]. optimization of the bound or network compression/discreeizattoo [50 51 52 53). A particularly notable contribution is made in (54] which provides PAC Bayesian generalization bounds for two-layer networks where the main complexity term involves Froebenius norms of the weight matrices, remarkably, without an additional factor of the width, achieving non vacuous bounds in various cases. However, the bounds are PAC Bayesian and not directly comparable to ours since the training error is replaced by an expectation over a posterior distribution (derandomized analogues such (55) reintroduce a factor of width), only GELU and ERF activation functions are covered and the number of layers is limited to 2. The gradient dynamic of deep neural networks and deep linear networks was widely studied from an optimization perspective to demonstrate neural rank collapse, with some works also covering 63 In terms of the implications of such results for linear networks on generalization, one can of course consider the results which apply to neural networks with activations and apply them to this case [ (see Corollary [C.I for a transfer of such results to the linear case), or construct Rademacher complexity bounds specifically for linear networks as in (64). However, such approaches involve an exponential dependence on depth which make it more difficult to capture any low-rank structure in the classes, since such structure appears for larger values of T. (smaller values of p). One can also consider all existing bounds for the multi-class linear classification problem, where the state of the art is provided by 665 which proves bound
networks with activations 24 56 27 57 58
59
60
of Ō
AIE, 232
improving earlier results from 666 67 68
in terms of implicit dependence on
C. Since then, the result has been extended to many variants of the learning problem. including multi-label learning, structured output prediction and ranking problems [69] 70 71
72 73
Parameter counting bounds such those of 4 and 74 apply both to CNNs and DNNs (in fact, 774 proves both norm based and parameter counting bounds for DNNs, CNNs and ResNets). Taking into account implicit factors of L coming through logarithmic factors, the tightest parameter counting
bound in both cases scales like δ (v WL where W is the number of parameters in the network. Our
own result in Corollary G.6 additionally takes the low-rank structure into account. Norm-hased 75
and parameter counting 766 bounds have also been recently provided for transformers 777
To the best of our knowledge, there are only two works which have utilized the low-rank structure in neural networks: [3). relies on Schatten p norms of weight matrices to improve the bound (.1) for matrices with low Schatten p quasi-norm. The argument relies on Lipschitz continuity arguments and yields bounds with a decay in N worse than O (I/VN). The recent work (64] manages to
achieve tighter bounds taking explicit low-rank structure into account. The resulting bound scales
as L, oF' 1 [|Aell] Lry
W. One of the consequences of the proof strategy is the presence of

---

explicit exponential dependence on L through the term Cf where C1 is an intractable constant In addition, even ignoring the factor of CJ the bound still involves product of spectral norms (with an exponent of 1), whereas our bounds involve a product of spectral norms with a potentially smaller, tunable exponent of 3p However, the elegant and short proof in 64] does imply that there are far pe+22
fewer polylogarithmic factors compared to our bounds. See Appendix C for detailed formulae.
Our proof technique draws some inspiration from (28), which introduced the parametric interpolation technique to estimate the complexity of matrix completion with Schatten quasi norm constraints. However, the derivations are radically different. Indeed, in the matrix completion literature on approximate recovery 779 80 81 the observations are entries of an unknown matrix A: the independent variable = (i,j) in the supervised learning formulation is drawn from an arbitrary distribution over the discrete set of entries [m]] x [n]. In contrast, in our work, the observations are modelled as outputs of a neural network, i.e., they take the form F(xz) where F is a neural network as defined in equation (3.6). Even for a single linear layer, the learning setting is different and the outputs take the form Ar, instead of A... The analysis complexities directly through elaborate chaining arguments, bypassing the need for covering numbers and interpolating between p and p In fact, the authors mention that any readily obtainable covering number would yield vacuous bounds in the matrix completion context. In contrast, our analysis interpolates between p 0 and p and produces chainable covers for weight spaces with Schatten constraints. A more detailed discussion of related works is provided in Appendix C
(28] relies on bounding Rademacher
3
Main Results
We consider a learning problem using loss function 1 RC y R+, where C is the number of classes (in classification) or (in regression). In this work, we assume loss function is Li-Lipschitz with respect to the L norm and uniformly bounded by B. In regression, the output space whilst classification, it is y = (1,...,C)) C). In the case of regression, an example of such a loss function is the truncated square loss
IR
(( v) min(B, 1 y)
(3.1)
Indeed, in this case, the loss function uniformly bounded by B and uniformly B-Lipschitz. For classification, typical example used in much of the literature is the following margin loss 41:
1,
if arg max; D: # y,
by max
1(0 v)
if By max D1 7, sty
(3.2)
0.
if gy > max DJ 7
iFy
In this case, the loss function is uniformly bounded by B = 1 and uniformly 2/7-Lipschitz with respect the _ norm. We assume the learner is provided with N i.id. samples EN X Rdd and the associated labels V1...., yN y = (1.2.....C each of which is drawn from joint distribution D X y. We are interested in high probability bounds on the generalization gap:
N
1
GAP = 100 - = [[(FA(+).))
-
(F)()))..)),
(3.3)
N
where E denotes the empirical expectation over the sample (I1 "i.)......a)) (ZN, yN), and FA = F(A ((Au Av) is our trained network. For classification, an advantage of the margin loss described in Eq. (3.2) is that a bound on GAP immediately translates to a bound on the probability of misclassifi-
cation: let I,,x j - Ec denote the proportion of samples which are either classified
N
incorrectly or correctly but with margin & 7. The misclassification probability [ 4477 satisfies
arg max (axxmxxxxxx)) * < (F((A())) & GAP ( & GAP +1yx- (3.4) P
'The constant is described as 'rather large' in 778 since it accumulates factors of Talagrand's majorizing measure theorem and generic chaining, suggesting an absolute minimum C1 > 11.
5

---

We provide results for three types of models: Linear Networks, Deep Neural Networks, and Convo- lutional Neural Networks (CNN). In all the results below, the matrices Mr are reference matrices which can take any fixed value as long as it is chosen in advance. Thus, they play an analogous role to prior in PAC-Bayesian bounds [49]. Typical choices for Mr include Mf = 0 or setting Mj to the initialization when training neural networks with gradient based methods. Whilst traditional norm-based bounds such as (1.3) typically benefit from setting M, to the initialization, our bounds typically perform better by setting M,-- O, since this is the configuration which allows the quantity
|A,| |Aclee.
|A to approach rank(Ar), We provide an experimental evaluation of the behavior
of our bounds on MNIST and CIFAR- 10 for both DNNs and CNNs in Appendix D
3.1 Linear Networks
We first present our results for linear networks, which amount to generalization bounds for multi-class linear classification with a bounded loss in the presence of a low-rank structure over the classes. However, the true value of those results to illustrate the potential gains in generalization ability which arise from the implicit low-rank structure which appears in neural networks trained with gradient-based methods. In this section, consider classifiers defined as follows:
F: Rd
RC I Az BLBL-1 BA
(3.5)
for some matrices B, RCx BL- R ..... B2 2 B1 Ruxd
We have the following result, which shows the implications of Theorem I.I forr generalization:
Theorem 3.1. W.p. > 1 ö over the draw of the training set, every linear network as defined in equation
3.5 satisfies the following generalization bound: GAP 0 B
log(1/5)
N
δ
L1 2)
| 2-p
min(C, df [C d 2_
=ō [11
+..
प
IC d)
N
L
where B = supp |ao|]. and the Ô hides polylogarithiic factors of [||A|]] |Illsss.ps N,d,N,P N. 7.
The idea of the proof is separate the function class into two components by applying tunable thresholding operator in the singular values of the matrix A. A proof sketch is provided in subsec- tion 3.2.1 below and the full proof is included in the appendix. Our full results in the appendix (cf. Theorem E.2) incorporate a finer dependency on architectural quantities such as the number of classes through more refined analysis over different norms each activation space, though we omit such subtleties from the main paper to reduce confusion. Assuming L >> and L,, 2 E ((),
|| = V4, our Theorem 3.1 scales like Ō Σx [eel,,
in sample complexity, whereas the
known result scales as Ô L (C,d)) [[Bel in 3 Thus, the simplified analysis in the
7.
linear case removes a factor of L which allows taking the limit as L - 00: in this case, our bound rank(A). On the other bound since IlB
behaves more and more like a parameter-counting
hand, the dependency the input space dimension d is absent in 1.2). Whilst it may be possible to improve the dependency on d in Theorem 3.1 assuming the input data lies on a oiw-dinesiional subspace, this would require significant modifications to the proofs, and is best left to future work.
3.2 Fully Connected Neural Networks
We consider neural networks of the following form
(x) Ar.
(3.6)
where the matrices A R x are the weight matrices, A = (A4, AL-1 ....,, A1) denotes the set of weight matrices considered together, Wi denotes the width at layer and o1.... or denote elementwise activation functions with Lipschitz constants Pe for layers indices & < E2 we also use the notation f41-t2 for the function defined by pL p()) =
b,.... L. For any pair of
Ae, os 1 Ge, (A .).). The result below follows from Theorem E.2 in Ô notation:

---

Theorem 3.2. Fix reference matrices Mi...., My. For every 8 > 0, w.p. > 1 1 6, the following generalization bound holds simultaneously over all values of Pt E [0, for { ,....,L. L:
log 1/0)
L N
L. N
GAP δ
B
+
B
RFA
where
(3.7)
N
2F1 Pe-2
L Σ
||A
Me bc.pr
pe+2
[we + w 1 24
RFA :-
2
Pr
A,l
[Aglie
and the Ô absorbs polylog factors of B, W, max; Aell; Li and N. Here, p:= max 1 Pt denotes the maximum of all the indices Pt and 2 supt [20]|]
is the maximum input T.2 norm.
Next, using Loss Augmentation 5 6 we obtain the following extension where norm norm-based terms are replaced by milder analogues relying on empirical estimates of intermediary activations. Since the product of spectral norms estimate | I Ii_ || usually large compared to the activation norm (x)0) II. this can often lead to substantial numerical improvements, as seen in Section D.1
Theorem 3.3 (Cf. Theorem[E.6). Fix reference matrices M1, .... Mr. For every 8 > 0, w.p. the following bound holds simultaneously over all values of pt [0, for L = =1,, I...., L:
log (10)
T + BB
I. V RFA
GAP & Ô
B
N +
B[LL]
(3.8)
N
where B 1,1
max (maxign |F (
|| Melloo
Rm
Σ
B 1
1I 1=8
P:ll
[we. + Wi 11
Pe pe1z
Ae Pt
and the Ô notation absorbs polylogarihmiic factor of Be- 1.A, A, W, L, max; |Ail L1 and N. Here, p = max/=11 Pe is the maximum of index pt and B == sup ||> the maximum input L² norm.
Theorem 3.2 holds for all values of pe simultaneously: they be optimized after training. For pe 0 4L, Thm 3.3 yields a sample complexity of Ô L + L I + w However, the additive term of L can easily be removed with simpler argument dedicated to the situation where Pr = (ef. Thm. E.8). Thus, our results provide parametric complexity estimate for neural networks whose weight matrices satisfy a low rank property: for neural network with fixed width W, the sample complexity is Ô W rr rather than Ô (W²I,,) T.2) in pure parameter counting bound: when applying Corollary 3.3 Thm. E.8) network with fixed width W, each weight matrix A₃ E IR. WW only contributes Ò (Wr) 'parameters' to the sample complexity, instead of the full W Theorem 3.2 further incorporates approximate low rank structure. Indeed, in equation (37). the indices pt interpolate between the parametric and non parametric regimes.
When p increases, the term [A|pE captures low-rank structure inherent very small singular values which are not quite equal to zero. However, the threshold pe must be carefully tuned due
As a partial limitation, we note that the bound does not exactly coincide with the norm-based result I.3) when p is set to 2, since there is always parametric dependence on the input dimension from the term [C + d] praz; whilst the bound an interpolation between norm-based and parameter counting bounds, maintains slight bias towards parameter counting. However, this is achieved without being uniformly inferior
to tradeoff with the scaling factor of B III..
'In this paper, our Ô notation absorbs factors of max/-, ||Ar]. which is stricter than the alternative of accepting polylogarithmic factors of [ |A:] In particular, one of the multiplicative factors of in bound arises from a logarithmic factor in 1 [|Ae]] We find this approach more natural as it makes the full-rank parameter counting complexity Ö(WL) Ö(W L2) match classic bower-bounds VC dimension 7 82
7

---

to either. To see this, consider the one-layer case in an idealized situation where all the weights take binary values {1.-1}. Here, the norm-based bound (I.3) yields sample complexity of
((Cd), which agrees with parameter-counting. Theorem 3.2 also yields a sample complexity of
δ (M P min(C, d) श.ं max(C, d) ) = Ō [vCd|AA] δ (Cd).
3.2.1 Proof Sketches
To highlight our proof techniques, we provide a proof sketch for simplified versions of our results.
Proposition 3.4 (Simplified form of Proposition F22- covering number bound for one layer), Consider the following function class of linear maps from Rd R FP := {M E mm |M & M; ||] < s). For any e > O and for any dataset Ii...., IN E R2 such that |æx,|| < B for all i, we have the following bound on the L covering number (ef Prop. F2 for formal definition) of the class:
MB
mdNM
log(No & [m d]
log
Proof Sketch. For simplicity we assume B 1 in the sketch. For any matrix M E FF, write - mmin(m.d) A.n.d for its singular value decomposition (with the singular values ordered (any) decreasing order, including zeros). For threshold 7 to be determined later, we decompose every M Jp into M = M1 + M2 where M1 = ΣxTT P,u and M2 = Eist+1 Pe where T the last index such that pr > T. By Markov's 's inequality, since | = Σ, Pf E MM, we have rank rank(M, <
M & a. M. Thus, Mj belongs to the set J. == { E F rank(Z) & TF | & M) (a function class with few parameters its members are low-rank), Furthermore, it is clear that
& M" In addition, the spectral norm of M1 is bounded as follows: |M]l| P1
M
min(m.d) Σ
|
2
pû < r mmin(mmm)) d).
k=T+1
Therefore M2 belongs to the class F small norms). By parameter counting argument, we can bound the L covering number of Ff:
1Z miinnm,, d)} (whose members have
M
M
M
No. (o. x [m + d][rank] log(
mm
d]
log
By classic norm-based arguments (Thm. in 83
we can bound the covering number of F3 as:
Iog(AV(F,.c2)) $ [max Frob norm] log( 2 MndN 7mmin(m, d)
log(
e
Combining both bounds gives log(AN (FF)) & log(N((FP, log((N(F2,
7 mmmin(m,d d)
log( r'ddN
MP M) + Im + dl
log(
2
Tp
Setting M gives log( (og (FF)) & Im + dI [
log( mdN as expected.
We then show how to extend the proof to the two-layer case. Here, we consider networks of the form FA
(A x)) where a is an elementwise 1-Lipschitz activation function (e.g- ReLU) and A E _mad A RC'm are weight matrices. We fix pı = P2 p [0, 2] and 81, 82, MI, M2 > 0, and let F denote the class such networks which further satisfy for all ie (1, ||Ai]| & s; || M, (or, by abuse of notation, the corresponding matrices (A²,At). For simplicity, the loss l RC x [C] - - is assumed to be I-Lipschitz w.r.t. the _ norm.
8

---

Suppose we are given an i..dd. training set (I), (11.91)..... ................................ (# yN from a joint distribution over Rd [C] such that |-;] & B w.p. 1. For any 5 >> 0, w.p. >1 1 - 6, the generalization gap of any network FA E F is bounded by:
Proposition 3.5 (Simplified form of Proposition E.
ò 0 [5192] -ラक
b/2 VN
(og((10) N
[ni[m o) d A + r2(m + a
+
(3.9)
MP is a soft analogue of the rank and the Ô notation incorporates
where for 1,2. r2 == polylogarithmic factors of N, d, C, $1, 82, M2.
Proof Sketch. Sketch. Since the loss function is Lipschitz, we only need find an 7 cover of F, i.e., set C c F such that for any A = A²) E F, there exists a cover element (A',A% C such that
vi, (a,,)) la c
(here, recall Fa(x;) RC is vector of scores for all classes). We achieve this by adapting standard chaining techniques (see [3,5]), with the caveat that we need to change the norm of the cover at the intermediary layer, incurring a factor of ym. More precisely, let F _ denote the set of matrices A Ruxd and A E RCxm satisfying the relevant constraints above. First, we can apply Proposition 3.4 above, with 6 set to 6 := 1/22/mm0 to achieve a C1 Fi such that for
all A E F there exists a À E C such that Vi, |o (x))) (x:']) $ ||'' A²2zsl &
2
/mll & 1| A'xrell & mme
and (og( E Ô [m d] 202
M,
ò [m
d mm=+=
81 82
2v
M1
p=2
Similarly, for any π E C1, lo xx:x;)] & 81 B
Vi, and therefore
another application of Prop. 3.4 with B replaced by Bs B and replaced by e/2 yields cover
C2(A') with size log()C2(A4)) e Ö Ma[Bar] [M
δ [Bs] 82] 1
M2 p+z
The cover = UAtec, (2t) is now an e cover of F. Indeed, for any (A', E F, we can define A to be the cover element associated to A in C₁ and subsequently A² to be the cover element in (A+) associated to A which yields for any & N:
|AAoo(Axx)) - 1' (o(AAxx))l & [Aao(( A'o + (A'o(A'xx)) Aoo(A A aa)ll
< 62 + |A lo Furthermore, the resulting cover has cardinality bounded
(x:))) < e/2 + s =c.
log(IC)) E ò
[Bs1ss]
[m + d)
d
M1
+ [m + C7
M₂
3v
CB2
which yields eq
3.9 after substituting for r, and calculations based on Dudley's 's entropy integral.
Thm E.2 is then derived from a union bound to ensure uniformity over MI, M2 etc. This step is standard for 81, 82, M2 but involves more tedious continuity argument for the parameter p.
3.3 Convolutional Neural Networks (CNNs)
In this section, we present an extension of our results to Convolutional Neural Networks (CNNs). Since CNNs are well-known class of models, we leave more thorough description of our notation for the forward pass to Appendix G We denote the filters of each layer by A (which incorporates each weight only once), whist we use op(Ab to denote matricization of the layer, i.e., the matrix which represents the linear operation performed by the convolution layer E with the weights Ag- We use Ue for the number of channels and de to refer to the dimension of the input patches. This includes both spatial and channel dimensions: if the input is an RGB image and the filter has spatial dimension (2, 2). do 2 x 2 x 3 12. Thus, the number of trainable parameters at layer & is d Uz, and write wy for the spatial dimension at layer E (for instance, 28 x 28 image will have Wo 28 28- 784). Thus, Ue x we is the number of preactivations at layer L.

---

Theorem 3.6. Fix reference matrices Mi...., ML. For every å (0. 1), w.p. > 1 - ö, the following
generalization bound holds simultaneously over all values of $ Pr f = I....,
log(1/5 1/0)
L N
L
GAP & δ
B
+
B
+ B[LLI]
R
where
(3.10)
N
N
2Pr P2+3
1
1. Pill op (A))l
|A - Me
FET2
RS.
B
X
Lle + de-1 W
[ (pp(Ae)|pc
i-1
B: = sup = ||a||| and the Ô notation absorbs multiplicative factors of logarithms of the quantities B. W. .. W. L, max; op((A.) L1 and N. Here, Wt := U2 x we (for # L) and WL := 1.
This result incorporates weight sharing in the same sense as other CNN bounds 4 16]; the term
| Mr only involves the weights once, irrespective of the number of patches.
Theorem 3.7 (Cf. Theorem G.10 For every å E (0, 1), with probability greater than 1 - 6, the following generalization bound holds simultaneously over all values of 0 & pt & 2 l 1...., L
(0g(1/0)
L3 N
L
GAP &
B
+
BBBV
+
B[LL]
ITF
pempp R
where
N
N
2p1
L
L Pd op((A))
pr+2
| Mell |pp((A))
PC+2
RFx
B
Bi-LA 1.A
11
[Ue de
p2+3
i=t
B BE-LA: := max (max A AL- (z.) 1...1....... denotes the maximum norm of a convolu- tional patch layer & 8-1 1 and the Ô notation absorbs multiplicative factors of logarithms of the quantities B, W.A, A. W, L, max; op(A,)] L, N. Here, W, := Ug x We (for E + L) and W,, := 1.
Compared to [4) Thm. 3.7 incorporates a low-rank structure: each layer's contribution to sample complexity is reduced from L x Up x de (the number of parameters in the layer) to [eJ (Uz is the number of channels at layer E and d;-1 is the dimension of patches at layer - 1).
Conclusion and Future Directions
For linear networks, deep neural networks and convolutional neural networks, we have shown generalization bounds which capture the implications of approximate low-rank structure in weight matrices in terms of sample complexity. The bounds are expressed in terms of the Schatten p quasi norms the weight matrices, and are, to the best our knowledge, the first bounds for deep learning which incorporate both norm-based and parameter counting qualities. When p O. the bounds
behave like a parameter-counting sample complexity of Ô L + L i + wr-1]rank( As)).
taking into account (exact) low-rank structure in the weight matrices. For more moderate values of p. the bounds incorporate norm-based quantities and incorporate approximate low-rank structure. Even in the case of linear maps, Subsection provides original bounds for multi-class classification the presence of towrrank structure over the classes, offering an alternative to classic results such as [65]
limitation of our work is that require the weight matrices be low-rank, whereas most research on neural rank collapse 21 27 demonstrates instead that the activations at each layer are low-rank. The are very closely connected, but are not completely equivalent: it is possible that capturing the effect of low-rank activations could lead to further improvements and insights. Crucially, we believe substantial modification of our proofs could tackle such situations. However, this would require a much more challenging network-wide approach to the simultancous tuning of the parametric interpolation thresholds and is left to future work. Like other uniform convergence results which are agnostic to the training procedure, our bounds are vacuous at for seaee-scale networks in the absence of aggressive bound optimization, limitation which may be addressed in future work by better controlling the norm-based components during training, manually truncating the ranks or incorporating data-dependent priors with a Bayesian approach. Lastly, we note that the low-rank assumption requires overparametrization and is not always satisfied for smaller architectures or layers (cf. Appendix D). Finally, other tantalizing future directions include proving fast rates in N and the extension of our work to other architectures such Resnets and transformers.
10

---

Acknowledgements
Rodrigo Alves thanks Recombee for their support. The work of Yunwen Lei is partially supported by the Research Grants Council of Hong Kong [Project Nos. 17302624). We thank the anonymous reviewers, Felix Biggs and Nadav Timor for their comments on our manuseript.
References
margin bounds [1] Peter L Bartlet, Dylan J Foster, and Matus J Telgarsky. for neural networks. Advances in Neural Information Processing Systems, 30:6240-6249, 2017.
[2] Behnam Neyshabur, Srinadh Bhojanapalli, David Mcallester, and Nati Srebro. Exploring generalization in deep learning. In Guyon, U. V. Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems
30, pages 5947-5956. Curran Associates, Inc., 2017.
[3] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. PAC-bayesian approach to spectrally margin bounds for neural networks. In International Conference Learning Representations. openreview.net, 2018.
[4] Philip M. Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. In International Conference Learning Representations, 2020.
[5] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 9725 9736. Curran Associates, Inc., 2019.
[6] Vaishnavh Nagarajan and J. Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing poise-resilience. CoRR, abs//1905.133 13344, 2019.
[7] Martin Authony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge University Press, Cambridge, UK, 1999.
[8] Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
[9] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint arXiv: 1.0353011.00,,,.1 2017.
[10] Giacomo De Palma, Bobak Kiani, and Seth Lloyd. Random deep neural networks are biased towards simple functions. Advances in Neural Information Processing Systems, 32. 2019.
[11] Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. In International Conference on Learning Representations, 2020.
[12] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control neural networks. In Peter Grunwald, Elad Hazan, and Satyen Kale, editors, Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pages 1376-1401, Paris, France, 03-06 Jul 2015. PMLR.
[13] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Sire-independent sample complexity of neural networks. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 297-299, PMLR, 06-09 Jul 2018.
[14] Pedro Cisneros-Velarde, Zhijie Chen, Sanmi Koyejo, and Arindam Banerjee. Optimization and generalization guarantees for weight normalization, 2025.
[15] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference Learning Representations, 2019.

---

[16] Antoine Ledent, Waleed Mustafa. Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks, Proceedings of the AAAI Conference on Artificial Intelligence, 35(9):2279-822) 8287, May 2021.
[17] Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Fesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[18] Sanjeev Arora, S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In ICML, 2019.
[19] Soufiane Hayou, Arnaud Doucet, and Judith Rousscau. The curse of depth in kernel regime. In Melanic F. Pradier, Aaron Schein, Stephanie Hyland, Francisco J. R. Ruiz, and Jessica Z. Forde, editors, Proceedings "I (Still) Can't Believe It's Not Better!" at NeurIPS 2021 Workshops, volume 163 of Proceedings of Machine Learning Research, pages 41-47. PMLR, 13 Dec 2022.
[20] Philip M. Long. Properties of the after kernel. arXiv preprinl urXiv:2 10585, 2021.
[21] Arthur Jacot. Bottleneck structure in learned features: Low-dimension vs regularity tradeoff. In Advances in Neural Information Processing Systems, volume 36, 2023.
[22] Arthur Jacot. Implicit bias of large depth networks: a notion of rank for nonlinear functions, 2023.
[23] Zihan Wang and Arthur Jacot. Implicit bias of SGD in $1 25regullarie linear DNNs: One- way jumps from high to low rank. In The Twelfth International Conference on Learning Representations, 2024.
[24] Zhen Dai, Mina Karzand, and Nathan Srebro. Representation costs of linear neural networks: Analysis and design. Advances in Neural Information Processing Systems (NeurIPS), 2021.
[25] Seijin Kobayashi, Yassir Akram, and Johannes Von Oswald. Weight decay induces low-rank attention layers. In The Thirty-eighth Annual Conference on Neural Information Processing
Systems.
[26] Suzanna Parkinson, Greg Ongie, and Rebecca Willett. Relu neural networks with linear layers are biased towards single-and multi-index models. SIAM Journal on Mathematics of Data Science, 70):10221 2025.
[27] Laura Balzano, Tianjiao Ding, Benjamin D. Haeffele, Soo Min Kwon, Qing Qu, Peng Wang, Zhangyang Wang, and Can Yaras. An overview of low-rank structures in the training and adaptation of large models, 2025.
[28] Antoine Ledent and Rodrigo Alves. Generalization analysis of deep non-linear matrix com- pletion. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Confer- ence on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 26290-26360. PMLR, 21-27 Jul 2024.
[29] Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes wwer-paaameterized neural networks. In International Conference on Learning Representations, 2019.
[30] Yuan Cao, Difan Zou, Yuanzhi Li, and Quanquan Gu. The implicit bias of batch normalization in linear models and two-layer linear convolutional neural networks. In Annual Conference on Learning Theory (COLT), 2023.
[31] Arthur Jacot. Implicit bias of large depth networks: a notion of rank for nonlinear functions, 2022.
[32] Tomer Galanti, Mengjia Xu, Liane Galanti, and Tomaso Poggio. Norm-based generaliza- tion bounds for compositionally sparse neural networks. In Advances Neural Information Processing Systems, 2023.
12

---

[33] Spencer Frei, Yuan Cao, and Quanquan Gu. Provable generalization of ged-ttrinne neural networks of any width the presence of adversarial label noise. In International Conference on Machine Learning, pages 3427-3438. PMLR, 2021.
[34] Henry Gouk, Timothy M Hospedales, and Massimiliano Pontil. Distance-based regularisation of deep networks for fine-tuning. arXiv preprint arXiv:2002.08255. 2020.
[35] Stéphan Clémençon, Gábor Lugosi, and Nicolas Vayatis. Ranking and empirical minimization of u-statistics. The Annals of Statistics.
[36] Yunwen Lei, Antoine Ledent, and Marius Kloft. Sharper generalization bounds for pairwise learning. Advances in Neural Information Processing Systems, 33:21236-2 2020.
[37] Yunwen Lei, Mingrui Liu, and Yiming Ying. Generalization guarantee of sgd for pairwise learning. Advances neural information processing systems, 34:21216-21225, 2021.
[38] Sanjeev Arora. A theoretical analysis for contrastive representation learning. In International Conference Machine Learning. 2019.
[39] Yunwen Lei, Tianbao Yang, Yiming Ying, and Ding-Xuan Zhou, Generalization analysis for contrastive representation learning. In International Conference in Machine Learning, 2023.
[40] Jeff Z. HaoChen, Colin Wei, Adrien Gaidon, and Tengyu Ma. Provable guarantees for self- supervised deep learning with spectral contrastive loss. In Advances Neural Information Processing Systems, 2021.
[41] Nong Minh Hieu, Antoine Ledent, Yunwen Lei, and Cheng Yeaw Ku. Generalization analysis for deep contrastive representation learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 17186-17194, 2025.
[42] Nong Minh Hieu and Antoine Ledent. Generalization analysis for supervised contrastive representation learning under non-lll settings. In Forty-second International Conference on Machine Learning, 2025.
[43] Rodrigo Alves and Antoine Ledent. Context-aware representation: Jointly learning item features and selection from triplcts. IEEE Transactions on Neural Networks and Learning Systems, 36(4))6492-6502, 2025.
[44] Naghmeh Ghanooni, Dennis Wagner, Waleed Mustafa, Anthony Widjaja Lin, Sophie Fellenz, and Marius Kloft. Spectral dynamics of contrastive learning with spurious features. In High- dimensional Learning Dynamics 2025, 2025.
[45] Naghmeh Ghanooni, Waleed Mustafa, Yunwen Lei, Anthony Widjaja Lin, and Marius Kloft. Generalization bounds with logarithmic negative-sample dependence for adversarial contrastive learning. Transactions on Machine Learning Research, 2024.
[46] Naghmeh Ghanooni, Barbod Pajoum, Harshit Rawal, Sophie Fellenz, Vo Nguyen Le Duy, and Marius Kloft. Multi-level supervised contrastive learning. arXiv preprint 202202250..02202, 2025.
[47] Weiran Huang, Mingyang Yi, Xuyang Zhao, and Zihao Jiang. Towards the generalization of contrastive self-supervised learning. International Conference on Learning Representation, 2023.
[48] Xin Zou and Weiwei Liu. Generalization bounds for adversarial contrastive learning. Journal of Machine Learning Research, 2023.
[49] Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv: 100.111003110 2017.
[50] 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. arXiv preprint 18X4v:1804.05882, 2018.
13

---

[51] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression upproach. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 253-263, Stockholm, Sweden, 10-15 Jul 2018. PMLR.
[52] Sanae Lotfi, Marc Finzi, Sanyam Kapoor, Andres Potapezynski, Micah Goldblum, and An- drew G Wilson. Pac-bayes compression bounds so tight that they can explain generalization. Advances in Neural Information Processing Systems, 35:3 13313499-3,73, 2022.
[53] Waleed Mustafa, Philipp Liznerski, Antoine Ledent, Dennis Wagner, Puyu Wang, and Marius Kloft. Non-vacuous generalization bounds for adversarial risk in stochastic neural networks. In International conference on artificial intelligence and statistics, pages 4528-4536. PMLR, 2024.
[54] Felix Biggs and Benjamin Guedj. Non-vacuous generalisation bounds for shallow neural networks. In International conference machine learning, pages 1963-1981. PMLR, 2022.
[55] Felix Biggs and Benjamin Guedj. On margins and dcrandomisation in pac-bayes. In Interna- tional Conference on Artificial Intelligence and Statistics, pages 3709-3731. PMLR, 2022.
[56] Pierfrancesco Beneventano and Blake Woodworth. Gradient descent converges linearly to flatter minima than gradient flow in shallow linear networks, 2025.
[57] Tomer Galanti, Zachary Siegel, Aparna Gupte, and Tomaso Poggio. Characterizing the implicit bias of regularized sgd in rank minimization. arXiv e-prints, pages arXiv-2206, 2022.
[58] Minyoung Huh, Hossein Mobahi, Richard Zhang, Brian Cheung, Pulkit Agrawal, and Phillip Isola. The low-rank simplicity bias in deep networks. arXiv preprint arXiv:2103.10427, 2021. 2021.
[59] Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. volume 30, 2017.
[60] Guy Gur-Ari, Daniel A Roberts, and Ethan Dyer. Gradient descent happens in a tiny subspace. arXiv preprint arXiv: 18/2. 02.44444.44444222 2018.
[61] Nadav Timor, Gal Vardi, and Ohad Shamir. Implicit regularization towards rank minimization in relu networks. In International Conference Algorithmic Learning Theory, pages 1429-1459) PMLR, 2023.
[62] Vardan Papyan, XY Han, and David L Donoho. Prevalence of neural collapse during the terminal phase of deep learning training. Proceedings of the National Academy of Sciences, 117440):2462-224663, 2020.
[63] Akshay Rangamani, Marius Lindegaard, Tomer Galanti, and Tomaso A Poggio. Feature learning in deep classifiers through intermediate neural collapse. In International conference on machine learning, pages
PMLR, 2023.
[64] Andrea Pinto, Akshay Rangamani, and Tomaso A Poggio. On generalization bounds for neural networks with low rank layers. In Gautam Kamath and Po-Ling Loh, editors, Proceedings of The 36th International Conference on Algorithmic Learning Theory, volume 272 of Proceedings of Machine Learning Research, pages 921 PMLR, 24-27 Feb 2025.
[65] Yunwen Lei, Urun Dogan, Ding- Xuan Zhou, and Marius Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions on Information Theory, 65(5):2995- 3021, 2019.
Ding-Xuan
[66] Yann Guermeur. Lp-norm Sauer-Shelah lemma for margin multi-category classifiers. Journal of Computer and System Sciences, 89:450 - 473, 2017.
[67] Khadija Musayeva, Fabien Lauer, and Yann Guermeur. Rademacher complexity and general- ization performance of multi-category margin classifiers. Neurocomputing, 342:6 - 15, 2019. Advances in artificial neural networks, machine learning and computational intelligence.
14

---

[68] Mehryar Mohri and Andres Munoz Medina. Learning theory and algorithms for revenue optimization in second price auctions with reserve. In Eric Xing and Tony Jebara, editors, Pro- ceedings of the 31 International Conference on Machine Learning. volume 32 of Proceediiggs of Machine Learning Research, pages 362-270, Bejing, China, 22-24 Jun 2014. PMI..
[69] Liang Wu, Antoine Ledent, Yunwen Lei, and Marius Kloft. Fine- tiee-graneed generalization analysis of vector-valued learning. In Proceedings of the AAAI Conference Artificial Intelligence. volume 35, pages 10338-10346, 2021.
[70] Waleed Mustafa, Yunwen Lei, Antoine Ledent, and Marius Kloft. Fine- Fine-graine grained generalization analysis of structured output prediction. arXiv preprint arXiv:2106.001 15, 2021.
[71] Zi-Hao Zhou, Jun-Jie Wang, Tong Wei, and Min-Ling Zhang. Weakly-supervised contrastive learning for imprecise class labels. arXiv preprint
2025.
[72] Yifan Zhang and Min-Ling Zhang. Generalization analysis for multi-label learning. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learming, volume 235 of Proceedings of Machine Learning Research, pages 60220-60243. PMLR, 21-27 Jul 2024.
[73] Jin Zhang, Ze Liu, Defu Lian, and Enhong Chen. Generalization error bounds for two-stage recommender systems with tree structure. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[74] Florian Graf, Sebastian Zeng. Bastian Rieck, Marc Niethammer, and Roland Kwitt. On measuring excess capacity in neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 10164-10178. Curran Associates, Inc., 2022.
[75] Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang. Inductive biases and vari- able creation in self-attention mechanisms. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 5793-5831. PMLR, 17-23 Jul 2022.
[76] Yufeng Zhang, Boyi Liu, Qi Cai, Lingxiao Wang, and Zhaoran Wang. An analysis of attention via the lens of exchangeability and latent variable models. arXiv preprint arX2522212.14852 2022.
[77] Jacob Trauger and Ambuj Tewari. Sequence length independent norm-based generalization bounds for transformers. In International Conference on Artificial Intelligence and Statistics, pages 1413. PMLR, 2024.
[78] Andreas Maurer. A chain rule for the expected suprema of gaussian processes. In Proceedings of the 27th Annual Conference on Learning Theory (COLT), pages 245-257. PMLR, 2014.
[79] Rina Foygel, Ruslan Salakhutdinov, Ohad Shamir, and Nathan Srebro. Learning with the weighted trace-norm under arbitrary sampling distributions. In Advances in Neural Information Processing Systems, pages 2133-2141, 2011.
[80] Nathan Srebro and Russ R Salakhutdinov. Collaborative filtering in a non-uniform world: Learning with the weighted trace norm. In J. D. Lafferty, C. K. I. Williams, J. Taylo,,, R. S. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems 23, pages 2056-2064. Curran Associates, Inc., 2010.
[81] Ohad Shamir and Shai Shalev-Shwarzz. Collaborative filtering with the trace norm: Learning, bounding, and transducing. In Proceedings of the 24th Annual Conference on Learning Theory, volume 19 of Proceedings of Machine Learning Research, pages 661-678. PMLR, 2011.
[82] Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve- dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20(63):1-17, 2019.
15

---

[83] Tong Zhang. Covering number bounds of certain regularized linear function classes. J. Mach. Learn. Res., 2:527-550, March 2002.
[84] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. Adaptive Computation and Machine Learning. MIT Press, Cambridge, MA, 2 edition, 2018.
[85] Vitaly Kuznetsov, Mehryar Mohri, and Umar Syed. Multi-class deep boosting. In Advances in
Neural Information Processing Systems, pages 2501-2509, 2014.
[86] Yann Guermeur. Combining discriminant models with new multi-class syms. Pattern Analysis Applications, 5(2):168-179) 179, Jun 2002.
[87] Vladimir Koltchinskii, Karim Lounici, and Alexandre B. Tsybakov. Nuclear- norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist., 39(5):3302-2323) 10 2011.
[88] Yunwen Lei, Urun Dogan, Alexander Binder, and Marius Kloft. Multi-class svms: From tighter date-dependent generalization bounds to novel algorithms. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[89] Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprini 1806.0550 2018.
[90] Nathan Srebro and Adi Shraibman. Rank, trace-norm and max-norm. Peter Auer and Ron Meir, editors, Learning Theory, pages 545-560, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg.
[91] Robert Vandermeulen and Antoine Ledent. Beyond smoothness: Incorporating low-rank analysis into nonparametric density estimation. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 12180-12193. Curran Associates, Inc., 2021.
[92] Chen Xu, Zhouchen Lin, and Hongbin Zha. A unified convex surrogate for the schatten-p norm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
[93] Fanhua Shang, Yuanyuan Liu, and James Cheng. Tractable and scalable schatten quasi-norm approximations for rank minimization. In Artificial Intelligence and Statistics, pages 620-629. PMLR, 2016.
[94] Fanhua Shang, Yuanyuan Liu, and James Cheng. Unified scalable equivalent formulations for schatten quasi-norms. arXiv preprint arXiv: T0t::666600000 2016.
[95] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. In David Helmbold and Bob Williamson, editors, Computational Learning Theory, pages 224-240, Berlin, Heidelberg, 2001. Springer Berlin Hcidelberg.
[96] Clayton Scott. Rademacher complexity. Lecture Notes, Statistical Learning Theory, 2014.
[97] Yann Guermeur. Rademacher complexity of margin multi-category classifiers. Neural Comput- ing and Applications, 12:17995-18808, 2020.
(98] R.M Dudley. The sizes of compact subsets hilbert space and continuity of gaussian processes. Journal of Functional Analysis, 1(3):290-330, 1967.
[99] Antoine Ledent, Rodrigo Alves, Yunwen Lei, and Marius Kloft. Fine Fine-grained generalization analysis of inductive matrix completion. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages
Curran Associates, Inc., 2021.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
We discuss limitations of the results in multiple places the main paper and appendix.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
17

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
18

---

Answer: [No]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
pablice/guides/CodeSuubbbe iow.eeeesubmsiisooooooooo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to rum to reproduce the results. See the NeurIPS code and data submission guidelines (https
//nips.cem mtapps.cc/ubblic/guu.de wwtp///ooeeesssieeooee wwaplbmmsssooPPPoo ssiocllyycy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: Computing the bounds over many different runs is computationally prohibitive. In addition, similarly to norm-based bounds, our results demonstrate the bounds' ability to capture the relationship between each trained network's weight configurations and the test performance. This cannot be achieved if the results are averaged over many runs. We do run our experiments over many width configurations on both DNNs and CNNs for many width configurations and observe similar behavior. Lastly, the focus of our work is mostly theoretical, and our experimental setup is in line with comparable literature.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
19

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: this work of purely theoretical nature and there are no negative possible societal consequences to consider.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
20

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
21

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
22

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy (https: http:pa//eeeerreeecc///ooorrrere for what should or should not be described.
23

---

A Table of Notation
Notation
Meaning
Spectral norm of matrix
|| +l, 1112
(L.) Norm of vector
1- Fr
Frobenius norm of matrix
- sec.p
Schatten p quasi norm of matrix
||
Nuclear norm
| |Z 2,1
Σ V Z
C
Number of classes
Loss function Lipschitz constant of 1 (W.r.t L norm)
L
B
upper bound on
Ag Rwexwe-1
Weight matrix at layer & Reference matrix at layer &
Mt E 1
(Flementwise) Activation function at layer &
Pe
Lipschitz constant of ae
FA(x)= == A1or(A4-101, 01, (... (A't)))) F (i)
NN with weight matrices A ........ AL
(Cf. Equation (36))
ot At 0 (A++1))....
Map from layer & to layer Eg
Architectural Quantities
Depth
Number of samples
We
Width layer max/_ we
W
(Maximum width of the network)
min(we we, we-1)
[we + we-1l if 8 "r if l input dimension
Wf
[weee]]
d
Function Classes
Fi
[Z E IR mmxd 12 & MM
{ L E R_xxd 12 PL & MM = rsp;
FP
||
&,a
{ E Rmudd
.rank (A)
r, |||| & s}
B
AA R x 1
|A Me Mellsc, & MM; |Ael < st)
{ F F(A Ae)
Ar E Br Vf L} (cf. Eq. (E.])
FB
(F F(AI..AA)))
|A M s: Me |||
& 84
34 4 L)
Saaus
(aagg (FA,
FA FF)
{ (Dagg (FA, FA F
Constraints/scaling factors
Pe
Schatten index for layer {
p max Pt
Maximum Schatten index over all layers
24

---

Upper bound on ||
Upper bound on ||Ael (fully connected)
M
Upper bound on se..
M2
Upper bound on || - Melsa.pe
MP
(rank proxy)
If
M.
(rank proxy)
B
sup ||تا|||
Pt
a priori upper bound on rank ( (Ae)
Be-1.A
max (max | FAr (x:))l: 1)
Constants/log factors
Typ
16|MP +1 1
+7 mN
e
16 +1]
+ m.
TzP
10 +1][6TT PEr
1w
+7 WaN
T
P8 +1][61H Aus 11 1w
+7 N
T
128 4 I2= + 1]s; 11 + [][L + 11W
[b+
Ule 1]s; + 11]
I
12 1b 1][L + + (E.141)
( ( 40. cf. eq
TFC
+ 1]
[4W + IT, P. A.I]
Oog
2 log [W + b11. p AA11] log(b)
- [og
2 log((W))
[B + 21[ + +1] N -= Up: 1|[[Aa1 2] + 1]
log 1W + b I[. |i|| Arl] x
Auay θ
log
log(bb + T. Eイ_ log
Aell) Σ log (Be.A) 2 WW)
Convolutional Neural Networks
O2 We
Number of convolutional patches at layer é
Spatial dimension at layer f Number of spatial dimensions before pooling at layer &
O
U.
Number of channel dimensions at layer
de
Dimension of input patches layer oth Convolutional Patch at layer e Weight matrix at layer {
84.0 [Ue] x [we]
At RUXxde
Mr. E RUixds
Initialized weight matrix layer Convolution operation associated to Ag
A
Represented by the matrix (At) RUixx -, RUx
Activation function (including pooling) (ar o AAt OT_11 AAi-1 o o...or ....i AA))(r)
FC A AL
(Cf. Equation (G.T)
25

---

Ei Up x Oz-1
A
(Total number of preactivations)
Σ de x Ur
W
(Total number of parameters in the network)
FA F ((A AL) IA Melac & Me.
Fg
op((A)) & se V L, ||A sD
Spatial patch size at layer l
max., )
B
Maximum norm of convolutional patch input layer
Constants/log factors for CNNs
12 S + ,ا -e (A.) + 11]
x [[W + II Pi op(4,)]
[ +1]WAN Th (A) + 11]
YeAuuu
[4 + 23 [I P: op A:)]]
16[MP + + 7) U'NO
Tee
cx12
re
16 +1][0 I PLs. 1 [ 7 NA
FP
16| +1|[++]||+++ +d|0'w' + +7) U'NO
ex
[ + 2] +1 + 1Jl1 A. + +2] + 11]
+ +1)) + 1]s; + 1]
Table 1: Table of notations for quick reference
26

---

B Table of Comparison to Existing Literature
Linear Classification
Linear Networks
Proof Technique
Bound (excluding polylog factors)
Reference
Parameter Counting
L N
66
L B V c LAIE
6
Norm Based
84
64
Norm- bonm-based/peeling from Linear Networks
L1 B V
Cmin (Rank Br
Ie Bell
64
N
L
Norm-based
L 2
65
Deduced from
clu
Norm-based
L BL 3
|||
2-1
00 7.
or 1
cf. Corollary
| pe.p [c+d]
Parametric Interpolation
BL 3कp
cf. Theorem 3.1
B
rank CA
0 in above line
DNNs, norm-based
2 11 LAI
Peeling
L V
13
[4]
Peeling
L max;
Ax
[All]
I g 4tp
13
2=35
Cly Ldiee
+ + of -f- lnc
Cov/wnr LArle-
L
TAil
Peeling
VN
64
1 |e
(Peeling)
L C
T |ell
W Lry
Particular case of above
N
Pac Bayes
T LVW vN
( (
(Σ
|
12 LAv
Covering Numbers
L
1= |
L
I(A--M
T
VN
|1a2|
DNNs, Parameter Counting
B V
WSL N
WL N
74
Iuy + wy
[rank[A) (A,
B
Theorem
E.8
N
27

---

DNNs Parametric Interpolation
B
2p1 B - P:1l 12
>
x
Theorem 3.2
AAe-Melannn
FE+2
we + wig 1]
1 1212
L1] 24p
25% B 1 Pi Pil
Parametric Interpolation & Loss augmentation
-
Theorem 3.3
|4 My
P2+2
24 p212
We + wy
CNNs, Parameter Counting
B
V
WSL N
B
WL
74
N
(U de rankk Az)
B
Corollary G.6
N
CNNs,
Norm-based
Covering Numbers
bllk [p((A))] VN
-e-1
Unwy [Mel 12,11 [pp(Ac]
L L1l | 8,
Peeling
32
CNNs
Parametric Interpolation
BI LJ デ f
Theorem G.5
Σ
B I Psl op(A,)]
Note:
We Up we
(for * L)
M Mr li
F++2
[Ue + de W. PC+2
and Wt = 1.
[pp(Ac)
B 2
2pc Be L IT Pil op(A,)]
Parametric Interpolation and Loss augmentation
Di=1
x
Theorem 3.7
Mee (ec Top(Az)
Petz
[Ue + de-1lW.Pr+ p(+2
28

---

Table 2: Summary of results and previous State of the Art. By convention, all results expressed in Ô notation, which hides polylogarithmic factors of all relevant architectural AW W, L) and scaling (maxe Aell A|lss etc.) quantities. In addition, we only consider the dominant Rademacher
(1/6)
complexity term: for simplicity we ignore both the missing terms of O [
and additional N
which would occur from making the bounds post hoc w.r.t. to the norm constraints (some works do this explicitly whilst some do not).
terms of the form (v
L N
29

---

C In-depth Comparison to Existing Works
In all the descriptions below, the Ō notation absorbs polylogarithmic factors in B, W, max; ||Ael, L1 as well as the Lipschitz constant L of loss or margin 7. Recall that in [3. it was shown that
log(Li 1/6)
LVW L
(
A
GAP O
BB
&
(C.1)
N
VN
2
In 1 it was shown that with probability greater than over the draw of the training set we have
log (18(1/8)
1
IIA
GAP By
L
A
(C.2)
N
Ap
Note that equation C.1 on a PAC Bayes approach).
discovered concurrently with C.2 with different approach
3
relied
C.1 Bounds for Linear Neural Networks
In this subsection, we briefly list generalization bounds which can be obtained for linear maps in the multi-class classification case, focussing especially on the ones which apply to linear networks form Bg... B1-
Most of the early literature on generalization bounds for linear multi-class classification focused on kernels, which are slightly more general setting.
For single output (C 1), it is well known from early results
688
83
that the Rademacher
complexity 7 of linear classifiers is bounded as Ö (v |a|2
1
B
||
Early
N²
work on generalization bounds for multi-class classification
86
used inequal-
ities for Rademacher complexities of composite function classes to obtain bounds of the form
δ
ClAIi N Later 88 65 the bound was refined to Ō
2
[A| N
by exploiting the L
continuity of common loss functions.
In the authors proved the following bound specifically targetted at linear networks of the form
A BL ByBi:
δ B C minne(RRnk( BB)) [
(C.3)
Note that [[ Bell > ||||| and |A| min: Vrank(BB > rrakka)))A) > |Al|Er- Thus, the bound
in behaves at least as Ō (V
/Caaj N
wwhcch exhibits the same behavior as the results in 86 66
The results expressed in terms of vector output Gaussian complexity, which has the advantage of yielding bounds for L2 Lipschitz loss functions. When the loss function is L Lipschitz, the bound from 665 will be tighter by factor of VC (ignoring any logarithmic factors). The main advantage of
the bound in equation (C.3) the introduction of the novel proof technique which also allows the authors to derive the bound CC. for neural networks with activation functions.
Comparison between Bound and Theorem for linear networks:
is worth noting that the Bound
C.
can be instantiated follows:
For simplicity, we use Ô notation, however, many of the result in this section do not require logarithmic factors when expressed as function of Rademacher complexity only. However, making them post hoc w.r.t. to the constraints requires additional logarithmic factors.
30

---

Corollary C.1. With probability greater than 1 over the draw of the training set. every matrix A satisfies the following generalization bound
2 C|A sc,
GAP &
BN
log (
I1 1||||| -
(C.4)
N
Proof. By the proof Theorem the values of Bi.... B2 which minimize the weight decay regulariser > Er satisfy [_B,] = |||] t and even o, (B,)) = a (A) for all &, where (Z) denotes the ith singular value of the matrix Z. It follows that for this choice of Bes, have
The theorem follows upon replacing the values into T1 e [B,]] ||| - and Belli ||A
equation (C.II
In contrast, for p L. our Theorem 3.1 scales
2p Ba
A
min(C, d) df max(C, d)
δ Li 2tp
scp
N
2 BLTT
A
[C d
< δ
(C.5)
N
The directly comparable: for thing, the bound in CC.4) is purely norm-based, which means that enjoys more obvious scaling properties. This also makes more vulnerable to large inputs. It is worth noting that both bounds potentially improve when L grows, as this influences the schatten quasi norm index. However, this benefit is strongly mitigated in the case of (C.T) by the multiplicative factors of L, which are not present our case. The explicit dependency on C is also worse in (C.I). but we believe this is an artefact of the L based proof technique and might be improvable with an argument more carefully dedicated to the linear case.
C.2 Norm-based Bounds for Fully Connected Neural Networks
Rademacher complexity bounds of the following order were In 13], extending work from obtained:
B2 L
A
δ
T
1=1
(C.6)
N
In addition, the same paper norms of the weight matrices. For instance (Corollary page 13) for any fixed value p: GAP
13 contains other variants, which mostly consist of products of various
log( N
L
1
B
+ L Bu
[el
(C.7)
P
N
where 2/ is an apriori upper bound on max, [Ael
14 Note: we have simplified the expression to adapt
it to our Ô notation assuming that Mp(A) M(A) & O(Wb). where M,(A) (resp. (A)) upper bounds on the Schatten p and spectral norms of A respectively (such an assumption makes sense since for
any matrix with dimensions bounded by W, we have IAlee & W not possible to directly [A|
compare the factors of L in our bounds and in (C.7) since fully post hoc version of that result would likely involve further factors of in our own proof.
Note that 14 < W. thus setting p 3 we obtain for instance
(og(1/8)
L
GAP
B
δ
L
2 F-1
AR
(C.8)
N
N
31

---

Still in the category of 'peeling' based bounds relying vector contraction inequalities, the recent work of [64 (cf. Theorem 7). which appeared independently of the present work, has established bounds of the following form for the Gaussian complexity of neural networks with fixed norm and rank constraints
L
Civ
LAil [A
Et N
LAcle T
A
B
(C.9)
where řg is an upper bound on the rank of layer f. In fact, notable property of the bound is that there are no logarithmic factors in the Rademacher complexity bound: however, note the Rademacher complexity bound into an excess risk bound would incur at least logarithmic factor of N, and making the bound post hoc w.r.t the norm constraints would incur additional logarithmic factors of the norms, well as a non logarithmic factor of VL. Here, C1, C2 are unspecified constants inherited from [78] (which are described as 'rather large' on page 4 of (78)). However, the authors in (64) do conjecture that the constants and the accompanying explicitly exponential dependence on depth could be removed with more careful analysis
W L
0
C
1
Aell
(C.10)
N
where & denotes the Gaussian complexity, and r the minimum rank of the weight matrices AL.
Comparison between CC.00 in and 125
Both results take the low-rank structure of the weight matrices into account and improve when neural collapse occurs. However, both the proof techniques and the final results differ significantly. Whilst translating the bound (C.10) into an excess risk bound would imply at least a logarithmic factor of N, and making the bound post hoc w.r.t. the norm constraints would incur additional logarithmic factors of the norms, as well non logarithmic factor of /L, the bound for the Gaussian complexity is free of any logarithmic factors (in contrast, even our Rademacher complexity bound from the calculation in Proposition E. includes logarithmic factors of the norms arising from the application of *
results such at Lemma I.5 which could give it an advantage when L is small. On the other hand, the bound C0 and C.9 exhibit both explicit and implicit exponential dependence on depth through the factors CT and Aell respectively. In contrast, the result in G.7 has no non logarithmic dependency on norm based quantities. In fact, it belongs the family of parameter counting bounds, whilst (C) is a purely norm based. In the case where all the spectral norms and the norms of the datapoints are considered to be O(1), the bound (C.10) amounts to sample complexity of OCP'' L2W), whilst sample complexity of Ô (rL"W) thus, the bounds nearly identical in this particular situation apart from the removal of factor of rCf (which removes exponential dependence on depth) in our work at the cost of additional logarithmic factors. It is worth noting that the proofs are radically different: we rely on layer-wise covering numbers analogous to [ 4 [4]
Theorem G.7 amounts
whilst [64] relies on vector contraction incqualities and is closer the works of [12 13.. In particular, one of the factors L inside the square root in Theorem E.8 arises from making the bounds post hoc w.r.t. the spectral norms. It would be interesting investigate whether this factor can be removed when assuming that [A = 1 for all L.
Several other comparable bounds are proved in 664,, which appeared independently of the present work. The bounds only apply to the exactly low-rank case, whilst we provide a more refined analysis based on the singular value spectrum decay implicit in the low Schatten quasi norm constraints. In addition, we also consider convolutional neural networks, and the proof techniques are radically different.
32

---

C.3 Norm-based Bounds for Convolutional Neural Networks:
In 16 it was shown that)
D (T))2
log(1/6)
1/6) N
GAP
&
δ
VI
(C.11)
N
where if & 1-
IT [p.))))
Tj B (X)((X)](AA Me) "ll.alaavuu max
(x
and L.
Tτ Bx-1(XX)
1
M I
Here, denote Bx(X) max; (x)ll where the norm ||- denotes the maximum L22 norm of convolutional patch for vector of activations at layer &.
The above bound relies on loss function augmentation to control the L2 norm of patches at each layer. However, the following simpler bound (Theorem E.2) can also of interest:
GAP-O (8 BB (1/(1/8)
37
Li LIVIII op(A))
Σ
Ugwel Me] Opp( Ax)l
12.1
(C.12)
Recently, in 332 an ingenious approach was used to provide bounds for convolutional neural networks in terms of products of the Frobenius norms of the weight matrices. The bounds and proof techniques are closer to the school of [12 [3] than those of []], and rely on vector concentration inequalities and direct calculations of Rademacher complexities rather than covering numbers, whilst incorporating many novel elements specific to the CNN situation. We have, considering a post hoe version of
Theorem 3.2 in 32 and translating to our notation, GAP-O
log(1/8)
12 N
Mellryy L 11 W,B
δ
B
(C.13)
VN
where wy denotes the spatial size of the convolutional patches at layer l and B max., (1 (I::)so.) go.. the maximum 2 norm of convolutional patch in the input.
The bounds (C.12) and (C.13) exploit the sparsity of connections the first layer to obtain bounds which only depend on the maximum norm of an input convolutional patch (as opposed to the full norm of the input), a characteristic which shared by our result (cf. theorem [3.6] In addition, the results in [16] exploit the weight sharing to involve only the norms of the weight matrices (rather than the linear operators op( At)) in the numerator. Quite remarkably, the bound in achieves a similar effect in the context of peeling type results by relying exclusively on the sparsity of connections. Our results for CNNs can be interpreted as low-rank generalization of those in [16] incorporating low-rank structure in the weight matrices, just However, the results [32 are not directly comparable, since they belong to the peeling family, affording them more favorable dependence width but poorer dependence on depth if the norms || B. are moderately large.
results for DNNs generalize those of []]
As explained in the main paper, convention on ő notation stricter than that in [16]: allow the ő Ö(L), which explains the additional
absorb factors of log pggmmx/21 Aell), but treat log(IT AA))) multiplicative factor of VL. This factor is absent in (74) due to the use of purely L2 covering number approach, though the implicit dependency the number of classes at the last layer stronger.
33

---

C.4 Parameter Counting Bounds
In 7 generalization bounds based on VC dimensions were established for fully connected neural networks. In more recent research the focus of parameter counting bounds has been on different architectures such as Convolutional Neural Networks or ResNets. We focus on CNNs below this work focuses on DNNs and CNNs.
In 4 (Theorem 3.1) the following bound is proved for CNNs with fixed norm constraints:
WSL
log 1/6)
GAP & Ō B
+ B
(C.14)
N
N
where W := Σi=1 de-1 x U2 denotes the total number of parameters in the network and S is an priori upper bound on [[maxe| |Ael]] 1].
Later in 74 (Theorem 3.4), the following result was showr
WL GAP = B
log(1/8)
N + BB N
(C.15)
Note: in 4. the regime of interest that where the spectral norms the weight matrices approach which explains the appearance of the quantity S. In fact, the quantity appears through upper bound on the product of spectral norms as (1 + vi & exp(vT.), thus, the multiplicative factor of [LS] can relatively straightforwardly be replaced by Ö(L). This results in bound which looks identical equation (C.15) when expressed in Ô notation. However, the bound in [74] presents many other advantages, including applicability to Resnets and much smaller constants and logarithmic factors. We also note that (89] provide rank-sensitive bounds for neural networks. However, the bounds include a multiplicative factor of the Jacobian of the full network (both outside and inside the logarithmic factors): the bounds will coincide (up to log factors) with our pure parameter counting bounds in the particular case when all the spectral norms of the weights are exactly equal to 1, but behave less favorably in other cases.
D Experiments
In this section, present some experiments demonstrate that our bound successfully capture the low rank structure in the weights to improve upon competing bounds. Although the numerical advantage of our bounds the bounds generally show a much milder growth as the width of the layers grows compared to all existing bounds when the generalization gap kept relatively constant. Thus, our bounds are able to adapt to capture the presence of unused function class capacity in the form of low-rank weights. We present results for both DNNs on the MNIST dataset and CNNs the CIFAR-10 dataset. All experiments were run with 128 CPUs with 500GB ram and DGX A100.
the best compared method (the parameter counting bounds of (74))
D.1 Fully-connected Neural Networks (MNIST)
To evaluate the bounds' behavior for fully connected neural networks, we conducted experiments on the MNIST dataset. We set the number of non-linear hidden layers to L = 3 and varied the width of the hidden layers wy in {300, 400, 500, 700) explore different regimes. To guarantee that we could analyze the phenomenon studied in this research, we enforced rank-sparsity through two complementary approaches: (1) implicitly, by preceding each non- non-linear hidden layer with four linear layers. (2) explicitly, by regularizing the neural network through weight decay. We selected the regularization parameter from (10-1, 10-4 10-3 102) and analyzed models with the
Note, keeping in line with the convention used for the Ò notation in this paper, interpret [max; [Ael]] a constant. This implies that the presence the quantities Ct,, in (74) introduces logarithmic dependency [maxe] [el]] inside the square root, corresponding multiplicative factor of L inside the square root.
34

---

highest weight decay that achieved an accuracy of at least 0.9. We then maximize the margin subject I,x & 0.1.
The results can be seen in Figure D.1 To facilitate comparison, denser bars are lower than less dense bars when compared to their counterparts, i.e, by considering models with the width. In addition, we only plot the bounds in Ô terms, igmoring all polylogarithmic factors. This facilitates the comparison since some competing baselines are post hoc whilst some are not: our bounds hold uniformly over all values of pe, A MMll sec.pe: etc., whilst some of the related works not explicitly perform the required union bound to achieve this. The practice of evaluating the numerical values of generalization bounds only up to polylogarithmic factors [74] 64 or not all
in line with the literature. When comparing to [64], we evaluate the bound for two values of the intractable constant C = 1, This is to account for the the authors' statement that the factor of Cf could potentially be removed with a more refined proof, and certainly underestimates the numerical value the established bound, since the constant C₁ is 'rather large' [78]. We include both versions of our bound: Theorem 3.2 (without loss function augmentation) and Theorem 3.3 (with loss function augmentation). A key observation is that as the width increases, our bounds do not increase as fast of the rank sparsity of the problem: in this
the competing results, suggesting successful experiment, the accuracy and generalization gap are constant (overparametrized regime), therefore, the modest growth exhibited by model indicates better ability to capture generalization error than the competing methods, which show much sharper growth with width.
Width (w)
Bound (Log Scale)
2
490
503
700
8
(Banter 2017) Bi
(Golwwchh 2018) Bg C5)
Eq Cs
(Golowich er 2018 Fq, C7
(Nopshabur al, 2018) Fig cin
(Long Sedgli, 2020)
2002) Ct16
(Pinto al. 2024) By CR C3 -C2-1
(Pinto al 2024) bg CB C1-C2-2
(Pino eta 2004) Fay C9 -1-1
2004)
Eq -C -2
Theore 3.2
Ous
Thomm
Figure D.1: Empirical comparison between our generalization results and previous works.
Further Validation of the Low-rank Condition Morcover, the singular value spectra plots from Figure D.6 demonstrates the presence of rank sparsity in our trained models. This confirms the observations made by a multitude of recent papers in the optimization literature (21 27), which further explains why bounds' advantage improves when the width increases. In this example, even the value pr = yields an advantage over classic parameter counting bounds due to the exact low-rank structure.
D.2 Convolutional Neural Networks (CIFAR-10)
35

---

Magnitude
0.8
Magnitude
Magnitude
00
10
20
20
30
40
Index
Index
Index
1= 101/3w=400
1=2/3 w 400
I= 3=333 40000
12
Magnitude
0.
Magnitude
Magnitude
T0
0.
04
00
Index
Index
Index
1/3
2/3
3/3 500
08
Magnitude
Magnitude
2
Magnitude
00
20
20
Index
Index
Index
==1
2/3 w 700
== 3=3/3 700
10
8
Magnitude
Magnitude
Magnitude 2
Index
Index
Index
Figure D.2: Spectral Decay of Intermediary Layers in the MNIST Dataset (Fully Connected).
36

---

D.3 Convolutional Neural Networks (CIFAR-10)
In this section, we present experiments
the CIFAR-10 dataset. We train neural network with convolutional layers with kernel size (3, 3) each followed by 5 fully connected layers. The last (output) layer has width 10 since there are 10 classes, and the width of the intermediary fully connected layers is varied between 100 and 1000. Due to the additional computational burden of the task and the more pronounced overparametrization, we evaluate the bounds on a single trained network for each architecture. To moderate the effect of norm- nam-baseddii factors, we employ spectral regularization, constraining the spectral norms of all weight matrices to We set the margin dynamically to ensure a loss of only 1 percent in accuracy compared to margin of zero, As in the fully connected case, we note that as most of the bounds are asymptotic in nature (and many of the sources do not calculate the explicit constants) their 'practical evaluation' challenging. For this reason, we only evaluate dominant term of each bound (ignoring the constants and logarithmic factors) and we employ a logarithmic scale, which is better suited to this asymptotic analysis since the bounds differ from each other by very large factors. This is also standard practice in the related literature [74 4 I whenever bounds are evaluated. As in the fully connected case, our bounds outperform the competing ones. However, more interesting the fact that our bounds exhibit a milder dependency on the width, which better aligns with the true generalization error.
Widh
Bound (Log Scale)
(Banter at. 2017) lig CHI
(Gulowich Be C5)
(Golowich di 2013) Eig C6
(Galowic at 2018) lig.
(Nayshabur all 201R) Eqg c10
(Long Solghi, Eig C1S
(Graf 2023) Do C16
(Pinto al, 2004) Ey Ca EI CC--
(Pinto al. 2024) Lq CS CI-C--2
(Punto at 2024) Fq. C9-C1-1
(Pinto et. 2004) Fig C9 CI -2
Oua W/O Loss Augmectiiionn Thoumn
Ous
Thence 3.5
Figure D.3: Numerical Comparison of our Bounds with other Bounds from the Literature (CNNs, CIFAR-10).
Furthermore, to provide further evidence of spectral decay and strong approximate low-rank structure in our trained models, we provide the following plots of the singular spectral of the weights of our trained models. The plots confirm that the approximate low-rank structure is stronger for larger widths, which also explains the fact that our bounds' advantage over existing approaches widens in such overparametrization regimes.
We also provide few additional comparisons validate our conclusion that our bounds respond to varying degrees of overparametrization better than pure parameter counting bounds. As mentioned in the main paper, the choice of pe can be made after training, as the bounds hold uniformly over their choice. In fact, the choice of pt made after optimizing the bounds is relevant factor in the interpretation of the bound terms of overparametrization regime: a larger but moderate value of (in the range f0.2, 1]) indicates that the norm-based factors are moderate enough to be involved in the bound and that the low-rank structure in the weight matrices is sufficiently pronounced to be exploited. On the other hand, a value of p O can indicate one of two things: either (1) the nose- factors are too large for the low rank structure to be exploited, or (2) the weight matrices are exactly low-rank. In our experiments, we observe the optimization of the bound often results in the value Pe O being chosen for convolutional layers, whilst the fully connected layers tend to correspond to more moderate values of pe. This can be seen in Figure D.5 below, which corresponds
37

---

=0000
Figure D.4: Illustration of the Spectral Decay of the Trained Models on the Layer fc2.
to the most overparametrized CNN model (w 1000) where the p&s are selected based on optimization of the bounds from Theorem 3.7 (with loss function augmentation).
1.0
0.6
0.4
0.2
convl
conv2
conv3
fc1
fc2
fc3
fc4
fc5
Figure D.5: Chosen Values of pt (with Loss Function Augmentation) for the most Overparametrized CNN Model (width- 1000)
The results somewhat expected: convolutional layers are already quite parameter efficient, making the exploitation of the low-rank structure comparatively less necessary. Furthermore, the norm-based factors arising from the product I are larger since convolutional layers have larger spectral norm due to the repetition over patches. On the other hand, the fully connected layers are able to select larger values of due to more pronounced low-rank structure and moderate norm- norm-based factors achieved through combination of loss function augmentation and spectral regularization during training.
We note that the choice of ps generally introduces tradeoff which is only imperfectly captured by the regime corresponding to the value of Pt chosen when optimizing the bound. Indeed, lower values pe correspond both to bias towards the parameter-counting component of our bounds and stronger exploitation of the approximate low-rank structure (assuming the norm based factors are large). Thus, more moderate values of Pe are preferable terms of the bounds' responsivity to changes in architecture, whilst setting very close to zero can sometimes be beneficial in terms of overall numerical performance due to the convergence to a parameter counting result. To better isolate the bounds' ability to capture low-rank structure and its indirect effect on function class capacity, we evaluate the bounds when fixing value of Pe to various values for all layers. We then compare the behavior of our results from Theorem G.5 (without loss function augmentation, blue) and Theorem
3.7 (with loss function augmentation, turquoise) to the parameter counting baseline of [74] (in yellow). To isolate the behavior as the overparametrization increases, plot the
38

---

ratio between the value of the bounds compared to the value of the same bound for a width of 100. Similarly. we also plot the ratio the test emoor (in red) compared the test error for width of 100 (i.e. 0.2793). The results are in Figure D.6 below.
Eq. C16
(Graf al. 2022)
Ours
Theorem 3.4
Theorem 3.5
Ours
Test Emrr
P
= 0.05
P= 0.11
P 0.16
4,0
Reggie ioverreet
PaLLan inseement
Penaher increreet
ReilEro incroroor
3.0
3.0
3.0
3.0
2.0
2.0
2.0
2.0
13
200
1000
200
600
1000
200
600
1000
600
1000
With
= 0.21
0.26
P 0.32
P 0.37
4.0
4.0
4.0
4.0
Roba increreet
PatLaN Incssmen
Poccste Pecttetteeeeee tecrereee
Paluieu Rulutee Incremiont
3.0
3.0
3.0
2.0
2.0
2.0
10
10
200
1000
200
600
1000
200
600
1000
800
1000
P 0.42
P 0.47
P 0.53
P 0.58
4.0
4.0
4.0
4.0
Relabe Retatelncaeent incement
3.0
PalaaN Incumert
3.0
Pacatt Tactteltcneeet increnent
3.0
Rututeelicrene Increnert
3.0
20
2.0
2.0
100
200
1000
200
600
1000
200
600
1000
200
800
1000
P= 0.63
P= 0.68
P 0.74
P 0.79
4.0
4.0
4.0
4.0
Reaane Pocementt
Retatvel inrenntt
350
3.0
3.0
3.0
20
2.0
2.0
200
1000
200
600
1000
200
600
1000
200
800
1000
P= 0.84
P= 0.89
P 0.95
P=1
4,0
4.0
4.0
Rearn PaaneForrmmet Forament
REMDON mornmmnt
Reaane Ioreeeet inceementt
Relavve horemen
3.0
3.0
3.0
2.0
2.0
200
600
1000
200
600
1000
200
600
1000
200
800
1000
Figure D.6: Relative Growth of our Main Results as Function of Width
We directly observe that for moderate values of pe, both our bounds are successful at capturing the implicit function class restriction that occurs through both norm-based effects and spontancous rank-sparsity in the overparametrized regime: for small widths (100 to 300), the bounds all grow linearly, which correspond to a parameter-counting behavior (indeed, the parameter count grows
quadratically in the width, which results linear growth of the term / N where the number of parameters), at the regime of moderate overparametrriztioon (width 300 to 700), our bounds maintain
39

---

relatively constant behavior, which matches the behavior of the test error. Then, at the extremely overparametrized regime (widths 800 1000). the bounds begin to grow again and exhibit less stable behavior, which also better matches the behavior of the test error compared to the parameter counting baseline, which continues to grow linearly.
E
Generalization Bounds for Fully Connected Networks
In this section, we prove our generalization bounds for classes of neural networks with Schatten quasi norm constraints the weight matrices. For each layer L, we have set of admissible matrices I w 3 B₁ == {A₃ R A| Mellsc.Pe & MMi A & 8e) and
F8 = {FA
And : Ae Be vl & L}
(E.1)
FA F(A ||Ae Melloc Me |e| & st VEELJ.
We define similarly:
FB F0 = (F) = A() A Br 14 [l
(E.2)
where we define
B {AEE R |A Melsc,p sc,pt & MM |Ael < st).
Proposition E.1. Fix some reference/inittalizatinn matrices M E 1gm1XX0 = R xd M" 12"XXwL - Assume also that the inputs IRd satisfy |>|| w.p. 1. Fix set of constraint parameters & Pe 2, st, Mr (for E = l....., L.).
With probability greater than 1 8 over the draw of an i.i.d. training set , NN every neural network Fa(x)= == 4-1 11 (
satisfying the following conditions:
1 - M 1sc,,p & Me
VA M E L
|A| $ 8t
|A] 22 &
(E.3)
also satisfies the following generalization bound:
E(((FA())
1 N
Σ ((FA(z:).
log( N
240 log, (og,(41) (4' log( N)
< 61B+1|
(1 L L1)
ス R.M.s.b.
(E.4)
N
where R.M.,p.b.F
2pr
2pg
PE
Pz 1
Pisk
re
[wew
p(+7 +
b
PiS:
I
PL
W
p1.
(E.5)
:= [b [][LL] +1] IT 1]s, + 11] and we use the shorthands It == min(we, 1) we = [we + wt-1].
Mrd
W. :=
Proof. Write F3 for the class of neural networks satisfying conditions E..3 By Lemma I.7 with
N and Proposition E.11 we have the following bound on the empirical Rademacher complexity of FB
40

---

Rg(LoFF)
BB
(1 I L min(e, 1)
FFF
2p
1.
2Ft
24
96 16lo22( (4
(4
Piši
It 2e+2
W
pr
wi
p2+2 de
N
N
2ng
120 /
loga
L L1) 24p
b
piss
Ie pr
p2+z Pe+?
W
de
B -
VN
N
2re
120 log,
[lg N) +
ve
+
+1 L1) +
PiBi
0i
p2
W
Pc+2
N
VN
(E.6)
Next, by Theorem 1.6 we have w.p. 1
1 E [[(FA(Z), w)
1og(4/0)
I(FA(z)), & <BBV
(E.7)
N
2N
N
Apc
240 log, 41 [og N) + B] (1 + L,)
L
PrSi
re P2
2
N
log( 3)
6|B +1]
2p1
240 log, 4D) log(
[B +1]
Pe+
(1 L,) z
Σ
P
P:8
rg
We
W
where the last inequality holds for N > (if this doesn't hold, inequality
E.4 holds trivially).
Plugging equation E.7 into equation (.6) yields the result from equation (E.4) expected.
Using Proposition E.1 optimized.
we can prove the following post hoc version, where the values of can be
Theorem F.2. With probability greater than 1 - 5, for any b E R+, every trained neural network FA and sampling distribution with |a:|| w.p. satisfy the following generalization gap for all possible values of the pes:
E [(F(A(())
v)
1
Σ
(FFA)))))))
N
log(1/5)
+ O1og
480[B + LL) a V Vlo((rre) log( N)
& 6[B +
+1]
+ 6B
RFA
N
N
VN
2oo 4W + b IT, p.l A:ll] [| log(bb) + L EL_ log(I]Ael) + log(4W))
where
Olog
TFC :- 12 [b I][LL, +1JWN IT [ed] A:ll + 11] [W + +b pa| A.l]. b is priori bound
on the input samples' 2 norm and where
41

---

RFa =
2ng PeT2
L-1
|
Mzlle..p
bpzl|A 2,,0
I
pil Azll
W2
2v v2
|Ael
i=1
L-1
|
+ bps
A2
PillA:l
A 2,00
PZ W
I.
W
Furthermore, the result also holds with b replaced by the empirical quantity b m |
Proof. Let A1, A2 > 0 be positive real numbers to be determined later. For every set of values k(bb, H(Me), klos) and & k((pe) 2 (where 1,..., I.) we apply proposition E. for the
following values of b, k(s)) MesPe, 6:
- b b= exp( ==exp(A ()(((,
(E.8)
8 - St c (L)
(E.9)
Mr - Me š with
(E.10)
πi expl A (
(E.
- - Pe = (gk(
(E.12)
8g0 ,obr))
أA 33L+1
I (6 (k(Me)
(E.13)
This implies that with probability greater than 1 8g00) piMe) gioe)s
N [[(F(()). v\1
log(
110 ((oe) senn wine) wine)
Σ
<6B\
240, logg (4L win log [B) +1]
(1 + L1) 2.r R Reted (orr), (00,,)))
(E.14)
VN Rytee p(m) is defined as the
where
value of se, Me, Pe taking the values defined in equation
Rmapb for Lr00
and
[exp(I<(0)) A) + 17[L + II exp(1( A + +1
Note that
Σ
g0s (oM)) 54
1
2
24+1
2
< 6. (E.15)
331+T
A
2
3
k00 k(e)) (MM (.MM))
iEz
Thus, equation E. 14h holds simultaneously over all admissible values of k(b), k(ss) k(M)) k(pe) with probability
> 1- 6.
For given neural network FA and choice of pas, we utilise the result above for the following values of 1b()), k((s) h(Ms)) k((e):
(()) [og(b)/Ai
(E.16)
k(me) = [log( ($c) L/Ar]
((M))
[log(1 (rz) A1]
k(Pe)
Pt
A2
42

---

where b - max; |ill. |Ael. - | 184-May Mellee. || E. Oi Mo (for l + L)
and IL |A Mells A| 2,00 & VUL E, oi(AL ML
For these values, we certainly have:
[exp(A1)o 1|[L +1JW I [pss exp( +1]
L00 &
(E.17)
< exp(2A1)
[b 1 W IITe: + 1|s; + 11 = exp(2A,)),
(E.18)
because T =
[b + 1]st + 1]]
Further, we have
it T
(E.19)
Note also that
2pt
2pt
2 pcl
& 2 - pel/2 & 2
(E.20)
Pe 2
PE
Pe +
and
2
2
2 pj.
2A,
& 22/
(E.21)
pr +
Pr + 2
[1: + 2] pr + 2]
Thus, we can continue:
Ryin B(ip)),MMM)ppp (10)))
(E.22)
251
L
PC+Z
exp(A,)6
)6 11
p,s; exp exp(ex/pp/) (Ai/L)
p(
0
i
(E.23)
Fr we
exp((11)
Σ
P:8i
12
F.
W
(E.24)
A2/2
201
exp(A1)
b
Pidi
Pesi
11
W.
W
(E.25)
42
L
P(S
A1/2
[Ie
We
P2
2
11
(E.26)
43
2pr
pC
1.54
b
PEs:
b
P.st
re m6+#
W
Pi u242
w
(E.27)
A2
1.54
P:8
W
Σ
P:8;
[re
wig
PETZ m
Pt
(F.28)
1.54,
P:8
W
RFA
(F.29)
(i.As)
4W +
P28;
RFA
(E.30)
43

---

where at equation (E.25) we have used equation (E.20), at equation (E.26) we have used equa-
tion (E.19). at equation (E.77 we have used the trivial fact that P
>>
Pr. and at equation (.28
P
p+pe
we have used equation
E.21 and the fact that re & We.
Equation (E.30) motivates the choice
log(2) log 4W + b b11: pi8i
A
D2
(E.31)
which ensures that
ReMM ginp 100, kood & 2R
(E.32)
Note that for this choice of A and A2, can write first (from equation [7.17).
LEm & I4
4W + II Aell
(E.33)
and then:
log (410),Atee) peme) (A0))
< log( + [3L + 1] log())) +
|1:00| + E1st00)
Σ naLMoy
+ L Log((1A2))
< 1oog(²) 1
+
4.3 + log log
4W + b I[[Dis pisi
+ |A:00) + Σ
|x(0e||| + Σ
(E.34)
1
< log(
{ +
4.3 + log log
4W + 6 IT Aell
+
(E.35)
+
log(bb)| +
Σ log(1 Ael)
(
A
(E.36)
< log( 1
() +
4.3 + log
4W + I[ Aell
+2
(E.37)
L
2 2og
4W [ pell Aell
[lg(bb) + L
Σ
log(1 Ael) + log W
1 < log( x + + 2og
4W + I psl Aell
[lo((b) +
Σ
1
log (Og( Ae/) + log(4W)
log( )) 8) 2 O1og
(E.38)
where at equation (E.34) have used the definition of Ag (i.e. equation (E.11) and the fact
log( (g(())(2)) > 1, at equation (E.36) we have used equations (E.16) and at equation (.37) we have used the fact that log(2) > z and the inequality log log(x) log(x) and at equation E.38 have used the definition of G1og-
We now plug equations
E.30
B.32
E.38
and
E.33 into equation
E.14 obtain:
44

---

log(
4
400, (000 NiMe) wir))
B ([ 5)1 N Σ I(FA(z)),))) 3n) & 6|B +[
N
240, 1og2 (2Lmo) (00) log (Bg()((B+]))) +1]
(1 + L1) .f R (ooke) (n b00))
VN
log (1/8)
12 Olog
6[B 66/++11 +11 <
+ 6 +
N
N
1og2 (81 4W + b bll, p: log(N)
480 + L
RFA
(E.39)
log (1/6)
2 + Olog
< 6|l + +11
N + G|B + -1V
+ 480 B(1 LL)
N
19g(12 [b + 1][LL] + N
Ii=,lTe + 1ss; 17
[4W + bl1. Pol Polleel]) log( (N)
RFA
N
log [1/6]
2 + Olog
< B| +11
+ B| + 11V
N
N
480 B(1 + L LL) ,.p v log((FF) log(N)
RE
(E.40)
N
where at line E.39) we have used equation E.32 and at the last line we have used the definition
TFC 12 6b + 1 +1JWN N
[ +1
4W
61 p: 1
6
i=1
This concludes the proof of the first statement.
For the second statement, suffices to use an elementary form loss function augmentation by considering the following augmented loss for any value of greater than 1: ('(x, y) max(1(FA(z)) y). 1B [=][>)))- Indeed, given any training set 21,..., Ey (not necessarily satisfy- ing [rs]| & b). we can apply Proposition[E:. F1 the training set (ar; || & b). which results in cover of l' FB with respect to the whole set {x,) since l' B whenever ||x.]] > b. The cover is
bounded above by the RHS of equation [E.13I) and we can continue the argument as in the proof
above and conclude that
N
((((F())) N
Σ ((FA()))))
(E.41)
where Q is the right hand side of equation E.40 Note that the argument above already uses a posthoc argument to show that the bound holds for all values of b simultaneously with single failure probability. Thus, the same true for equation (E.4I). Note that it is not necessary for to be Lipschitz in the input x, since cover of input space required.
Next, we have:
1 N
E[(FA(#),u) w)]
Σ
I(FA(:)).))
N
<E(((FA())))) 9) N
Σ
I(FA(z)) vi)
(E.42)
1
Q
((Fx(1)))
1 (FFa)
(E.43)
N
Q
(E.44)
45

---

where at the second line E.42 we have used the fact that 1' > 1, at the third line (E.43 we have used equation (E.4T) and the fourth line (E.44) we have used the fact that b max, [ This completes the proof.
E.1 Tighter Results with Loss Function Augmentation
In this section, we use the technique of Loss Function Augmentation to improve the scaling of bound with respect to norm based quantities.
We first recall the following definition of the ramp loss (defined for any B). which we use in controlling the intermediary activations of the neural network:
AB( min(B (x
B)+ B)
(E.45)
We now consider the following augmented loss function:
laug( 2F == max
max (=L-1
Ab,
(1)) B1
(E.46)
We first prove the following extension of Lemma E.12 to incorporate the loss function augmentation over activations.
Lemma E.3. Assume St 32 and let by (for 0, 1......,I L) be some positive real numbers with
by = Lt. Define PE supazt Pu.u/bu where before, PI Pt Im=1+1 Smpm-
Assume as in Lemma E.12 that we have fixed dataset Ii,..., with |x,|| & bo for all i & N. Let Bi.... By, be arbitrary subsets of the spaces gwexxee- and instantiate the rest of the notations bet.
from Lemmal E.12 and explicitly set Ee
T.pi
There exist covers C1 BI....,Co-L = (AI, AL) E B1 x ....BB.... there exist A ,..., A such that for all & & A 10-1.
B1 x ... ......... Be.... CL B1 ... BL such that for all
(A1 ...,...,A4.
Ab) Co-- and for all i & N, N. & L:
Dang (FAs Fz, y) >ang (F Fi, v), E e.
(E.47)
Furthermore the covers satisfy the following covering mumber bound:
log((Co-21) &
log(NNo, Ee, N, 3b)-
(E.48)
where as before, for any 5 > 0 and N E N, e (,, is defined as the minimum number N such that for any dataset _ f-1 .....
2' 1-1 with N < N and a 'le & b for all < N, where
I|-lle = for E * L and ||-11 ||
Proof. The proof quite similar to the proof of Proposition 8 in 42 itself inspired from 74 16
We will construct the covers such that they satisfy the following claim:
Claim 1: There exists a cover Co--1 satisfying equation (E.48) such that for any A = (A...., A B, ... Br, there exists a A ..... AL such that for each x X and each & L, one the following two conditions is satisfied:
bl < e, F 14 An
14 (x)
F At.... A an (2) cepe
(E.49)
or there exists é < such that
10-6 A A4 (x)lle 3bb
(E.50)
46

---

(Here as usual I-le= = ll-1l2 if e * L and ||-| = 1.1loo).
Proof of Claim I:
For the first layer, writing X :- (.1,... ............... .... we know by assumption that there exists cover (x(X) Co-1 c B1 such that for all A B1 there exists A1 Ci (Xo) such that for all i & N,
I(A (x4)l & c1
(E.51)
from which it also follows that
(x1) -F (21)) = (A ( -
( (A(A)( CIPI-
(E.52)
It follows that (FATT) A E Bi} c FB is an - cover of Fg as required: equation E.49 holds for t=
For the inductive case:
Assume that the covers Co Co have been constructed and satisfy the claim up to and including layer For each element A0-L of Co-se, we can split the dataset X into two sets Xe, = X and [X [Xe, as follows:
XLAA0- = xE X: A4 & sl:10a- A... (ox)ll & 3ber.
x
(E.53)
Next, by the definition of N ce, N, 3bc-1), there exists cover 1, C Bet1 such that for any A E Be+1, there exists A E C₁ such that for any x Xe.5o.es
LA Flone (
A Foof &
(E.54)
Accordingly, we define the cover
Co-e11=
U Ao sce,
(A-1) Ce-1.5o-1..
(E.55)
For any 10-41 (A', A E B x BE+1, the associated cover element 70-2+1
A²) is the cover element of Co associated to is defined by " A A where (A' (A'
(A (A',.... A.) defined by the induction hypothesis, and A the cover element of Ce+1 associated to A by the definition of ( e,, N, 3b.-1) to satisfy Condition (F.54).
Equation (E.54) implies that for any Xg, condition (E.49 holds for the value f = l. In addition, we already know from the induction hypothesis that the same condition holds for E E. Therefore, the condition holds for all L < f + for all x E Xx Furthermore, by definition of Xe,4r-e, any x E [Xe, has to satisfy equation (E.50) for some ε < l 1. Thus, every & X indeed satisfies either condition (E.49) or condition (E50 as desired.
This concludes the proof the claim.
To finish the proof of the lemma, it only remains to prove equation E.47 B1 x ... Br, and the associated cover element (A), A?..... A²).
Consider arbitrary
Let x e be an arbitrary sample. Let 8* be the smallest number less than such that
1 ge (x)le 36,-
(E.56)
and let 8* if the above equation doesn't 't hold for any value of L.
47

---

By instantiating the claim for any l < 8*, we know that equation E.49 holds for all & < L. Thus,
Abc
A (x)]]) >b, (x)))
(E.57)
1
1 (0) = (x)]
(E.58)
1
F F
A 2o A (x.))(()) (.(1)....a
F
a0 A'... ,44 (z)
(E.59)
bt =1
1
t/
(E.60)
be
1
c
PEi-l
(E.61)
be
Lppes
1
bb Pe. oe & EC
(E.62)
b Lpe,
where at equation (.60) we have used the claim, at line EE.6 we have used the definition of ct, and at line (..62 we have used the definition of Peg.
In particular, it certainly follows that l & I 1,
[ (x) > (x) - 11.1/
- (x)] > 3b; by = 2b, (E.63)
which implies that Aaug FA v) Aangl (F A Fr, y) other hand, 6 L, then since by. = 1/ L1, equation (E.62) instantiated for & = L also shows that
0 and equation (E.47 indeed holds. On the
[(FA(z)) - (=) c
(E.64)
whilst [.62) instantiated for any & L 1 also shows that
max FEL
Ao, (1 (x)I)) (1FF2-()))))
max (=))( <
(E.65)
Together, equations (E.44] and
E.65 imply that equation (E.47) holds, as expected.
Proposition F.4. For any granularity > IV and any values of1 & by,,.. bs.-1, 1, 8t, Pe, there exists cover of the augmented loss class (Naug (FA, v) A (Al ,..., A B1 B1} with cardinality bounded as follows:
2pc pc
L(1 Li) min(e, 1)
2-p
log (IC)) < 288 (4g)(4))
b
SiPi
Tt M2
W W
(E.66)
Proof. The proof is analogous to that of proposition E.
and consists in plugging in the one layer
covering number estimates (Propositions (F.4) and F22 into equation (E.48), taking into account our new definition of c, = bre.
Lpe
log (ICI)
N, 3b)
2-1
L-1
Me bo-
2rc ve12
& 72
W
PET
lT xF,e)
(E.67)
2PL
Mr b
P1.
+
W.
PL
wT
PL
log, (T (T Fp,,1)
(E.68)
61
48

---

Note also that since we are assuming that > 1 for all l and by > 1 for all & * L, we also hec
have E, = Lei
> EPe-L, thus, the bounds on the logarithmic factors 1T ,L. I Fyy,e derived in
equations E.141
still hold. Thus, we can continue:
201
Mebe-1
PE+2
log (IC)) 72 loga
E
(F.69)
C
2ny
Me be 1pc T. + [T]]
PE+2
11- Sift
< log, (T)
W /
Pt
(E.70)
c
2p1
L(1 L1) min(e 1)
2p 2+7
M
Pr42
< 72 (0gg2((T)
b--
stPi
W
12
Wi
(E.71)
88
i=(
L(1 + Ln) min(e, e, 1)
L
Pt
= 288 (ogg((1))
bg
SiPs
Pe
W
42
Pr W
(E.72)
1=1
1=1
as expected.
Then, we can proceed with the following straightforward analogue of Proposition E.1
Proposition E.S. Fix some reference/nittilliaaion matrices M E Rum x R ML R" Kwz- PC Assume also that the inputs x E IR satisfy | & b w.p. 1. Fix a set of constraint parameters & pt v 2,1 & Me (for f 1,.., L). Also fix some numbers b,,-1 and by. = +.
1 b,,,..,,,,,.
TNN. With probability greater than over the draw of an i.i.d. training set I1,... NN, every neural network F FZ)) = A 1- (1)(t)))... satisfying the following conditions:
||
M sc,pt & Me
||| < 8t
| 12,,000 & 82
(E.73)
FF (x))l < be,
L- ViEN
(E.74)
also satisfies the following generalization bound:
1
E[(FA(=).))]
((FA(=:).)) ys)
N
log(
416 log, (4l) log( [B] +1]
<
+1
[L( Li)] M.s.
(B.75)
N
where R.M...p.
2rt pp-2
Pigi
r veTz
wi
Pt
2 [w]
vetz + (1r.-1P9)
re P2
w
PL
w
PL
Pr.
(E.76)
and as usual, r = [B- + llx + 1]s; + 1]] and we use the shorthands vę =
M. see W. == min(we, wt-1), We = [w + w1-1
Proof. We first note that with calculation nearly identical to that of the proof of Proposition E. relying Proposition E.4 instead of Proposition E.11 with additional factor of v3 and (1 L L1)
49

---

replaced by L(1 L1) as well as 6 6 Sip; replaced by b IT S,P1, we obtain the following bound on the augmented loss class Xaugi
N Xan FA, Fig 9:)
E Daug (A. ..2,
N
log( (
832 v log, 41 log (N) [B) [B+1]
< <b + +1I
[L(1 + L1) RMappr
(E.77)
N
VN
However, we know by definition of Aang that
E (aaug (A, EI(FA(a),y).
(E.78)
Furthermore, since the last condition in E.73 holds, we certainly also have:
Yaug F Fi,
N I(FA())),
(F.79)
N
The result now follows.
We can now apply the above results to obtain a post hoc version using argument similar to those used the proof of Theorem E.2
Theorem E.6. With probability greater than 6, for any b E R+ every trained neural network FA satisfies the following generalization gap for all possible values of the pes:
1 Σ I(FA(x:). [[((F(=)) N
(E.80)
log(1/0) 6B 6B\
1.5 + O
Nane
6[B 11
N
832|B +1][1(1 LJJ 24p V log(TFc) log(N) NN)
R RA.dou
N
where Aaauz log
2 log
4W + 6 I[ pull
[og(b)] Σ log [|||Ae)))
Σ
log (B..) log(4W)
= 12 [b 1][LI, + +1JW +IWNN Ael + 11] [W + IT. p:ll Ar1], b max;
TFC
and where
RA.ddau
(E.81)
2pt
|A
Me PPc
B Be-1.PPL/AATle. 2,,00
II
Ail
Ae
W P1+Z
W
Pt Pp#2
(E.82)
i=1
2x PL
|AL Milkep
Pt F2
+ +[BL-IAPL/147 12,00
1
2
F1 L
W
L
(E.83)
where B,-1AA max (maxiaN FAA..... (1:)),.)..
Proof. Let A1, A2 0 be positive real numbers to be determined later. For every set of values k(b), kibe), k(MM), k((ee) Z and 0 & k(pe)
2. Az (where é 1, I,..., L) apply proposition E.11
50

---

for the following values of b, k(st), Me, Pe, d:
b - = exp( 111101)
(E.84)
bq by exp( A (h(ht)))
$s - St = exp (1 LL)
Me M ii?? with
ÿt = exp( (ap(AiAlMm))
Pe - Pt == Agk(pe)
J 34L+1
1
16.00) E-E, (1(0))) |-E I (u(Me)
(F.85)
Using Proposition E.5 this implies that with probability greater than 1 - S (he)), wlre) vim)) w(m)) (re))
log( (00) wine) clMe))
E E[((F(I)),))
Σ (FF((I)). < <B
N
416, 1ogg (4T log( [)
[L(1 L)) Ritee wime 1009 wloe)
(E.86)
VN
ReOOs, wie,) go0e) g(Me) pire) is defined as the value of Rmapp b. be, 8t, Me,Pe taking the values defined in equations E.84 and D00 [exp((<())) A) + 1J[L + lxx A) +1]
where
for
Note that
2
Σ 1:00 100 (ole) p
6g0s, (00e) glee) (lMe)) 822
36+1
$ 8.
342+1
A₂
2
iE2
(E.87)
Thus, equation (E.6 holds simultaneously over all k:(b), g(bbe) kee)) k(Me), k(de) with probability 1-8. 8.
admissible
values
of
For a given neural network FA and choice of p.s, we utilise the result above for the following values of (00), k(o0), b(MM)), I(Pe);
(0) (lg(b)/Ai)
(E.88)
((bb)) (Be,a)/Ar]
(E.89)
(+c) [lg((s) L/Aii1
(M,) = [og(rz)/A> Ail
(Pe)) Pe
A2
where b max, || by Br,A, 82 || re |A Mellii /|pps oi - -
(for T.) and rt. |A Mz
Al
PL
& ywr Σ, ( P2))
As in the case of Theorem E.2 the following equation still holds as it doesn't involve k(be) (cf. Eq. E..77)
[exp(A1)b 1] + +1JW i Jai exp(A1/T)) +1]
(F.90)
<exp(2A1)
b 1 +IJWN [os + 1]s: 1] expp22A)]
(E.91)
51

---

because I [|LLL+IJWA +I Ul. + 1]s, 11
For the same reason, we still have (cf.
equations
E. 1.19
(E.20) and E.21
8e & Te
(F.92)
2pt
2pt
2 pel
& 2 - pol/2 2
(E.93)
Pe + 2
PE 2
Pe +
and
2
2
2 L0e + 21 +
2 pt]
< 22/2.
(E.94)
Pr +
DE + 2
4
Thus, plugging in the new values of k(1h),k kbbb)), klre), b(Me), k(Px) into the definition of M.s.p
El [b - pisi] 3p, pit2 It p6-2 w petz me+3
we
now obtain:
Ry,00, _,00), p,lee), ((Me)) (.MM)),a(r)) (APP))
(E.95)
L exp( (xp(A1)br-. 11
PF12
pis exp(A1/L)
W
W
(E.96)
I
9
[b exp A1)
pols: exp(e11(11))
W
+2
(E.97)
i=!
2fr
PET
< (exp(Ai)
Σ
bi-1
Pi8i
PETT
W1
W
(E.98)
imf.
2Ft
L.
P1
A [e)p(A1)]
b0
b
71
12
4
W
(E.99)
i=1
42
2 F2
exp(A1)
b
P5Si
be-1
P(S
879 +
1
+2
(E.
1=1
42
Up PC
L
L
P&s
A1/2
b
Pis.
[Iee thg
12
20
(E.101)
i=f
PE
e 155
b
Pi8i
Pe
Wi
F7
W
~ ve-
(E.102)
i-f
Ag
2z1 Pe12
15A1
P::;
W/
by-1
Pi8i
[re wyp
गミंス i7
(E.103)
44
e 1.5
P::;
W1
R FA.Naug
(E.1
max AAn A2)
4W +
R RA
(E. 105)
where at equation (..9 we have used equation E.93 at equation 100p we have used the fact that be & = P:S; (differently from the proof of Theorem E.2 The rest of the calculation is analogous
52

---

to the proof of Theorem E.2 at equation (E.10T) we have used equation (E.92) at equation (E. 102
we have used the trivial fact that Pr.
Pr.
and at equation (0.103) we have used equation E.94
pc-2
24p
and the fact that ry & Wz.
Thus, since the multiplicative error is unchanged, we proceed, in the proof of Theorem E.2 to set
1og(2) log 4W b I1, P:Si
A = A
(E.106)
ensuring
MMMM JiMo 100) wo,) & FR
(E.107)
Similarly, as before, we can write first (from equation E.90
P4
4W + II Pill Aell
(E.108)
and then:
log
(E.
(og(z) 1 + [14 + 1++11]1 (3)) + |k:00| Σ [A:coo)) + Σ [k:0ro) + Σ [klmeny)
< log(
+ L. log( 1/
(E.110)
<log(>) - + L 5.5 log log
4W +
(E.111)
[1:00|
Σ [ Σ |k((be|| Σ lacMoo)
+
(E.112)
<log( 1
8
L
5.5 log log
4W b b1 pil Pell
1.5
(E.113)
[og((b) + L
Σ log(1 Aell)
log(Be,a)) + log(W)
AA
(E.114)
log( 1
8)
L
5.5 log
4W + I Pol Ael
+.5
(E.115)
log
4W 1) [[ [alllA Aell
log(()) L
log(1 Al
log( (B,A) log(W)) (W)
< log( )
+ 1.5+
(E.116)
2 log
4W 6 I pill
[og(b)) + L
Σ (ee(() + log( Be,a) + log 4W)
= loog(
) + 1.5 + Aann
(E.117)
where at equation (1. we have used the definition of A (i.e. equation ( (E.10)) and the fact that log(log(2)) - 1, at equation (E.114) we have used equations (E.88) and at equation (E.115)
53

---

have used the fact that (2g(2) > and the inequality log log(2) < (zg( at equation 11.116 we
have used the fact that 4 log () 2 5.5, and at equation (E.117) we have used the definition of θ
Anng log
We now plug equations EE.05
E.107
EE.17 and E 108 into equation E.86) to obtain:
N Σ
log( (16) p(re), (MM)) ((r))
E ((((A())))))
(FA():), vi) E 6[
832 1og2(22 (2T k(8) ((0))) log [N][++1]
[L(1 L1) / Recor mon wor (o0
More)
(E.118)
N
log(1/0) N
1.5 + 10gg
x 6[B +11
+ 6[B 6[ +1
(E.119)
N
832 B L[ L:)] 25p logz( (8r 4W bII, P.llAel)) log(NN
RFA.NaN
(E.120)
log(1/0) N
1.5 + Olog
$ 6[B + 11
+ 6[B + 11
832 B[ + L,]] [
(E.121)
N
log(12 12
1][LL, + +1
[T: + 1]s, + 11 4W + blI,, p:ll log(N)
R Aane
N
(E.122)
log(1/5 (10)
1.5 + Olog
< 6[B + +1l
+ + +6/++1V 11V
(E.
N
N
+ 832 B[L(1 + L)] Vlog(Trc) log(N)
R
Paidaus?
124)
N
where at line E.120 we have used equation
EE 107 and at the last line we have used the definition
TFC == 12 [b I +1W
I [Al + 11
4W + b I Pa A,l
This concludes the proof.
E.2 The Case pr = for all
We note that both of the above results hold for all values of the prs, including O. However, the fact that Theorem E.2 posthoe with respect all combinations of values of pr introduces an additional
term
La In this subsection, we show that this can be avoided with more dedicated proof for N
the case ps-
0.
We first note the following immediate corollary of Proposition E.
Proposition E.7. Instate the assumptions of Proposition E.1 and assume additionally that pt 0
for all With probability at least 1 over the draw of the training set,
([((F(=).
1 N
Σ ((FA())))))
1og(
240 log, (4))
log( (B) +1]
6|
+1I
Σ we + we-1lee
(E.125)
VN
where 7q is an priori upper bound on vank(A.).
54

---

Next, we consider the following post hoc version.
Theorem E.8. W.p. e - 6 over the draw of the training every neural network satisfies:
1
E (IFA(()), v)
Σ
(FF((z)).))
N
1=1
< 6| + +111
log(?)
240
log R) log [ +1]
Σ
we + wy- uranklran(AAl
N
VN
log(4/6) + log
[ + 2] [ (1Aa] 2) + Llog(W)
N
where TR [23
+] ll + A 2] 1].
We apply Proposition E.7 setting
Proof.
simultaneously for all the values of b, se N+ and ng [W] after
6b,51.f2
(E.126)
[b+ 1[2 1,2W
Note that
8W [ /6 1 1+
Σ
80
(E.127)
WL
beN FyEN W
Thus, inequality (E.125) holds simultaneously over all values of b, 85 E N_ and Fz W probability 8 with the loss function replaced by lang as in the proof of Theorem E.2
with failure
We apply this to 85
Aell. b [2]. ft rank(A9) This immediately yields
N
[[(FA(T), v)1
Σ
(FA(T.))
N
log( 0b,
240
loga
41 R) log( [B) +1]
G| +1J1 &
Σ
w + Irank (At)
N
VN
(E.128)
where
Ta &
[b + 1][[ + 1]WN
[[o: +1ss; + +1]
==1
< [ 2][ +1JWN
[[los + A + +2] 1J.
1=1
Next, we note that
log( ōb.
& log(4/0) + 2og
[ + 2]
I (I + 2) + Llog(W).
(E.129)
[=1
Plugging this back into equation E. 1.128 yields the result as expected.
55

---

E.3 Covering Number Bound for Fully Connected Networks
In this subsection, we use the results of Section to construct covering number bound for the class of fully connected neural networks. First, we briefly recall the following definitions.
Definition E.9 (Covering number). Let V < I= and || be norm in I". The covering number w.r.t. |l. denoted by eV, D) the minimum cardinality m of a collection of vectors v v'...., v E R such that se mmnj-1....m | v < In particular. if J c. R* is function class and X (21, (01, ; ,In) E X are data points, ((F((), (1/ n) [l2) is the minimum cardinality m of a collection of functions F .!.................. fT :X' R such that for any f E F, there e Similarly, (FF((X) e, || Il is the minimum cardinality of collection of functions F fl. ,'.,... X R such that for any E F, there exists j & m such that i & n, [f(z)) f(z:) E
exists & m such that (1/n( (x+) f(x))
Definition E.10. Let F be a class of real-valued functions with range X. Let also $ = (i1, T2, ................................ .......) X be n samples from the domain of the functions in F. The empirical Rademacher complexity (F) of F with respect to 21, T2.
is defined by
Rs(F) == Es sup feF
Σ 8.f()))
(E.130)
where 5 = (6), 62.... .........,.... k,) E [+1)a is a set of n iid Rademacher random variables (which take values 1 or with probability 0.5 each).
We now have the following result on the covering number of the class FB.
Proposition E.11. let .1,..., IN E Rd be an arbitrary set of inputs satisfying | < b for all i. We have the following bound on the 1 covering number of the class Fs for any granularity 1 E:
log (Nac(l
201
(1+ LL) min(e,1)
2p 2tp
Pr+2
Mr
pr
< 22llog((T) (T)
Pi8i
W
42
W
8pPe
2pe
(1+ + L L1) min(E,)
2+p
Pt ve
x (96log2(4D)
PiSi
rt veTZ
PE
1
(E.131)
where p maxe(pe), we min(ws, w)-1), Wz [we wz-1].
Mr
and
se
we [wewe] if l # wy = L. Here we also have r 128I and r [bb 1J[LLL+ N 11 lllp + 1Js; 11 where W max We
Before proving Proposition 11 we will need the following Lemma, which we will later apply to the following choice: B, (Ae E ge x A Mellsc,pe & Me; |[gl] & se}.
Lemma E.12. Let 61,..., eL 0 be some arbitrary positive real numbers, and assume we have fixed dataset Ii,-.. IN with |a,||| & for all & N. Let BI....,BB Br. be arbitrary subsets of the spaces R W
There exist covers Ci Bi...., Co-st = Bi ... Bu..,, Cr. B, ... Br, such that for all (Ai...,,A) Ar. E Bi .I, there exist A A AL such that for all & & L, A
BI.
(Ā). ....., A²) Co-sE and for all & N,
10- P (x
A A (xx)))
Eppt
if l
F0-L
p0-t
(24))
EPpL-L
(E.132)
Here Pi,-12 == P6i 1e PESE where po 1 by convention.
56

---

Furthermore the covers satisfy the following covering mumber bound:
log((Co-x11) $
IBe ce, N, bpo--e--)),
(E.133)
where for any b > and N e. N n0 (B,, Cg. N, b) is defined the minimum number N such that for any dataset ø f-1
FN ...., with N N and o lle < for all i N. where ||-lee I-
+ L and -1112 1-
Proof. The proof consists in stringing together the covering numbers of each individual layer with arguments analogous to those in the comparable literature on generalization bounds for neural networks [ 16 74).
For the first layer, writing X :- (-1,---, "01,...,2NN), know by assumption that there exists cover (x() = Co-1 c: B1 such that for all A E B1 there exists a Ai E (Xoo) such that for all i & N,
KA A (z;)) E c1.
(E.134)
from which it also follows that
| (21) (01)- - (x1)l ||r,(A');) 0n (A:(())) & 61p1
(E.135)
follows that ( A B1} TB is 1 cover of Fg required: equation E.132 holds for é = 1.
For the inductive case:
Assume that the covers Co-1,..., have been constructed and satisfy equation (E. 132 For each element - of Cu- we have
(Ffof & Po--b.
Thus, we can construct cover Ce+1 (x-((()) Be+1 such that for all A B2+1 there exists a A E Bi-1 such that for all i & N, we have
00-+1
A - p0-8+1 "*. (enn Ee+1
(E.136)
and
log (ICe+1 (x)))) (Be N.ppoee))
(E.137)
now construct the cover
Co-et1:-
(F
(F.138)
Ao AE-
For any A ..... for all & N.
....,,At]. A++1, by the induction hypothesis
there exists (A), ....... A²) E Co- such that
F A
A F ( (x:)
Thus we have
p0-++1 1-141 (I:) (x:)]
den A A'....AtI1
10-611 14: (I:))
po-lt1
2e11 (2:)) + 10--441
Aen
(00))---44 po-e+1
121 (x:)
At Almnn
P Flmel
Ar Flol
Te (x:)) + petsl (A A (+
E+1
< p1+185+1 Σ apt Pe+1Ce+1 P141C411
4
10 f the theorem proved, assume E L in which case ||+ |+|
57

---

as expected. Furthermore, by construction (E.138).
the cardinality of Co-e+1 certainly satisfies:
Co--4+1 & (Co-el (B bpo-e+1)
(o
1=1
8+1
I (B,
[-1
where the last line we have used the induction hypothesis.
We can now proceed with the Proof of Proposition E.11
Proof of Proposition E. For any choice of 61, C,, by Lemma know that oFF admits an L cover with granularity Σl Eepe-L and cardinality
log (ICI)
(og N, bpoo-)))
(E.139)
Let us denote Wg
We min(w;, (Wy, w and we further define Wj Wr if L ==1 L.
[wy + we we- 1l.
[wswe]] if a L
Further, by Propositions (.4) (for l L) and F2 (for layer l L), further continue from equation EE.139) as follows:
log (ICI)
x
ce, N, bpo-e-1))
L-1
Mr bpo 1-1
3p1 ve12
< 24
Σ
W
[
(Tg2(TxPFe)
3p
Mi. bpo
FL
W1
11
xx
logz (T (F,L)
CL
2p
2p
< 24log.((T) (T)
Me -e-
P2
Wi
de W
+
ML bpo-
PI.
W 1
1
21
-2
e7
2pr
Me 6
92#2
<24log,(1)
w
Pr
W
(E. 140)
10fMiPe II PLo. + + [
where
Fy
+7 WºN
F
16[M PL +1][b1I 1][++ we ez s2 +w +7 Wr,N (indeed, note that since
|A & Sr. we certainly have |A & wrs1)). Next, we upper bound the logarithmic factors arising from "p,e and Ff L follows:
M 64[max, .55
1][b 1 1]s; 1 [ 1]
max T FP.e &
+7 WN
min(1,e)
L
<
128
[Ip + 1]s: + 1] [][L, L. + N2
F 128T
(E.141)
[=1
where T = [b + l][LL +IWN 11s, + 11] and we have used the fact that
Mr max; s/Pt
& W WWL.
58

---

We now set = até are that the granularity of the cover C is
for some such that Σe at
Lt Note that this ensures
PE-L e1 sp..
L
C=L
Σ
age
Pe
E.
(E. 142)
Pe-t.
Then, we can plug in the value of & into equation
E. 140 to obtain:
Me -po-t-1
log ([C)) & 24 log
PE+Z
W
2pc
Me bebITi PES.
Pe
< 24 (og22((
88
W
E0E
Me bebll Prsi
PC-2
< 24 10g2
W
P1+2
Wi
42+3
< (T)
(1+ LL) min(e, 1)
2+P
2P
Σ
Pisi
Pe+
2p1
MM
vita
W
W2 p2#2
(E. 143)
8yPt
where at the last line, have (tg
I
F
Covering Numbers for Linear Maps with Schatten Quasi-norm Constraints (One Layer Case)
In this section, we prove covering number bounds for classes linear maps with bounded Schatten quasi norms, which corresponds the layer case in analysis. Thus, the results in this section form the basic ingredient used for the proofs in all other sections. To achieve this, we begin with the following parameter counting argument to bound the complexity of low rank matrices. Proposition F.I is known, but we reproduce the proof for completeness. The other results in this section are original the best of our knowledge.
Proposition F.1 (Cf. [28] (Lemma DI page 30), cf. also 90 91]). Let E,,s denote the set
{A E Rmxd rank(A) < r, |A]o & s). There exists cover C Ers with respect the spec-
tral norm such that
1+ 6s = ([m+drrr)
log (IC) < [m + drrlog
(F.1)
Proof. First, note that every matrix A εr,, can be written A WVT for W Rm V e Bdxr with Wi & / and [V| & v8. Then, by Lemma (L44,, there are c/2 covers C, and C, of the balls of radius / in mmxr and Rdxr (w.rt. the spectral norm) with cardinalities
6s
log ([G)) & [mr]] log
+
c
6s
log (Ic+)) [dr] log
+
(F22
Let A WVT E Ers, we define - WVT where W (resp. V) is the cover element in G (resp. C,) associated to W (resp. V). By definition of the covers via Lemma we have
I - W Wo. VV Vla & 2/8
(F.3
59

---

Using this, we certainly have
|A - All- IWV - 1b
IW(V V']llo -OWW-W-V
[V - -V') + I-W -
2/8 </2/
2/8 =
(F.4)
Thus, C {A m
WV We e G. V C.} is a valid cover of &ns w.r.t. the spectral
norm. Furthermore, by equations F2 we certainly have
log (lc) < log (|C1) + log (IC.))
(F.5)
1 1 68
< Im + drr
(F.6)
as expected.
Proposition F.2 ( cover of FP) ) Consider the matrices with bounded Schatten
:- follows: -= (
Rmxd 12 M 1 & MM =rss;1121 & s (where M is a fixed reference
matrix), viewed as linear maps from Rd I and assume as usual that we have training UN
Ei,...,,NN E R such that ||ae||| & foor all i & N.
There exists cover C c FT such that for all Z E FP, there exists a Z C such that for all & N. we have
I1( Z)zillo0 EE
(F.7)
and
3p n+2
Mbb
log ([C)) 24
[m d] p+z min(m, d) z&p loga (Txp)
2p 2
C 24
[m + d] [ pfa logz (Tzr),
where Fp : [6[]M +1][0+ [[o++[][[+[[mm
m.N.
cP42
Remark F.3. Note that in particular, the proposition holds for p O, replacing M with constraint on the rank. In that case, the proposition follows immediately from Proposition F.1 Furthermore, also follows from the limiting case
O. This is only true thanks to careful management of the logarithmic factor Fyy indeed, in addition to the constraint |Z & MM, we also independently require the constraint |Z|| < s. This second constraint is only necessary to maintain good scaling as p 0. Indeed, could have bounded |Z|| via 7 1 & M. However, this would result in a factor of M (without an exponent of p) inside the logarithmic term, making the bound blow up at rate of 1/p p O. To this, note that as p 0,
log([[Z]ssc.p) log(1 Z I O( loggrrank( (]) 00.
(F.8)
p
p
Proof. The proof relies on the general "parametric interpolation" technique developed in (8 After simple translation argument, threshold to be determined later. We first prove the following claim:
assume without loss of generality that M 0. Let be
Claim 1: Any matrix Z F. can be decomposed into sum Zi Z2 where Z₁ E,. and Za FM, where ri M and M₂² 72 min(m,d) d).
Proof of Claim 1:
Let P1.... dmi denote the singular values of Z, so that that the singular value decomposition
of Z is Z Le Py U.wn for some unit vectors un R and wp RRd.
Let T = max (k Pk 7) and write Zi ERST PN Tinaa and Ze Z Zi EKST Pk Ukw
60

---

Note that by Markov's inequality, since / sc,p < MM, we have that rank Z1) & T & M Furthermore, we clearly have || P1 Next, it is clear that
72
Z & 1 sc.p & M. Thus, Z1 E & as expected.
min(m.d)
Z2
Σ p E min(m,d) d).
(F.9)
k-T+1
Thus, Z2 M2 expected, which concludes the proof of the claim.
Thus, it follows that for any choice of and gramularity e, we can apply Propositions F.1 and I.3 to obtain e/2 covers C1 = EM and C2 E FM,, such that for any Z1 E EI, and for any Z2 E F M2 there exist Zi C₁ and Zg C2 such that for all N. [1 Zi)xill & e/2 and (1Z22-2)xxille & <//2. is then clear that for any Z E FT, the element Z = Zi+ Z2 E & + satisfies [2 2) & e. Thus, C = C1 + C2 is the required cover of FP (which satisfies
inequality F.7 and by Propositions F.1 (with
c/(2)) since the required granularity c/2 and Proposition gives a cover w.r.t the spectral norm) and I.3 (with e t e/2) its cardinality satisfies:
log (IC)) x log (IC]l)
log (|C2l)
12bs
144 M4 ba
16.22
< mm + d] ri log
+
+
log2
+ md
e
2²
M2
12sb
144
min (m, d)b²
[
(L6T
[6T
116rmin(m. min(m, d)b + 7) m.N
[m + d]
log
1
loga
7P
2²
(F.10)
where at Equation F.10 we have substituted the values of ri and M2. This motivates the following
choice of
Im dJ min (m, d)
p+2
T 144 संय M bxizb b
(F.11)
which leads to the following covering number bound:
2y (m + d d
Mbb
12s
log (Ic) & 144
log
1 +
min (m, d) オ
16 M el
24p min(m, d) t11
Im + d) ptzb b
+ log2
+ 7 md
Mb
v+2
3p
[m + d] djriz min(m, d) o loga (
[16]MP + +1][b + 1J[1 + s) Im +
24
+7 mN
where at the last line, we have used the fact that p & 2 and therefore 144 < 12. The proof is complete.
We have the following very direct L2 analogue, which follows directly by applying Proposition with - m. Proposition F.4 (L2 cover of FP ). Consider the set of matrices with a bounded Schatten norm as follows: FP == {Z mxd xd 1Z Milea & = [| & 3 (where M is a fixed referenece matrix) viewed as linear maps from Rd to Tum and assume as usual that we have a training set I1,... .1....,IN.
EN E Rdd such that || & for all i & N.
There exists cover C c FP such that for all Z E FP, there exists a Z C such that for all & N. we have
I1( Z)0il12 C.
(F.12)
and
M 3P
log (IC)
& 24
[m + d min(m. (m, d) ooス [m]] +
loga (T'rp)
bs
x 24
[ + d) d piz +tz log, (Tz+),
61

---

where I xp == (0j//e + + +7) m..
cP-7
G
Extension to Convolutional Neural Networks (CNN)
In this section, we generalize our results to Convolutional Neural Networks. particular, this section culminates in Theorem G.5| which provides post hoc generalization bound for convolutional neural networks whose weight matrices have low Schatten p quasi norm.
We first introduce some more detailed notation, which generally follows the existing literature on norm based bounds [16] and is reintroduced for completeness. One difference that we assume that the pooling operation only operates on the spatial dimension (which is standard in real life CNNs applications), which results in the single notation Ug for the channel dimension layer E, which replaces both notations my and Ug from [16].
Let R/x= denote input 'image', A Uxd and S* S2..,, be O ordered subsets of (f1, 2, 21,,..... w) x {1, (1,2,.... U}} each of cardinality d corresponding to the convolutional 'patches'. We will write A E RUxO for the image of under the convolutional operation associated with A: Ax(x)j.o Σ A5. The sets , , So represent the image patches where the convolutional filters are applied, and A would be represented via the "tf.nnn.cov2d" function in Tensorflow (or we add a layer index l. For instance, if the input is 28 x 28 x 1 image and the convolutional filters are size 2 x with stride 2, - g0.1 = {(1, 1), (1, (2, 1), (2, 2)} represents the first convolutional patch, and g0.2 {(3, 1), 2), (4, 1), 24) represents the second convolutional patch.
conv2d" in Pytorch). To represent the patches at a given layer,
We will also write op(A4)) for the matrix in RUOO2 1xte 1 that represents the convolution operation Ar (after unravelling all the dimensions), as we will rely on its sepetral norm op(A in calculations. To represent the full architecture, we use the index é to represent the l'th layer: for instance, the fth layer's convolutional operation is denoted by Ax= /g 18u - R0 and acts on the é- 1th layer's activations in the space. is also assumed that the last layer is fully-connected.
x
The architecture above help represent feedforward neural network involving possible (intra- layer) weight sharing as
F'C. At : RUxx RUUxx : (OL A OL- o AA o 01 AAI)()), (G.1)
where for each & L, the weight A a matrix in Rexd and for each &, og RU,xO, R x is L Lipschitz with constant pe and represents both the elementwise activation operation and any spatial pooling.
G.1 One Layer Case
We now consider the covering number of the class of functions corresponding to layer's convolu- tional operation with a matrix A such that ||A - M M|ssc.p & M for some number M.
Proposition G.1 (L cover CP for a convolutional layer). Assume we are given a training set II....,ZN E Uoxx such that sups,o (zx:)so. & b. Consider the set of matrices with bounded
Schatten norm as follows: FP = {z E R xd ZZ M & MM rs"; op ()] & s (where M is an arbitrary reference matrix) and the associated class C, == (AA : A FP] of linear maps
representing the assocated convolution operations from RD xw to U8" xw.
There exists cover C C? such that for all Z CP, there exists a Z C such that for all & N, have
[(Az - A2) Ec
(G.2)
62

---

and
log (Ic)) < 24
Mb
[0" + d] dj min(U", d))=t log2 (Tee)
2p
[ss
< 24
(U) [U' + dl min(U", dd rl-stz po loga (Tee)
where Tep == 10[ + [[+++[[++++++++ +
U'NO. +
cP42
Proof. Note that ||||| <
& [2]
Thus, the proposition follows immediately from Proposi-
tion applied to the auxiliary dataset collecting each input convolutional patch as a sample and replacing N - NO and m + U.
We also have the following immediate T,2 version, which follows from the previous proposition with The and utilizing the - Lipschitzness of the nonlinearity a.
Proposition G.2 (L2 cover of ez for convolutional layer). Instate the notation of Proposition G.1 and consider a p-Lipschitz activation function : RU'x TR'''xu' There exists a cover such that for all Z E Ey, there exists a Z E C such that for all i & N, we have
Il(Az (z,)ll $ Ep
(G.3)
and
3p
Mb
P12
log (Ie)) & 24
[U' + df min(U", ,d, -d [U' w'Il loga (T'e)
c
$ 24
bs
p+2
[U' + +d- 1 W'' loga (Te:),
where TV Cp
[6] +1]b+||]++ss00 +'U''
+7) U'NO.
FF2
We now move to covering number bound for the class of CNNs with fixed norm constraints:
we write
ENE F 10-(''- PA= (AI...A)) IA Melsc & Me op(AA) se v | & $L
for the class of neural networks whose matrices satisfy the norm constraints with fixed constraints Me, etc.
G.2 Covering Number For the Class Fg
We have the following analogue of Proposition Proposition
E.1l for the convolutional case:
G.3. Let II be a given training
set
sat-
isfying
b
for all i.
Consider the class F
FA=FF (A Az) | Melao Me lop(Ae)] s Ve |AAll2,0 CNNs satisfying a set of fixed norn constraints for given set of Me, St. We have the following covering number bound for the loss class loF for any > N:
st of all
(1 + LL) min(E,
1
ll e)) < 22loog24I1
(G.4)
b
Pss
Me PETZ
P4 [U d p2 min(U,, de-1) PC- W.
peta
SePe
where 1. := [6 1|[LL| + +1JAAN IT
[l:
1]s; 1].
63

---

Proof.
continue from The proof is similar to that of Proposition E.1 most differences are in the detailed calcula-
tions.
As before, for any choice of 61,-.., C,, by Lemma R.12 we know that loFg admits an 1 cover with granularity Σe=1 Cepe-L and cardinality
log (IC)) $ Σ (o E N, b.opo-e-1)),
(G.5)
where B : {A₂ E Uexde || Mellac.p. Ma op((A)]] & 8t) (for + L) and BY || - Mellsc.p1. & MLi op(At))l & SL}.
{Ac Uexd
We now use the following notation: we write Ug for the number of channels at layer & and de for the number of pixels each convolutional patch at layer so that min(U,, de-1) is the minimum dimension of the filter applied at layer L. we also write W U2 x we with the convention that WL 1. We also write W := Σ de-1 Ue for the total number of parameters in the network and A :- Σz= U2 x Oz-1 for the total number of preactivations/inutt dimensions including both the input and the final layer output. Note that by Propositions G. and G.2 equation (G.5) as follows:
202
log ([C) < 24 Σ
Me bpo
PF12
[U++ + d, d--1 min 1,1, w P t log, (T JP z): (G.6)
W
FP. 16 + 11 11 gottt] + +7) NA (indeed, since
where for all E I. re
|| & S1, we certainly have ||AL| & sL.).
We now set e, 1LL++1ppe- as before and bound all the logarithmic factors as follows:
16/max/ M, 6eee
11 I[p: + 1]s; + 1] + [ +1]WA'
max r
FP &
+ +7 NA
min(e, 1)
L
64
1]s; + 11 +1W [[p: (=1
< [4r
(G.7)
where r : [b+ 1[ + IIWANT 1]s; + 1]. Plugging the value of epsilon into
equation (..
continue with a calculation similar that of equations E. 143
log (Ic)
72 (og
Me -po
Pe-2
21 U de-1] F6+2 min de-1) PE+2 Wrrtz
2p
(1 L Ln)
72 (4g
min(e, 1)
Σ
M
92+2
[U+ + d min(Ue, de-1) 1--1) W !
Prsi
8pPr
expected.
G.3
Generalization Bound with Fixed Constraints (CNNs)
Based on the above. we obtain the following analogue of Proposition E.1
Proposition G.4. Fix some reference/intiiaizatiin matrices M E Rwixes Rw xd ...... M4
R xw C Assume also that the inputs x satisfy || & b w.p. Fix set of constraint parameters 0 Pe & Me (for E 1,... L).
64

---

With probability greater than 1 - over the draw of an i.i.d. training set II....,NN, every neural network F (a) defined with equation (G.I) satisfying the following conditions:
AA MMaae & Mr
& t L
|| [op(A)e 8e
f L-1
2, & SL:
(G.8)
also satisfies the following generalization bound:
N Σ
[[(FA()).V]]
(FA((z)).))
N
log( ())
208
logz [1 [Bg())
< 6[ +111
(1 + II.) = M.s.p.b
(G.9)
N
VN
where R
M.a,p. :
3p PC+2
Mr
PE+2
2 de-1) min(Us, 1 pita W
P38
re
(G.10)
SpPe
with re,
M. SC
and r : [b +1WANT + 1]8; + 1].
Proof.
The proof is exactly the same that of Proposition E.11 with गहंड w we vズ
replaced by
2
Pt
ve [Ue + de-1) -tंz min(Ue, 1e-1) -E+z W and the initial constant of 98 replaced by 72. D
Tgee
G.4 Post Hoc Result for CNNs
Based on the above, we are finally in position to present the following analogue of Theorem E.2 for the convolutional case:
Theorem G.5. With probability greater than 8. for any b IR+, every trained neural network FA and sampling distribution with | & b w.p. satisfy the following generalization gap for all possible values of the pes:
1
E ([((F())) w0
(FF(()))
(G.11)
N
log (1/5)
2 + 0
Vlo((re log( N)
6[B 6[B+
6B
+16[B+1][ LL),ffy
RFA
N
N
where
o
2 log
4W.A sup [.
I op(A))
[og[sup |axl|)) L Σ
log(Il op( 2log(4AM))
i=1
7e.
12
[ + 1][LL++ +1JWAN M op( A3) 1]
4W B I pall (oppp(p)
and where
65

---

3PL PC
L-1
A || [op(Ae)
Melle, Pe SC.
Me
Rr,
sup
[ppll/lllll 22,00
II
poll op(())]
2-1
2F PL
|A Mr.1le..p
FL
P1
bp 2,00
Pi
Asl
W
PL
W
The proof is the same as that Theorem E.2 || replaced by op((A))l, and W replaced by AW.
Proof.
with the constant 240 replaced by 208, with
G.5 The case 0 (CNN)
For Pe we obtain the following immediate corollary from Proposition G.4
Corollary G.6. Instate the notation and assumptions of Proposition G.4. and assume additionally that for all E. We have
E(I(FA(z),)) w)1 (FF(.:))
log(#) 208 1ogg(41 (4I log( [) +1]
L
& <6[B+1] <6/++]|
Uv + di 1
(G.12)
N
VN
where Fe is an a priori upper bound on rank(Ap) and as usual, r = [b + + 1]s; 1].
With a union bound, we achieve the following post hoc version: Theorem G.7. W.p. > 1 over the draw of the training set, every neural network satisfies:
N
log :
208 log, 41 log [B +1]
[[(F(()) 1(Fx(x)),)) & 6[ +1]
N
(G.13)
where DE [
+ A: + +
11]
Proof. The proof is nearly exactly the same as that of Theorem E.8
G.6 Results for CNNs with Loss Function Augmentation
Proposition G.8. For any granularity > L and any values of & ben... br.-1, 88, there exists
N cover C of the augmented loss class Ce.Auus == {Naug (FaugFFAAs I,,, FA Fb) with cardinality bounded as follows:
log (IC)) & 216 216log(4 E (.nu )
(G.14)
3p4 Pr#2
L)) L(1
TFF
"y [U + de-1] 12 min de.1) w
b
sipi
min(e, 1)
Proof. The proof is similar to that of Proposition G.3 and F.4 with the main difference only in the calculation of the log terms. By Lemma E.3 and Propositions G.1 and G.2 there exists cover C of
66

---

the loss class Aaug (Fa) with cardinality satisfying
log(Ic)) x
,e,, N,,,,,,,,,,)
(G.15)
3p1
Me b1
PC#2
[U + 1e-11 min(Us 7e W loga ( (.Aa))))
& 72
F9,e
Next, recall that
bye
c
(G.16)
Lpe
and Pt, maxt P max, Pr, - (min(1, & Ph. Phi-ppis[[ + L1] & Ph Pty-oPisi +
Lj] = Ps II [p,,;[1 LJ,, thus
< Lpe-211 L,]
(G.17)
Thus, by a nearly identical calculation to that in equation G.7 we obtain
16[max
M,Pe "p
I1l I Up: + 1Js; 1 + I 1JWA
C.dan max
JP,
$
min
+ +7 NA
64
[[P: + 188; + 1 + +1W < [ooo
(G.18)
i=1
where e.Aavg = [b + +I
+ 1]ss + 1]. Thus, we can continue from
equation (..15 : log((e]) &
201 PCT2
Meb
Pv [U2 + de-1] ve1z min(Ue, d W
216 2o6log( 4T (.dug))
d
PETZ
C2
2pr Me Mebe-ipe + [T] [1 8:P
Pr12
216 216log( 41 Cidaus)
e
x
[Ue de-1] 14-1]66 Fets
W
2x1
L(1 + Ln) min
2+7
2p
L
P/42
< 216 log( (4 (.daa))))
be-
8:Pi
i=1
[Ue de-1] ग min(Ue, de-1) Wirtt 1f
expected.
Next, similarly to the proof of Proposition G.4 we can obtain:
Proposition G.9, Fix some reference/inttialzzaton matrices M' E wgwixe w ML
p", = C Assume also that the inputs satisfy ||=||| < b w.p. 1. Fix set of constraint parameters Pt st, Me (for e = 1,..., L).
With probability greater than 1 over the draw of an i...d. training set Ii,..., IN. every neural network F (x) defined with equation (G.) satisfying the following conditions:
A
M M & Me
viεlEL L v1 v
|| [p(())) & 88
LA 12.00 & 81.
(G.
67

---

also satisfies the following generalization bound:
N
[[)(FA+))
(FFA(:))
(G.20)
log
361, v logo( (4I a.pe,auu log(N)( +1]
< 6|B +1|N
(1 + LL) ,ंr R R.dag
N
N
M.s.b.b
where R C.daug
M.s.p.bb ==
2p
Me
2
Pt
Pi8i
2112 e,
[Ue + de-1] 7 min(U d(,, W Pr
Se
i-f
with rg,e = M and C,Aau = lb+ +1)
+1s; 1].
Proof. The proof is the same as that of Proposition G.4 with an additional factor of v3, relying Proposition instead of Proposition G.3
Finally, we can obtain the following post hoc version from the above.
Theorem G.10. With probability greater than 1 5, for any E TR+,, every trained neural network FA satisfies the following generalization gap for all possible values of the pes:
1 Σ
log( 1/6)
E (((FA()),
(FF(()))))
< 6[B +11l
(G.21)
N
N
2 +
C.Auna log
Vlog(Te, Aan log(N)
722 +22[BB+][[(1
L,)] a
C.Aano
FA
N
VN
where
+
G,Aang = 2 2log log
4W.A + sup [a Il pel op(A:)]
|
log (x +
Σ
log(ll op(AA)))
Bo((BBe-L.l)) log log(4AW))
Ye, 12
[2 I][LL, [[[LL++1JWaal IJWAN I
[adl op( A:) +1]
4W + B II Tellop(A)))]
1=1
and where
2pr pf42
R C.Aang RA
Σ
sup [x; 11.111///222,00 B, 1,Ae
II Pisi
(G.22)
i-1+1
|lAe
Me Pt || opp |
re+2
[Ue + de-1
min(Ue, de-1) p W
2
Proof. The proof is the same as that of Theorem B.6 with the original constant of 416 replaced by 361 and ||lll replaced by o.((e)].
68

---

H Generalization Bound for Linear Networks with Schatten Constraints
In this section, we briefly mention that it is possible to prove alternative bounds for linear networks assuming the presence of Schatten quasi constraints the factor matrices (instead of L constraints). Indeed, a generalization of Theorem 3.1 (Theorem I.2) allows also one to translate such constraints into single Schatten quasi norm constraint the linear map A.
Theorem H.I. For any 0 & & 1, write for the conjugate such that = - over the draw of the training set, every linear network as defined in equation following generalization bound:
W.p. > 1 1-6 satisfies the
3.5
(
GAP
B
log(1/ (18) z
\ \IL
23
L
pl
Pt
24p
[C d]
(H.1)
N
N
where supp laell the Ô notation hides polylogarithmi
I Known Results
This section collects some well-known results which are key to our proof, and which we include for the benefit of self-completeness.
Theorem I.1
22 Theorem 1). Let 2 min(C, d) and let Bı,..., By be matrices such that
B1 wxxd Br RCx B2..., BL-1 Rwxw For any matrix A Boxd have
L|A sc, = min
Bell subject to BLBL-1-.. B₁ A.
(I.1)
Theorem 1.2 (192 93 94)). Let Eo min(C, d) and let B By be matrices such that B Rexd B, RCxx B...., BL-1 E Rxx Fix . PL such that 1 = => pi
For any matrix A Rexd have
P2 p Be
|A
min
sE.PE
subject to BI.BI- Bi
(1.2)
sc.
Pt
[I6] (with U 1), see also 65 Let Ti..... EN Rd be such that ||x & foror all i & N. For any fixed choice of reference matrix M E Rmax consider the set FM of matrices A E mamxd such that ||A -M lr, & a. For any > 0 there exists a cover C c SM such that for all A FM, there exists A E such that for all & N, II(A M) and
Proposition 1.3 (Cf. Proposition
36a212
(8ab)
log (IC)) &
loga
+7) mN
(L.3)
Lemma 1.4 (Lemma 8 in 4
The (internal) covering number N of the ball of radius in dimension (with respect to any norm ||-l)) can be bounded by:
3x
3k
N
$
+
(I.4)
Recall also the following lemma from 833
Propusition L.5. Let n, dE N, a, b b> 0. Suppose we are given n data points collected as the rows of matrix X e Rund with [ ||a & 6, Vi 1....,m. For (o,((X) {Xa |al2 a. Rd).
we have
36a 21
8abm
6n + 1).
log.V DV,.(U.,. (X),
&
loga
2
69

---

Theorem 166 (Generalization bound from Rademacher complexity, ef. e.g. 1951. 196 197 etc.). Let Z, Z,, ...... Zn be i.i.d. random variables taking values set Consider set of functions Fe [0, 1]2. vo > O, we have with probability 2 1 å over the draw of the sample S that
1 VFEF, B(S(2) & N
log( 4/8)
Σ f(4) + 29 3V
2N
where RF(F) can be either the empirical or expected Rademacher complexity. In purticular, if f arg min B()( and f arg frg Li-1 f(zi), then
1og(2/6)
B(((Z)) & (Z)) + (F) + 6
2N
Lemma 1.7 (Dudley's entropy theorem 198] this version from [16 191. see also 1 4). Let F be real-valued function class taking values in [0, B). Let S be finite sample of size N. We have the following relationship between the Rademacher complexity R(Fls) and the L² covering number e 11-112).
12
R(F(s) inf
4a
(F15,
VN
where the norm ||-12 on RRN is defined by ||0| N ( 10,12))
70


Reviews:
[{"review_id": "sOk1ZF2bKf", "reviewer": "Reviewer_Udna", "summary": "This paper obtains generalization bounds for neural networks with low complexity weight matrices - both in terms of low rank as well as low Schatten $p$-quasi norm for $0<p<1$. The bound obtained by the authors scales as $O \\left ( \\sqrt{\\frac{L^2 r W}{n}} \\right) $ and does not scale exponentially with the depth or width of the network. The authors also evaluate their bounds on trained deep networks and show that their results compare favorably to other generalization bounds.", "questions": "1. Are your bounds still larger than the test error? It seems like the are in Fig D.6 In which case, are they still technically vacuous?\n\n2. Is there a route to obtaining non-vacuous generalization bounds through the low-rank bias of deep networks? Possibly applying your techniques with PAC-Bayesian bounds.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper is very well written and comprehensively discusses a lot of related papers on generalization bounds. Their appendix sections serve as a good review of the literature on generalization bounds for deep networks. The application of covering number based bounds allows the authors to avoid exponential dependence on the depth. The authors derive their bound for fully connected networks as well as convolutional networks. They also study how their techniques interact with others such as loss function augmentation to obtain data dependent bounds. The results seem quite favorable, especially when looking at the comparisons on trained networks.\n\nWeaknesses: While this is a strong paper with a lot of technical results, it mostly applies techniques developed by prior work in the context of deep network generalization bounds. Rademacher complexity bounds through metric entropy, parametric interpolation for bounding the covering numbers of approximately low rank matrices, and complexity bounds for convolutional networks that depend on the weights of the filters rather than the number of patches are all known results. Putting them together is a valuable contribution, but that also means that the mathematical novelty in this paper is limited. In case this is mistaken, the authors should do a more precise job of outlining their novel mathematical contributions.", "was_revised": true, "final_justification": "I believe this paper makes a meaningful contribution to the literature on generalization bounds. The questions I raised were exploratory in nature and not threshold issues for the paper's validity. I recommend acceptance.", "rebuttal": "Many thanks for your positive review and your interest in our work, as well as the efforts invested in reading our paper. We also appreciate your statements that our paper is **very well written** and **comprehensively discusses** a lot of **related papers**. \n\n\n**Re main weakness** \"Putting them together is a valuable contribution, but that also means that the mathematical novelty in this paper is limited. In case this is mistaken, the authors should do a more precise job of outlining their novel mathematical contributions\": \n\nMany thanks for your comment. We want to clarify that our bounds are the first to incorporate the technique of **parametric interpolation** into the study of neural networks. Thus, we are the first to provide generalization bounds in this context which are neither fully \"parameter counting bounds\" nor fully \"norm-based\" bounds. This is achieved by interpolating between the two regimes.  More precisely, we the class $\\mathcal{F}_p:\\{A\\in\\mathbb{R}^{m\\times d}: \\|A\\|\\leq s, \\|A\\|_p\\leq \\mathcal{M}\\}$ into two components: (1) **a component** with (exactly) **low rank**, to be treated with *parameter counting* techniques [2,3], and (2) a component with **small norms**, to be treated with norm based techniques [4,5]. For linear maps $A\\in\\mathbb{R}^{m\\times d}: x\\rightarrow Ax$, parameter counting bounds on the covering number of the class $\\{A\\in \\mathbb{R}^{m\\times d}}: \\|w\\|\\_{FR}}\\leq a\\}$ scale as $O\\Big( D\\text{Polylog}(\\epsilon,a,b) \\Big)$ where $b$ is a bound on the input samples' norms and $D=md$ is the number of parameters. On the other hand, norm-based bounds scale as $O\\Big(\\frac{a^2b^2}{\\epsilon^2}\\text{Polylog}(N,a,b,d)\\Big)$. Combining them in an approximately low-rank context allows us to replace $D$ by $[m+d]r$ where $r$ is a threshold rank depending on the Schatten quasi norms, gives rise to a completely different dependency on $\\epsilon, a,b$ and even the Lipschitz constant of the loss (i.e. the margin parameter in a classification context). The combination is not trivial and involves decomposing the function class by thresholding the singular values with a carefully tuned threshold (cf. eq F13).  In addition, there are many additional technicalities which are new to this setting. For instance, the continuity argument to make the bounds post hoc with respect to all the Schatten indices $p\\_{\\ell}$ is relatively tedious.  To further improve your assessment of the novelty of our method, we invite you to read the **proof sketch** of a minimum working product version of our theorem which is **provided in our answer to reviewer 9AFC**. \n\nWe promise to further emphasise the novelty of our techniques and provide the proof sketch in the camera ready version if accepted.  \n\n\nRe typos: \n\nLine 56 (also pointed out by reviewer 9AFC): we will add the word \"small\" at the end of the sentence, many thanks. Line 137: thank you for the correction. Line 213: yes, you are right. Many thanks for helping us improve the quality of the manuscript. \n\nE. 142: yes, you are right, we will fix this, which will harmonize the result with the version provided in the main paper. Idem for F12/F15. Once again, we **thank you8* warmly for your efforts in reading our main paper and appendix carefully. We stand **ready to answer any further questions** as required. \n\nRe question 1 \"is the bound larger than the test error\": we appreciate your observation based on the axes of the graph. Yes, like most comparable works, the bounds are vacuous at realistic scales if we do not apply further tricks (e.g. compression, data dependent priors, aggressive optimization of the bound through additional spectral regularization). We wanted to compare how all bounds vary with architectural parameters in a reasonable simple pure uniform convergence setting which excludes applying too many post-processing tricks to make the bounds tighter. Our reasoning is that the numerical values of generalization bounds are not as important as how they behave when the architecture changes. Indeed, numerically tighter estimates of the test error can be obtained with a validation set. Our bounds demonstrate the validity of  the approximate rank as a complement to margins [3,5] as a measure of **unused function class capacity**. \n\nRe question 2: \"route to non-vacuous bounds\": yes, we believe it is possible to achieve non-vacuous bounds with more aggressive tricks. For instance, the bounds for the fully connected case are not far from being non vacuous if one ignores logarithmic factors. They may become non-vacuous if we were to tweak the architecture, explicitly **compress** the rank by removing higher order singular values, and apply spectral norm constraints. In addition, incorporating PAC-Bayesian techniques, including data-dependent priors [7,9,10] into our analysis is a **tantalizing direction for future research** with the potential for non-vacuous results. However, we wanted to limit our setup to uniform convergence as closely as possible to provide a fair proof of concept. We hope and believe our contributions are a sufficient component to warrant one publication, without having to combine it to even more other techniques to make the bounds numerically tighter, as we believe doing so would make the paper even less approachable to readers and reviewers. \n\nOn a side note, we would also like to point out that it is very difficult, if not impossible, to compare all bounds in the literature without ignoring logarithmic factors and constants. Indeed, many works (e.g. [2]) skip constants entirely, and **many works (e.g. [2,3]) do not explicitly write down the proof of the post hoc step,**  leaving it as an exercise for the reader. This makes a comparison with our theorem E.2. unfair if one includes the logarithmic factors arising from the numerous post hoc steps over $s\\_{\\ell}, p\\_{\\ell}, \\mathcal{M}\\_{\\ell},$ etc. \n\n\nOnce again, we thank you for your appreciation of our work and look forward to our further discussion with you. \n\n\n\n\n============================**Continuation of Answer to Reviewer 9AFC**======================\n\n\n\nMany thanks for your detailed comments. We **appreciate the constructive suggestion** of a proof sketch and the corrections of the typos found in the appendix. We promise to fix all of these typos and suggestions, including introducing a footnote at line 38.  We also promise to cite and discuss [6] as requested. Re Line 115, we will remove the initialized matrices $M_\\ell$ from the introduction to improve clarity. Many thanks. Re 250, both equation (2) and Neyshabur et al. refer to the same result, we will clarify this and fix the sentence. Re 285/266: many thanks, we will harmonize both notations by removing the initialized matrices $M\\_{\\ell}$ from the introduction. \n\n**Re dependency on the input space dimension:**/**possibility to remove the dependence on the input dimension or the hidden layer**. \n\n\nMany thanks for your comment, which is closely related to reviewer wqbT's insightful question 1. For the one layer case, we agree that our results translate to a sample complexity of at least $[m+d]$ where $d$ is the input dimension. This is a weakness compared to the purely norm-based bounds in [4,5], which only involve the Frobenius norm of the weights. In particular, even for $p=2$, the bound doesn't coincide with [4,5]. To the best of our knowledge, this limitation is extremely challenging to remove (we invite the reviewers to check the argument involving Markov's inequality in the proof sketch of Prop F2 to satisfy themselves that no simple modification of the technique can improve this). However, this limitation *doesn't make our results uniformly inferior* to either norm-based or parameter counting bounds. \n\n\nWe want to clarify that when we claim it could be possible to improve the dependence on the input dimension, we mean to achieve this under the assumption that the input samples approximately lie in a low-rank subspace. Similarly, taking into account the fact that activations approximately lie in a low-rank subspace may also allow us to further improve the dependency. However, these as-yet uncertain improvements require very significant technical modifications to the proofs which are better left to future work. \n\nCf answer to rev. wqbT for further details on these last questions. \n\n\nWe thank you again for your interest in our work and are looking forward to our further discussion. \n\n\n\n\n\n=================================**References**===========================\n\n\n[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.\n\n[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.\n\n[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.\n\n[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.\n\n[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017.\n\n[6] Suzanna Parkinson, Greg Ongie, Rebecca Willett. ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models  \n\n\n[7] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel M. Roy. On the role of data in PAC-Bayes bounds\n\n[8] Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization. https://arxiv.org/abs/2106.15933v1\n\n[9] Zhou, Wenda, et al. \"Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach.\"\n\n[10] Biggs, Felix, and Benjamin Guedj. \"Non-vacuous generalisation bounds for shallow neural networks.\" International Conference on Machine Learning. PMLR, 2022.\n\n[11]  Neyshabur, Bhojanapalli, Srebro.  A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks. ICLR 2018."}, {"review_id": "gl5OypmtD6", "reviewer": "Reviewer_jSQv", "summary": "This paper studies why neural networks often form approximately low-rank representations in their layers during training, a property sometimes called the bottleneck rank. The authors analyze this phenomenon and develop new theoretical generalization bounds that explicitly account for the rank-sparse structure of neural network weights. Using the framework of Schatten p quasi norms, they derive sample complexity results that interpolate between traditional norm-based bounds and parameter-counting bounds, capturing the benefit of low-rank weight matrices. The paper extends these results to linear networks, fully-connected deep neural networks, and convolutional neural networks (CNNs), providing a new perspective on how low-rank properties induced by depth can improve generalization. Overall, the work offers novel theoretical insights on the role of implicit low-rank regularization in deep learning.", "questions": "1. The paper introduces a parameter 𝑝 in the Schatten 𝑝-quasi norm, but does not give any practical guidance for choosing or interpreting this parameter. Could the authors discuss how to select 𝑝 or its influence on the bound? \n2. Could the authors clarify the approximate magnitude of the bound, or at least discuss whether they are likely to be meaningful for realistic network sizes?\n2. The paper’s interpolation between norm-based and rank-based bounds is interesting. Could the authors clarify more explicitly how their framework compares to, or might be combined with, margin-based generalization analyses (e.g., in kernel methods or neural tangent kernel literature)?\n2. The theoretical guarantees appear to rest on the existence of low-rank (or approximate low-rank) weight matrices. Can the authors comment on how realistic this assumption is across a wider range of architectures, for example transformers or large language models?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nThe paper is rigorously grounded in mathematical theory, presenting novel generalization bounds for neural networks by leveraging the low-rank (“bottleneck rank”) structure of their weight matrices. \n\n1. Extending low-rank sample complexity arguments beyond linear networks to FNNs and deep CNNs, while explicitly considering the Schatten p quasi-norm, is innovative.\n2. Overall the paper is clearly written, especially in its statement of the main results and their significance. Morever, the related works are concrete including key literatures.\n3. The analysis is thorough, covering linear networks, deep neural networks, and CNNs, with detailed treatment of covering numbers and complexity measures. Clear notations, definitions, and assumptions are well documented.\n\nWeaknesses:\n\n1. It presents main theoretical results in section 3, while there is no any problem set up, no empirical results and detailed experimental settings in the main text, though some results presented in the appendix. However, they are not well referred to the theorems presented in the main text. \n2. The proofs, while thorough, are highly technical and may be difficult to follow for a broader ML audience not specialized in generalization theory.\n3. There is no experimental verification of the tightness of these bounds beyond theoretical discussion (though they mention an appendix with MNIST/CIFAR10 references, it is not sufficiently emphasized and lacks of comparisons with recent approaches).\n4. Some transitions between theoretical claims and related works are abrupt, making it hard to track their originality relative to prior results without repeatedly cross-referencing. \n5. There is limited demonstration of the practical impact for network design or training, which might weaken its appeal to practitioners.\n6. The assumptions of low-rank weight matrices may not hold in all architectures, especially in smaller models or architectures with strong regularization.", "was_revised": true, "final_justification": "Thanks for Authors' detailed clarification, I have increased my rating. However, the authors should add additional content mentioned in the rebuttal to the final paper version.", "rebuttal": "Many thanks for your efforts reading and reviewing our paper. We try our best to allay most of your concerns in this response and stand ready to answer any further questions you may have during the author discussion period. \n\nRe weakness 1 \"there is no any problem set up\": The problem set up is described in the \"main results\" section, and is a **standard supervised learning set up** with neural networks where we study the excess risk in terms of an arbitrary $L^\\infty$ loss function. As explained in that section, this setting can cover both classification [1,4] and regression [2] settings, and is a similar generic characterisation as in [3] (mentioned by reviewer wqbT). \n\n**Re weakness 1** \"no empirical results and detailed experimental settings in the main text\" and **weakness 3** \"*There is no experimental verification of the tightness of these bounds beyond theoretical discussion (though they mention an appendix with MNIST/CIFAR10 references, it is not sufficiently emphasized and lacks of comparisons with recent approaches)*\":\n\nOur paper contains a large amount of content including novel generalization bounds for linear classifiers as well as bounds for deep neural networks with a low rank structure, it is difficult to include every result in the main paper. However, the appendix does include substantial **experimental verification on pages 31 to 36** where we demonstrate our bounds' competitiveness and ability to capture some of the phenomenon of unused function class capacity. Indeed, we demonstrate: \n1. That our bounds are competitive with other uniform convergence bounds \nand 2. that our bounds are less sensitive to architecture changes than other bounds in the overparametrization setting. In particular, this demonstrates our bounds' ability to capture unused function class capacity via an alternative notion of effective capacity than the well-established alternative such as the distance to initialization and the margins. \n\nRe weakness 1 \"the experiments lack comparison to recent approaches\":  whilst our paper is mostly theoretical, we compare our work experimentally to **11 baselines from 7 papers** including one from ICML 2024. The choice was based on a focus on bounds in the same category as ours: **uniform convergence** bounds which do not incorporate the optimization procedure into the bound and do **not overly optimize the bound** with data dependent priors  or by splitting the dataset and learning different parameters on each subset (such as e.g. [3]). To the best of our knowledge, the compared approaches are state of the art in this category. **Please let us know if you have another specific \"recent approach\" in mind for us to compare to.** This would help us further improve the contextualisation of our work. \n\nRe weakness 5 \"no practical impact in terms of model design\" and \"assumption of low-rank matrices may not hold in practice\": the main message in our submission is that the implicit low-rank condition which occurs with depth and overparametrization implies a reduction in effective function class capacity and therefore, estimation error. The convergence to low-rank representations is a broadly studied phenomenon which many recent works have demonstrated occurs at realistic scales. We believe that demonstrating the effects of this phenomenon on learning is worthy in itself, even if it may not yield completely new models (though it does provide some evidence for why depth can reduce rather than increase function capacity in some regimes. \n\n\nOn your questions: \n\n1. As we tried to explain in lines 86-94, the parameters $p$ control the strictness of the low rank constraints and the bounds position on the spectrum between parameter counting bounds and norm-based bounds. Indeed,  when $p\\rightarrow 0$, the bound behaves as a parameter counting bound taking into account the rank of the weight matrices. For larger $p$s, the bound behaves more like a norm-based bound based on the *approximate rank* of the weight matrix, with a larger tolerance for moderately small singular values. \n\nNext, note that as explained in line 289, the bounds **hold simultaneously over all values** of $p_l$. Therefore, the $p_\\ell$s can be be optimized after training via **grid search**. \n\n\n2. As can be seen from the (logarithmic) scale of the axes of Figures D1 and D4, the bounds are generally vacuous at realistic scales, even ignoring logarithmic factors.  However, so are all comparable bounds in the literature when used directly. We acknowledge it is possible to obtain tighter bounds through a more aggressive optimization of the bound or by modifying the training procedure to validate certain parameters using the training data. However, such bounds are no longer directly comparable.\n\n3. **Our bounds** include **margin-based** generalization analyses as particular cases of our results. In particular, our setting for the classification case is exactly the same as that in [1]. In that case, our result is generally tighter but nether uniformly superior nor inferior to most existing approaches. A combination of our results with bounds based on the **Neural Tangent Kernel** would be more subtle since such results  ** rely heavily on the optimization procedure**. However, if one assumes that the neural network training is purely at the neural tangent kernel scale, then the problem becomes analogous to the study of linear predictors, which could in principle be combined with our results. However, to the best of our knowledge, the convergence of neural network learning to a neural tangent kernel limit has not been proved in a reasonable classification setting (all NTK results rely on the square loss). \n\nWe promise to incorporate a discussion of these concerns in the camera ready version. \n\n\n4. As explained in lines 76 to 80, the emergence of the low-rank condition is well-documented in many influential recent papers [5,6,7,8], including large language models [8]. We also verified it experimentally, as can be seen in figures D2 and D4. \n\n\nRe formatting concern 3\" in line 248, \"the above bound\" refers to equation (11) in the theorem just above the remark inside which line 248 is found. We will replace the statement by a concrete reference to the equation as requested, many thanks for helping us improve the presentation of our work. \n\nRe figure captions:  in figures D2 and D4, the plots illustrate the spectral decay of the weight matrices: each given plot represents the singular values of a weight matrix, ordered from the largest one (on the left) to the smallest one (on the right). Hence, the x axis is referred to as \"index\" in the caption and the y axis similarly refers to the \"magnitude\" of the singular value. Thus, the graphs are always decreasing by definition, and a graph which hits 0 (i.e. the x axis) at index r would correspond to a matrix of rank exactly less than r. We will  make sure to explain this in further details in the revision. \n\n\n\n\n[1] Peter Bartlett, Dylan J. Foster, Matus Telgarsky. Spectrally-normalized margin bounds for neural networks. NeurIPS 2017\n\n[2] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruosong Wang. Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks. ICML 2019\n[3] Biggs, Felix, and Benjamin Guedj. \"Non-vacuous generalisation bounds for shallow neural networks.\" ICML 2022.\n\n[4] Florian Graf, Sebastian Zeng, Bastian Rieck, Marc Niethammer, Roland Kwitt. NeurIPS 2022On Measuring Excess Capacity in Neural Networks. \n\n[5] Arthur Jacot. Bottleneck Structure in Learned Features: Low-Dimension vs Regularity Tradeoff. NeurIPS 2023\n\n[6] Zihan Wang, Arthur Jacot. Implicit bias of SGD in L2-regularized linear DNNs: One-way jumps from high to low rank. ICLR 2024\n\n[7]  Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity. Arxiv 2021\n\n[8]  Laura Balzano, Tianjiao Ding, Benjamin D. Haeffele, Soo Min Kwon, Qing Qu, Peng Wang, Zhangyang Wang, Can Yaras. An Overview of Low-Rank Structures in the Training and Adaptation of Large Models.  ArXiv 2025"}, {"review_id": "93YXrpDDgo", "reviewer": "Reviewer_a1zf", "summary": "The paper presents a generalization bound that utilizes the low-rankness of the weights in deep learning. Choice of the matrix Schatten $p$-norm to characterize network layers result in a particular effect in the generalization bound: as $p\\to0$, the remaining dominant term in the bound makes the bound act like a parameter-counting bound, while as $p\\to2$, the bound acts like a product-of-norms bound, while still incorporating the approximate low-rankness of the matrices. The authors extend their results to CNNs as well.", "questions": "- L8: Schatten norms are introduced as quasi-norms in the abstract, and described as such in L84. Then in the later section results with $0\\leq p \\leq 2$ are presented. This conflict persists elsewhere in the paper as well, please fix.\n- L42: Using a more specific term instead of \"architectural parameters\" would be helpful\n- L56: Cut-off sentence?\n- L60: Difficult to understand summary\n- L75: The abstract and introduction are unclear regarding whether the focus of the paper will be low-rankness of weights vs. representations. A stark example is L94 discussing representation rank vs. L95 declaring that the paper will focus on weight rank.\n- L78: \"experimentally\" typo\n- L83: Dimensions of $A$ wrong?\n- L89: \"with more tolerance for small non-zero singular values\". This is unclear. What does tolerance mean in this case?\n- L93: \"rank of the activation layer\"? Rank of the post-activation representations?\n- L94: The term “bottleneck rank” is used multiple times by now without a clear or formal definition, two of these in the abstract. Its relevance to the paper’s main results is also not well motivated. Unless it's central to the core theorems - which currently does not appear to be the case - I suggest removing all references to it. An alternative is to present this within a cogent discussion as in L365 (and doing so *once*).\n- L107: \"over the classes\"?\n- L115: Omitting the reference matrix before the clarification in L223 is confusing\n- L123: I appreciate that the authors are not burying the lead by introducing baseline vs. their own proposed bounds in Section 1, but without a proper introduction to the notation this gets real confusing real fast\n- L139: \"spacial\" typo\n- L145: I cannot understand the main point of this paragraph\n- L175: I wonder if this detailed a discussion between previous and current work should be left for after the main results.\n- L208: \"common joint distribution\"\n- L208: $\\mathcal{D}$ undefined\n- L226: \"extreme\"?\n- L228: I don't think this paragraph clearly introduces the significance of the linear network results\n- L276: \"indices\"?\n- L277: max. input norm is already defined\n- L281: Is the replaced term realistically/often smaller than the maximum input norm?\n- L317: Unclear, use the standard term \"matricization\" perhaps?\n- L323: \"spacial\"", "limitations": "The authors are transparent about the limitations of their work.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- The paper is clearly situated and motivated within the context of previous literature.\n- The authors present generalization bounds that exploit the (approximate) low-rankness of the weight matrices. Although their bounds are not necessarily strictly tighter than previous bounds (e.g. with full-rank matrices), that they can be tighter utilizing the approximate low-rankness of the matrices is important.\n- That their bounds behave like a parameter-counting bound vs. product-of-norms bound based on the $p$ value is independently interesting\n- The authors expand their results to CNNs.\n\n## Weaknesses\n- The paper presents a strong narrative and addresses a meaningful problem, but it has significant issues with clarity of the presentation, particularly in the introduction. The reader is presented with technical claims before being properly introduced to the notation and setup; the introduction repeatedly emphasizes the low-rankness of representations in deep learning, only to later clarify that their results are based on the low-rankness of *weights*; the abstract refers to Schatten quasi-norm, but only later does it become apparent that the results apply across the full range $0 \\leq p \\leq 2$. None of the issues are individually disqualifying but their cumulative effect significantly undermines the readability of the paper. See the section below for more details.", "was_revised": true, "final_justification": "I think that this is a paper that has merit, but is hindered by its disorganized presentation. The authors have committed to resolving these issues, thus I maintain my recommendation for acceptance.", "rebuttal": "**Many thanks** for your careful reading and for your appreciation of our work. We are happy that you deem our work to **address meaningful problems** and ** is clearly situated and motivated within the context of previous literature.**\n\nRe **clarity **(especially the  introduction): many thanks for your comment and for the typos identified.  We promise to restructure the introduction to further improve clarity by defining the relevant quantities earlier and introducing further simplifications in the introduction. \n\n**Re L 281 \"realistically smaller\"**: yes, the improvement provided in this theorem is frequently significant, since it removes a factor of the product of spectral norms from layer 1 to layer $\\ell-1$ (replacing it by an empirical estimate of the norms of the intermediary activations. \n\n**Re \"full range $0\\leq p\\leq 2$\"/ L8, conflict with abstract**: **for $p<1$**, the resulting object is **not a norm** but only a quasi norm, though we agree **it is a norm for $p\\geq 1$**.  All norms are also quasi norms, but the opposite is not true, which makes it difficult to choose a single term since (as you observe) we cover the full range $p\\in[0,2]$. Therefore, we use the term \"quasi-norm\" in all cases to avoid the more redundant term \"quasi norm/norm\". We **promise to explain this** more clearly earlier in the introduction and are willing to adapt to any further suggested change of terminology. \n\n\n**Re \"low-rank weights, not low-rank activations\"**: many thanks for the insightful comment. We do mention the distinction in various places including the conclusion/future directions. However, we agree to discuss it more clearly earlier in the introduction. As mentioned in the paper, the two are very closely related $\\star$ and we believe that a significant extension of our techniques would allow us to *directly capture* the low-rank structure in the activations as well (without truncating the rank of the weights after training). However, this requires a much more careful treatment involving advanced uses of loss function augmentation, especially when the activations are only approximately low-rank. From our initial calculations, the singular value thresholds must be tuned simultaneously over all layers, which is very tedious. \n\n\nRe typos: many thanks, we will fix all of them. \n\n\n\n\nMany thanks again for your comments, we promise to discuss all the above issues in more detail in the camera ready revision if accepted and look forward to continuing our discussion during the author-reviewer discussion phase. \n\n\n\n\nFootnote:\n$\\star$ Indeed, treating only the exactly low-rank case for simplicity, if the inputs $x_1,\\ldots,x_N$ lie in a low-rank space of dimension $r$, then for any high rank weight matrix $W\\in\\mathbb{R}^{m\\times d}$, there exists a low rank weight matrix $\\bar{W}$ of rank less than $r$ which has exactly the same effect on these inputs: $Wx_i=\\bar{W} x_i$ for all $i$. Indeed, if $U\\in \\mathbb{R}^{d\\times r}$ is an orthonormal basis of that subspace, then $\\bar{W}=[WU ]U^\\top$ will work because $UU^\\top x_i =x_i$ for all $i$.   Thus, **if the activations are low-rank, then the same network can be represented with low-rank weights**."}, {"review_id": "BUriZRlnOb", "reviewer": "Reviewer_9AFC", "summary": "This paper provides generalization bounds via covering numbers for neural networks with low-rank (or approximately low-rank) weight matrices.", "questions": "Can you provide a proof sketch of a simplified form of Theorems E.2? I am not comfortable accepting this paper without a readable proof sketch to fascilitate verification of the validity of the proof, and I think a good proof sketch will make this paper much more useful to the community. Aim for as much simplicity in the sketch as possible; e.g. assume that $L_1 = B = \\rho_i = 1, L=2$, etc., and use $\\lesssim$ liberally instead of explicitly showing constants, etc.. If the sketch is clear and verifiable, I will increase my score to a 5.\n\nYou mention that you believe that the dependency on input dimension is likely removable. Do you believe that the dependency on the output dimension and/or hidden width is also removable?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Generalization bounds based on low-rank weight matrices have the potential to be much tighter than existing bounds. It has been observed empirically and theoretically that depth induces an inductive bias towards low-rank weight matrices, this result is a great first step towards tightening generalization bounds in this setting.\n\nHowever, the paper is currently poorly presented. Technical notation is used in the introduction long before it is defined in section 3. I was unable to verify technical details because of the very, very long proof without a sketch. A readable sketch that gives more insight into the techniques would be helpful.\n\nAdditionally, the final bound has poor dependency on the input space dimension. At least this work is *upfront* about the fact that dependency on input dimension is a major limitation. \n\nOther minor comments/suggestions to improve clarity:\n- Line 26: \"DNNs *on* natural data\"\n- Line 38: the parenthetical (for simplicity...) is better as a footnote\n- Eq 1,2,3 and Lines 104, 110, 114: *Lots* of undefined notation here, including $p_\\ell, L_1$, etc. Perhaps simplify the presentation by assuming some terms are constants here-- $L_1, B, \\rho$, etc. \n- Line 56: make the norm *small*\n- Line 75: Should also cite Parkinson et al. 2023 (arXiv:2305.15598)\n- Line 83: Typo: $A \\in \\mathbb R^{C \\times d}$ not $A \\in \\mathbb R^{w \\times d}$\n- Line 91: These results are more about the effect of adding a $L_2$ regularization term to the loss than about optimization itself.\n- Line 115: While later you specify that it's best to choose $M_\\ell$ to be zero in which case talking about the low rank structure in the term makes sense, it's confusing that $M_\\ell$ is dropped here. If $M_\\ell = 0$ is the best choice, why include $M_\\ell$ in line 110 at all?\n- Line 237: The first sentence seems to have a word missing?\n- Line 250-251: This doesn't make sense as written. I think there's a typo in equation it's comparing to?\n- Line 285: is this supposed to be the notation from Line 266?", "was_revised": true, "final_justification": "I believe this work represents a significant result, and including a proof sketch and addressing other presentation issues we have discussed will improve the paper. While the proof sketch provided during the discussion period was morally correct and the authors have since corrected several typos, the presence of typos in the proof sketch gives me some trepidation that there may be other unidentified issues in the full proofs. However, I believe reasons to accept outweigh reasons to reject, so I raise my score to a 4.", "rebuttal": "Many thanks for your detailed comments and interest in our work and promise to increase your score to 5 pending a satisfactory proof sketch of our main theorem. Due to the character limit, we include only the sketch here. **Please note the answers to your other questions are provided in the response to reviewer Udna**. \n\n**Simplified Prop F2 (covering number for one layer)**: Consider the following function class of linear maps from $\\mathbb{R}^d$ to $ \\mathbb{R}^m$: $\\mathcal{F}^p:=\\{M \\in\\mathbb{R}^{m\\times d}, \\|M\\|\\_p\\leq \\mathcal{M}; \\|M\\|\\leq s\\}$. For any $\\epsilon>0$ and for any dataset $x_1,\\ldots,x_N\\in\\mathbb{R}^d$ such that $\\|x_i\\|\\leq B$ for all $i$, we have the following bound on the $L^\\infty$ covering number (cf Prop F2 for formal defn) of the class: \n\n$$\\log(\\mathcal{N}_{\\infty}(\\mathcal{F}_r^p,\\epsilon))\\lesssim [m+d]\\Bigg[\\frac{\\mathcal{M}B}{\\epsilon}\\Bigg]^{\\frac{2p}{p+2}}\\log(\\frac{mdN\\mathcal{M}}{\\epsilon}).$$\n\n**Proof sketch (for simplicity we assume $B=1$ in the sketch):**\n\nFor any $M\\in\\mathcal{F}^p$, write $\\sum_{i=1}^{\\min(m,d)} \\rho_i u_iv_i^\\top$ for its singular value decomposition. For a threshold $\\tau>0$ to be determined later, we decompose every $M\\in\\mathcal{F}^p$ into $M=M_1+M_2$ where $M_1=\\sum_\\{i\\leq T\\} \\rho_i u_iv_i^\\top$ and $M_2=\\sum_{i\\geq T+1}\\rho_i u_iv_i^\\top$ where $T$ is the last index such that $\\rho_{T}> \\tau$. \n\nBy Markov's inequality, since $\\|M\\|\\_p^p=\\sum_i \\rho_i^p \\leq \\mathcal{M}^p $, we have $\\text{rank}(M_1)\\leq \\tau\\leq \\frac{\\mathcal{M}^p}{\\tau^p}$. In addition, the spectral norm of $M_1$ is bounded as: $\\|M\\_1\\|=\\rho_1=\\|M\\|\\leq \\|M\\|\\_{p}\\leq \\mathcal{M}$. Thus, $M_1$ belongs to the set ${\\mathcal{F}^p}\\_1:=\\Big\\{ Z\\in\\mathcal{F}^p:\\text{rank}(Z)\\leq  \\frac{\\mathcal{M}^p}{\\tau^p}, \\quad \\|Z\\|\\leq \\mathcal{M}\\Big\\} $ (a function class with few parameters its members are **low-rank**)\n\tFurthermore, it is clear that $$\n\t\t\\|M_2\\|\\_{FR}^2=\\sum_{k=T+1}^{\\min(m,d)} \\rho_k^{2} \\leq \\tau^2 {\\min(m,d)}.$$\nTherefore $M_2$ belongs to the class $\\mathcal{F}^p\\_2:=\\{Z\\in\\mathcal{F}^p: \\|Z\\|\\_{\\text{FR}}^2\\leq \\tau^2 {\\min(m,d)}\\} $ (a function class whose members have **small norms**). \n\nBy classic *parameter counting* arguments (cf. [2,3] etc., the specific result being Lemma D1 page 30 in [1]), we have the following bound on the $L^\\infty$ covering number of $\\mathcal{F}^p_1$:\n$$\\mathcal{N}_\\infty(\\mathcal{F}^p_1,\\epsilon/2)\\lesssim [m+d][\\text{rank}] \\log(\\frac{\\mathcal{M}}{\\epsilon})\\lesssim [m+d]\\frac{\\mathcal{M}^p}{\\tau^p}\\log(\\frac{\\mathcal{M}}{\\epsilon}).$$\n\nBy classic *norm-based arguments* (Theorem 4 in [4]), we can bound the covering number of the class $\\mathcal{F}^p_2$ as follows: \n$$\\log(\\mathcal{N}(\\mathcal{F}^p_2,\\epsilon/2))\\lesssim [\\text{max Frob norm}] \\log(\\frac{\\tau^2 mdN}{\\epsilon}) =\\frac{\\tau^2 {\\min(m,d)}}{\\epsilon^2} \\log(\\frac{\\tau^2 mdN}{\\epsilon}).$$\n\nCombining both covering number bounds gives \n$$\\log(\\mathcal{N}_{\\infty}(\\mathcal{F}_r^p))\\leq \\log(\\mathcal{N}(\\mathcal{F}^p_1,\\epsilon/2))+\\log(\\mathcal{N}(\\mathcal{F}^p_2,\\epsilon/2))\\lesssim     \\frac{\\tau^2 {\\min(m,d)}}{\\epsilon^2} \\log(\\frac{\\tau^2 mdN}{\\epsilon})+[m+d]\\frac{\\mathcal{M}^p}{\\tau^p}\\log(\\frac{\\mathcal{M}}{\\epsilon})$$\n\nSetting $\\tau=\\mathcal{M}^{\\frac{p}{p+2}} \\epsilon^{\\frac{2}{p+2}}$ gives \n$\\log(\\mathcal{N}_{\\infty}(\\mathcal{F}_r^p))\\lesssim $ $[m+d]\\left[\\frac{\\mathcal{M}}{\\epsilon}\\right]^{\\frac{2p}{p+2}}\\log(\\frac{mdN\\mathcal{M}}{\\epsilon})$\nas expected. \n\n\n\nThe above result forms the basis of the one-layer case. As requested, we now consider the two-layer case: \n\n**Simplified form of Proposition E.1.:** Consider neural networks of the form $F_{A}:x\\rightarrow A^2 \\sigma(A^1 x)$ where $\\sigma$ is an elementwise 1-Lipschitz activation function (e.g. ReLU) and $A_1\\in \\mathbb{R}^{m\\times d}, A^2\\in\\mathbb{R}^{C\\times m}$ are weight matrices. For fixed $p_1=p_2=p\\in[0,2]$ and $s_1,s_2,\\mathcal{M}_1,\\mathcal{M}_2>0$, let $\\mathcal{F}$ denote the class of such networks which further satisfy for all $i\\in\\{1,2\\}$: $\\|A^i\\|\\leq s_i; \\> \\|A^i\\|_p\\leq \\mathcal{M}_i$.  By abuse of notation, we also use $\\mathcal{F}$ to refer to the set of matrices $(A^1,A^2)$ satisfying the above requirements. \n\nLet $\\ell: \\mathbb{R}^C\\times [C]\\rightarrow  \\mathbb{R}^+$  be a 1-Lipschitz loss function w.r.t. the $L^\\infty$ norm (e.g. a margin-based loss function as in [2,3,5] with margin 1) and assume we are given an i.i.d. training set $(x_1,y_1),\\ldots, (x_N,y_N)$ from a joint distribution over $\\mathbb{R}^d\\times [C]$ such that $\\|x_i\\|\\leq B$ w.p. 1. \n\nFor any $\\delta>0$, w.p.  $\\geq 1-\\delta$, any network $F_A\\in\\mathcal{F}$ satisfies the following generalization bound: \n$$\\mathbb{E}\\ell(F(x,y))-\\hat{\\mathbb{E}}(\\ell(F(x,y)))$$ $$\\leq  \\tilde{O}\\bigg([s_1s_2]^{\\frac{p}{2+p}} \\bigg[\\big[\\frac{\\mathcal{M}_1^{p}}{s_1^{p}}\\big]^{\\frac{2}{p+2}} [m+d]^{1+\\frac{p}{p+2}} + \\big[\\frac{\\mathcal{M}_2^{p}}{s_2^{p}}\\big]^{\\frac{2}{p+2}} [m+C]\\bigg]^{\\frac{1}{2}} \\frac{1}{\\sqrt{N}} +\\sqrt{\\frac{\\log(1/\\delta)}{N}}\\bigg).$$ $$ < \\tilde{O}\\Bigg([s_1s_2]^{\\frac{p}{2+p}} \\bigg[\\big[r_1[m+d]^{1+\\frac{p}{p+2}} + r_2 [m+C]\\bigg]^{\\frac{1}{2}} \\frac{1}{\\sqrt{N}} +\\sqrt{\\frac{\\log(1/\\delta)}{N}} \\Bigg),$$\n\nwhere for $i=1,2$, $r_i:=\\big[\\frac{\\mathcal{M}_i^{p}}{s_i^{p}}\\big]^{\\frac{2}{p+2}}  $ is a **soft analogue of the rank**. \n\n\n\n**Remarks:** We assume the margin parameter is 1 because you specifically requested that the lipschitz constant be ignored. However, our full results include a fine analysis of the dependency on the margin parameter $\\gamma\\simeq 1/L_1$. The $\\tilde{O}$ notation incorporates logarithmic factors of $N,m,d,C,1/\\epsilon, s_1,s_2,\\mathcal{M}_1,\\mathcal{M}_2$. \n\n**Proof sketch:**\n\n**Step 1 (key)**: bounding the $L^{\\infty}$ covering number of $\\mathcal{F}$. Since the loss function is 1 Lipschitz, we only need to find an $L^\\infty$ cover of $\\mathcal{F}$, i.e., a set $\\mathcal{C}\\subset \\mathcal{F}$ such that for any $A=(A^1,A^2)\\in\\mathcal{F}$, there exists a cover element $(\\bar{A}^1,\\bar{A}^2)\\in \\mathcal{C}$ such that $$\\forall i, \\|F_{A}(x_i)-F_{\\bar{A}}(x_i)\\|\\_\\infty\\leq \\epsilon$$ (here, recall $F_{A}(x_i)\\in\\mathbb{R}^C$ is a vector of scores for all classes). We achieve this by adapting standard chaining techniques (see [3,5]), with the caveat that we need to change the norm of the cover at the intermediary layer, incurring a factor of $\\sqrt{m}$. Let $\\mathcal{F}^1,\\mathcal{F}^2$ denote the set of matrices $A^1\\in\\mathcal{R}^{m\\times d}$ and $A^2\\in\\mathcal{R}^{C\\times m}$ satisfying the relevant constraints above. First, we can apply Proposition F2 above, with $\\epsilon$ set to $\\epsilon_1:=\\epsilon/[2\\sqrt{m}s_2]$, to achieve a $\\mathcal{C}_1\\subset\\mathcal{F}_1$ such that for all $A\\in\\mathcal{F}$ there exists a $\\bar{A}\\in\\mathcal{C}$ such that $\\forall i$, \n$\\|\\sigma(A^1(x_i))-\\sigma(\\bar{A}^1(x_i))\\|\\leq \\|A^1x_i-\\bar{A}^1x_i\\|\\leq \\sqrt{m} \\|\\leq \\|A^1x_i-\\bar{A}^1x_i\\| \\leq \\sqrt{m}\\epsilon_1 =\\frac{\\epsilon}{2s_2}.$ and $\\log(|\\mathcal{C}|)\\in \\tilde{O}\\Bigg( [m+d] \\Big[\\frac{\\mathcal{M}_1 B }{\\epsilon_1}\\Big]^{\\frac{2p}{p+2}} \\Bigg) =\\tilde{O}\\Bigg( [m+d]  m^{\\frac{p}{p+2}} [s_1 s_2B]^{\\frac{2p}{p+2}}\\Big[\\frac{\\mathcal{M}_1   }{s_2\\epsilon}\\Big]^{\\frac{2p}{p+2}}\\Bigg)$. \n\nSimilarly, for any $\\bar{A}^1\\in\\mathcal{C}_1$, every $i\\leq N$ satisfies $\\|\\sigma(\\bar{A}^1x_1)\\|\\leq s_1 B $, and therefore another application of Proposition F2 above with $B$ replaced by $\\tilde{B}:=s_1 B$ and $\\epsilon$ replaced by $\\epsilon_2:=\\epsilon/2$ yields a cover $\\mathcal{C}_2(\\bar{A}^1)$ with size $\\log(|\\mathcal{C}_2(\\bar{A}^1)|)\\in \\tilde{O}\\Bigg( \\Big[\\frac{\\mathcal{M}_2 [Bs_1] }{\\epsilon_2}\\Big]^{\\frac{2p}{p+2}} \\Bigg)=\\tilde{O}\\Bigg([Bs_1s_2]^{\\frac{2p}{p+2}} \\Big[\\frac{\\mathcal{M}_2  }{\\epsilon s_2}\\Big]^{\\frac{2p}{p+2}}   \\Bigg)$. \n\nThe cover $\\mathcal{C}:=U\\_{\\bar{A}^1\\in\\mathcal{C}_1} \\mathcal{C}_2(\\bar{A}^1)$ is now an $\\epsilon$ cover of $\\mathcal{F}$. \n\nIndeed, for any $(A^1,A^2)\\in\\mathcal{F}$, we can define $\\bar{A}^1$ to be the cover element associated to $A^1$ in $\\mathcal{C}_1$ and subsequently $\\bar{A}^2$ to be the cover element in $\\mathcal{C}\\_1(\\bar{A}^1)$ associated to $A^2$, which yields for any $i\\leq N$: $$\\|A^2\\sigma(A^1x_i)-\\bar{A}^2\\sigma(\\bar{A}^1x_i)\\|\\_{\\infty}\\leq \\|A^2\\sigma(A^1x_i)-A^2\\sigma(\\bar{A}^1x_i)\\|\\_{\\infty}+\\|A^2\\sigma(\\bar{A}^1x_i)-\\bar{A}^2\\sigma(\\bar{A}^1x_i)\\|\\_{\\infty}$$ $$ \\leq \\epsilon_2+\\|A^2\\|  \\|\\sigma(A^1(x_i))-\\sigma(\\bar{A}^1(x_i))\\|\\leq \\epsilon/2+s_2\\epsilon/[2s_2] =\\epsilon.$$\nFurthermore, the resulting cover has cardinality bounded as $$\\log(|\\mathcal{C}|)\\in \\tilde{O}\\Bigg( \\Big[\\frac{Bs_1s_2}{\\epsilon}\\Big]^{\\frac{2p}{p+2}} \\Big[[m+d]^{1+\\frac{p}{p+2}} \\Big[\\frac{\\mathcal{M}_1  }{s_1}\\Big]^{\\frac{2p}{p+2}} +[m+C] \\Big[\\frac{\\mathcal{M}_2  }{s_2}\\Big]^{\\frac{2p}{p+2}}  \\Big]\\Bigg).$$\n\n**Step 2:** Apply Dudley's entropy integral to obtain Rademacher complexity and apply classic results. This step  (cf. Proof of Prop E1) involves more straightforward calculations. \n\n\nIn prop E2, the result holds **uniformly over all $p$s** and all $\\mathcal{M}_1,\\mathcal{M}_2,s_1,s_2$. The idea of the proof is to apply Prop E1 to a each element of grid $\\{0,2/K, 4/K,\\ldots 2\\}$ of $p$s with the failure probability replaced by $\\delta/[K+1]$ and to tune the granularity $K$ together with a tedious continuity argument w.r.t $p$. Cf. pp 39 to 42 for details. \n\n\n\n\n\n\n[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.\n\n[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.\n\n[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.\n\n[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.\n\n[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017."}, {"review_id": "ZJhOJU9VJk", "reviewer": "Reviewer_wqbT", "summary": "The paper proves a novel generalization bound for fully-connected and convolutional neural networks. This bound features a free parameter $p_l$ for each layer $l$ which could be chosen a-posteriori (that is, the bound is uniform wrt these parameters). By choosing these parameters, one could interpolate between a norm based bound similar to [1] to a classical parameter-counting bound, individually for each layer. To be specific, the bound is based on $p$-Schatten norms of layer weights, which interpolate between a Frobenius norm ($p=2$) and a usual matrix rank ($p=0$). Being able to interpolate gives flexibility that allows to cover the case of approximately low-rank layer weights conveniently.\n\nThe paper provides a thorough overview on existing norm-based and parameter-counting generalization bounds, as well as on a low-rank bias of neural nets. There are also experiments conducted for simple multi-layer fully-connected and convolutional networks trained on MNIST and CIFAR dataset.\n\n[1] 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", "questions": "1. Am I right that Line 110 does not coincide with (2) when all $p_l=2$? In other words, does your Theorem 3.2 recover the main result of [Neyshabur et al. 2018] when all $p_l=2$? If no, why?\n2. Lines 90 — 94: which \"deep results\" specifically are you referring to?", "limitations": "If the obtained bounds are numerically vacuous, I would mention it as a limitation.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The approach taken in the paper generalizes two large classes of generalization bounds (norm-based and parameter counting) in a natural and neat way.\n2. The literature overview is rather thorough.\n3. The paper spends a lot of time comparing its main result and approach to relevant works, thus showing clearly where this work stands among other works.\n4. The main theorems are stated in a clean and easy-to-absorb way.\n\n**Weaknesses**\n\n1. Rank sparsity was specifically enforced in experiments for fully-connected networks.  To me, this is not really fair because this looks like forging a setup that favors the bound of the paper but not the bounds the paper compares to.\n2. The architecture used for experiments on convolutional nets looks strange: 3 conv layers followed by 5 fully-connected layers. What was the reason to use this structure? This looks neither like a standard setup to compare with other works, nor like a simple well-performing ConvNet.\n3. The comparison ignores logarithmic factors, and, probably, constants; are the exact numbers provided in Appendix D informative then? Maybe, an asymptotic for large depth or width could be more informative.\n4. The paper does not disclose any exact values of the bounds they prove. This makes me suspect these bounds to be vacuous in more-or-less realistic setups when evaluated up to a number. At the same time, non-vacuous bounds do exist (see e.g. [2,3]), but the paper never mentions them.\n5. One relevant citation seems to be missing: [1] studies low rank biases for linear networks induced by $l_2$-regularization.\n\n**Minor issues**\n\n1. Not clear from this point what is L_1 in (1) (it is introduced later). If it is a Lipschitz constant, why \"we assume that the nonlinearities are 1-Lipschitz when discussing related works\"?\n2. Line 111: there is no $p$ in the above formula.\n3. Line 110: is the factor $L^{p/(2+p)}$ forgotten here?\n4. Not clear from this point what is $p_l$ in the formula on line 110 (before the main result is formally introduced).\n5.  Line 78: \"expreimntally\"\n6. Line 285: the argument $x_i$ seems to be at the wrong place.\n\n[1] Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization. https://arxiv.org/abs/2106.15933v1\n\n[2] Zhou, Wenda, et al. \"Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach.\" \n\n[3] Biggs, Felix, and Benjamin Guedj. \"Non-vacuous generalisation bounds for shallow neural networks.\" International Conference on Machine Learning. PMLR, 2022.", "was_revised": true, "final_justification": "I thank the authors for responding thoroughly to my questions. I am convinced that I understood the paper fairly during the initial evaluation and therefore, I keep my score.", "rebuttal": "Many thanks for your positive review and your statement that our paper **clearly where this work stands among other works**, and that our theorems are **clean and easy to absorb**. We try our best to allay all your concerns below and stand ready to provide further clarifications upon request. \n\nRe weaknesses: \n\n1.  Many thanks for your comment. We agree that this additional regularization in the fully-connected experiments favors our bound and somewhat departs from our general approach of minimizing optimization tricks. We believe that both our bounds would still outperform the baselines if we replaced this trick by spectral constraints, and that our sharper result (including loss augmentation) would still outperform the baselines with neither trick involved. We promise to incorporate a discussion of some additional such experiments in the camera ready version if accepted. \n\n2. The architecture was chosen to be large enough to involve the rank-sparsity inducing effects of depth which we study, but also small enough to allow us to fun experiments for a wide range of widths without undue computational overload. \n\n3. Yes, our numerical comparison ignores logarithmic factors and constants. This is in line with much of the recent literature. Therefore, the main message of our experimental section is that our bounds are **less sensitive to increases** in width, since they can **capture the spontaneous reduction** in function class capacity arising from low-rank representations. \nWe would also like to point out that it is very difficult, if not impossible, to compare all bounds in the literature without ignoring logarithmic factors and constants. Indeed, many works (e.g. [2]) skip constants entirely, and **many works (e.g. [2,3]) do not explicitly write down the proof of the post hoc step,**  leaving it as an exercise for the reader. This makes a comparison with our theorem E.2. unfair if one includes the logarithmic factors arising from the numerous post hoc steps over $s\\_{\\ell}, p\\_{\\ell}, \\mathcal{M}\\_{\\ell},$ etc.\n\n\n4. Yes, the bounds are vacuous at realistic scales if one incorporates all the logarithmic factors (though as explained above, this is a potentially questionable point). Our aim was to limit ourselves to uniform convergence bounds, excluding many of the tricks used to optimize bounds. For instance, to the best of our understanding,  [9] rely on a **compression**of the learned network, similarly, [10] assumes that the weights of the first and second layer are optimized on distinct subsets of the training set. We interpret these facts as warranting the classification of those results as belonging to a slightly different branch of the literature. However, we really **enjoyed reading both papers [9,10]** suggested  (especially [10]) and **promise to incorporate a further discussion of them** in the camera ready version if accepted. \n\n5. Many thanks for the suggestion. Although we have already included other references by the same authors which study the same phenomenon [13,14,15], we have missed this one, which we promise to discuss in the camera ready revision. \n\n\nRe **question 1**: \n\nYes, you are right, and this is a very sharp observation. This is due to the Markov inequality argument in the key proof of Proposition F2, which we also recommend you check in the proof sketch we added in the response to reviewer 9AFC. The key reason is that the parameter counting component of the function class involves a factor of $[m+d]r$ and even the norm-based component involves a factor of $\\min(m,d)\\tau^2$, resulting in an unavoidable dependence on $[m+d]$ (or at least $\\min(m,d)$).\n\nTo the best of our knowledge, it is difficult to smoothly remove this limitation except by trivially  imposing a minimum between both bounds. This underscores the substantial differences between our application of parametric interpolation in the neural networks context as opposed to its original introduction in the context of matrix completion in [1]. However, we want to emphasize that this doesn't make our results uniformly inferior to either norm-based or parameter counting bounds. \n Indeed, counting parameters directly when estimating the capacity of the first layer  of linear maps $A^1\\in\\mathbb{R}^{m\\times d}$ would yield a sample complexity of at least $md$ instead of $[m+d]$, and the norm-based bound would be very large if the norms of the weights are large, though our own results involve norm based quantities only at a reduced and tunable power of $\\frac{2p}{p+2}$.  Furthermore, if all the weights are binary (making norm based and parameter counting approaches equal), then our result will coincide with both, indicating that there is **no \"pure loss\"**: it can merely be said that although our bound interpolates between $p=0$ and $p=2$, a casualty of the interpolation is that **even setting $p=2$** (which corresponds to the norm-based bound), the bound **still leans slightly towards parameter counting despite incorporating strong norm-based aspects**. \nIndeed, consider the one layer case in n idealised situation where each weight belongs to the set $\\{-1,1\\}$. In this case, the norm based bound gives a sample complexity of $\\|A\\|\\_{Fr}^2=md$, which recovers the same bound as a pure parameter counting bound. **In this case**, our \\textit{sample complexity} bound for $p=2$ and $B=1$ scales as (cf Theorem 3.1)  $\\mathcal{M}^{\\frac{2p}{p+2}} \\min(m,d)^{\\frac{p}{p+2}} [m+d]^{\\frac{2}{p+2}}=\\mathcal{M} [m+d]=O(\\|A\\|\\_{Fr}\\sqrt{\\min(m,d) \\max(m,d)} )=O(md)$, **which also coincides with both norm based and parameter counting bounds**. However, as explained in the main paper, our bound is also sensitive to the rank, approximate rank, etc. \n\nRe Question 2: we meant to refer to the results in [12,13,14,15,16], and promise to clarify this further in the camera ready revision. \n\nRe Limitations: many thanks, we will incorporate a full discussion as above in the revision. \nRe minor issues: many thanks for your help in improving the clarity of our manuscript. Regarding points 2 and 3, the confusion arises from the fact that we treat the Lipschitz constants as absolute constants in the informal discussion in the introduction, removing the need for the factor in question. \n\nOnce again, thank you for your thorough comments. We hope that our rebuttal has helped further convince you of the value of our work and that you will continue to engage with us in the discussion phase. \n\n\n\n=================================**References**===========================\n\n\n[1] Ledent, A.; Alves, R. Generalization Analysis of Deep Non-linear Matrix Completion. ICML 2024.\n\n[2] Long, P. M.; Sedghi, H. Generalization Bounds for Deep Convolutional Neural Networks. ICLR 2020.\n\n[3] Graf, F.; Zeng, S.; Rieck, B.; Niethammer, M.; Kwitt, R. On Measuring Excess Capacity in Neural Networks. NeurIPS 2022.\n\n[4] Zhang, T. Covering Number Bounds of Certain Regularized Linear Function Classes. JMLR 2002.\n\n[5] Bartlett, P. L.; Foster, D. J.; Telgarsky, M. Spectrally-Normalized Margin Bounds for Neural Networks. NeurIPS 2017.\n\n[6] Suzanna Parkinson, Greg Ongie, Rebecca Willett. ReLU Neural Networks with Linear Layers are Biased Towards Single- and Multi-Index Models  \n\n\n[7] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Arpino, Daniel M. Roy. On the role of data in PAC-Bayes bounds\n\n[8] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, Franck Gabriel. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity  \n\nEarlier version: Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization.\n\n[9] Zhou, Wenda, et al. \"Non-vacuous generalization bounds at the imagenet scale: a PAC-bayesian compression approach.\"\n\n[10] Biggs, Felix, and Benjamin Guedj. \"Non-vacuous generalisation bounds for shallow neural networks.\" International Conference on Machine Learning. PMLR, 2022.\n\n[11]  Neyshabur, Bhojanapalli, Srebro.  A PAC-Bayesian Approach to Spectrally-Normalized Margin Bounds for Neural Networks. ICLR 2018.\n\n[12] Arthur Jacot, François Ged, Berfin Şimşek, Clément Hongler, Franck Gabriel. Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity  \n\nEarlier version: Jacot, A., Ged, F., Gabriel, F., Simsek, B., and Hongler, C. (2021). Deep linear networks dynamics: Low-rank biases induced by initialization scale and l2 regularization.\n\n\n[13]  Bottleneck structure in learned features: Low-dimension vs regularity tradeoff. NeurIPS 2023.\n\n[14] Implicit bias of large depth networks: a notion of rank for nonlinear functions. \n\n\n[15] Zihan Wang and Arthur Jacot. Implicit bias of SGD in $l_2$-regularized linear DNNs: One-way jumps from high to low rank. ICLR 2024. \n\n[16] Laura Balzano, Tianjiao Ding, Benjamin D. Haeffele, Soo Min Kwon, Qing Qu, Peng Wang, Zhangyang Wang, Can Yaras. An Overview of Low-Rank Structures in the Training and Adaptation of Large Models. ArXiv 2025"}]

Author rebuttal:

Meta-review: The authors develop generalization bounds for linear networks, fully-connected and convolutional neural networks.  Using the notion of Schatten quasi norms, they have obtained sample complexities that interpolate between classical  norm-based bounds and parameter-counting bounds. 

The reviewers had originally concerns about the novelty of the results, tightness of the bounds, and appropriateness of the experiments to test the implications of theory. All reviewers are already happy with the paper and noted the rebuttal addressed their major concerns. Considering the rebuttal and reviewers’ final justification, I would like to recommend acceptance and suggest that authors address all revisions that are promised within the camera-ready version.
Decision: Accept (poster)