Norm-based Generalization Bounds for Sparse Neural Networks
Authors: Tomer Galanti
Mengjia Xu
Liane Galanti
Tomaso Poggio
Venue: NeurIPS 2023 poster (2023)
Keywords: generalization bounds
convolution
rademacher
generalization
sparsity

Abstract: In this paper, we derive norm-based generalization bounds for sparse ReLU neural networks, including convolutional neural networks. These bounds differ from previous ones because they consider the sparse structure of the neural network architecture and the norms of the convolutional filters, rather than the norms of the (Toeplitz) matrices associated with the convolutional layers. Theoretically, we demonstrate that these bounds are significantly tighter than standard norm-based generalization bounds. Empirically, they offer relatively tight estimations of generalization for various simple classification problems. Collectively, these findings suggest that the sparsity of the underlying target function and the model's architecture plays a crucial role in the success of deep learning.

Norm-based Generalization Bounds for Sparse Neural Networks
Tomer Galanti
Mengjia Xu
Center for Brains, Mind, and Machines Massachusetts Institute of Technology galant @mit..mi...e....mmmeeeeeeeeeeeee edu
Department of Data Science
New Jersey Institute of Technology mx6@n jit edu
Liane Galanti
Tomaso Poggio
School of Computer Science
Center for Brains, Mind, and Machines Massachusetts Institute of Technology tp@csail wwt. edu
Tel Aviv University Lianeaalanti @mail. tau. ac. il
Abstract
In this paper, derive norm-based generalization bounds for sparse ReLU neu- ral networks, including convolutional neural networks. These bounds differ from previous ones because they consider the sparse structure of the neural network architecture and the norms of the convolutional filters, rather than the norms of the (Toeplitz) matrices associated with the convolutional layers. Theoretically, we demonstrate that these bounds are significantly tighter than standard norm-based generalization bounds. Empirically, they offer relatively tight estimations of gen- eralization for various simple classification problems. Collectively, these findings suggest that the sparsity of the underlying target function and the model's archi- tecture plays a crucial role in the success of deep learning.
Introduction
Over the last decade, deep learning with large neural networks has significantly advanced the solu- tion of myriad of tasks. These include image classification [ 2 3.
language processing 5 6 g) and code synthesis (.. Contrary to traditional theories such as [10), recent findings [T] 12 indicate that deep neural networks can generalize effectively even when their size vastly exceeds the number of training samples.
interactions with open-ended environments
To address this question, recent work has proposed different generalization guarantees for deep neural networks based on various norms of their weight matrices 13
14
18 19
20
21 22 23).
Many efforts have been made to improve the tightness of these bounds to realistic scales. Some studies have focused on developing norm-based generalization bounds for complex network architectures, such as residual networks 24 Other studies investigated ways to reduce dependence the bounds on the product spectral norms 21 25 or to use compression bounds based on PAC-Bayes theory (26 27). or on the optimization procedure used to train the networks [19] 28 (9). However, most of this research centered around fully-connected networks, which generally underperform compared to other architectures like convolutional networks (30), residual network [ and transformers 4 31.. Thus, the ability of these bounds to explain the success of contemporary architectures is rather limited.
To fully understand the success of deep learning, it is necessary to analyze wider scope chitectures beyond fully-connected networks. An interesting recent direction [32] B3 introduces generalization bounds for neural networks with shared parameters, such as convolutional neural networks. For example, 32 showed that by taking into account the structure of the convolutional
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

layers, we can derive generalization bounds with a norm component smaller than the nomn of the associated linear transformation. However, many questions remain unanswered, including (a) Why certain architectures, such as convolutional networks (0) and MI.P-mixers [34, perform better than dully-connected neural networks? (b) Is weight sharing necessary for the success of convolu- tional neural networks? (c) Can we establish norm-based generalization bounds for convolutional neural networks that are reasonably tight in practical settings? In this paper, we contribute to an understanding of all three questions.
1.1 Related Work
Approximation guarantees for multilayer sparse networks. While fully-connected networks, including shallow networks, are universal approximators [35 36 of continuous functions, they are largely limited in theory and in practice. Classic results [37 38
41] show that, in the worst- case, the number of parameters required to approximate continuously differentiable target func- tions (with bounded derivatives) grows exponentially with the input dimension, a property known as the "curse of dimensionality".
39 40
A recent line of work 42 43 44 shows that the curse of dimensionality can be avoided by deep, sparse networks, when the target function is itself compositionally sparse. Furthermore, it has been conjectured that efficiently computable functions, that is functions that are computable by Turing machine in polynomial time, are compositionally sparse. This suggests, in turns, that, for practical functions, deep and sparse networks can avoid the curse of dimensionality. These results, however, lack any implication about generalization; in particular, they do not show that overparametrized sparse networks have good generalization.
Norm-based generalization bounds. recent thread in the literature 13 15 16
19
20 21 23 has introduced borm-based generalization bounds for neural networks. In particular, let S = {(r,. y4) 1m be a training dataset of m independently drawn samples from probability measure P defined on the sample space X' x y, where X' C R and y= = {=1]. A fully-connected (W"o(W ... )), where W RR xd: and
network defined as (x) = W (WL-Wo-
(x) is the element-wise ReLU activation function max(0, æ). A common approach for estimating the gap between the train and test errors of a neural network is to use the Rademacher complexity
of the network. For example, in 13 an upper bound on the Rademacher complexity is introduced
based on the norms of the weight matrices of the network of order O 2 I |W'| F). Later, [14
vmm
showed that the exponential dependence on the depth can be avoided by using the contraction lemma and obtained a bound that scales with OVVL).
While these results provide solid upper bounds on the test error of deep neural networks, they only take into account very limited information about the architectural choices of the network. In particular, when applied to convolutional networks, the matrices W represent the linear oper- ation performed by convolutional layer whose filters are w². However, since Wt applies w' to several patches (d, patches), we have ||W*|F Vdi
w |. As result, the bound scales with
O(v IT' di). that grows exponentially with L. This means that the bound not suitable for con- volutional networks with many layers as it would be very loose in practice. In this work, we establish generalization bounds that are customized for convolutional networks and scale with I || || instead of ||W'|/ IF.
In 455 they conducted large-scale experiment evaluating multiple norm-based generalization bounds, including those of [17 [4]. They argued that these bounds are extremely loose and nega- tively correlated with the test error. However, in all of these experiments, they trained the neural net- works with the cross-entropy loss which implicitly maximizes the network's 's weight norms once the network perfectly fits the training data. This can explain the observed negative correlation between the bounds and the error. In this work, we empirically show that our bounds provide reasonably tight estimations of the generalization gap for convolutional networks trained with weight normalization and weight decay using the MSE loss.
Generalization bounds for convolutional networks. Several recent papers have introduced gen- eralization bounds for convolutional networks that take into account their unique structure. In [23]. they introduced a generalization bound for neural networks with weight sharing. However, this bound only holds under the assumption that the weight matrices are orthonormal, which is not real-

---

istic in practice. In [331, they introduced generalization bounds for convolutional networks based on parameter counting. However, this bound scales roughly the square root of the ratio between the number of parameters and the number of samples, which is vacuous when the network is overparam- eterized. In 32,, they extended the generalization bounds of [7] for convolutional networks where the linear transformations W at each layer are replaced with the trainable parameters. While this paper provides generalization bounds which each convolutional filter contributes only once to the bound, it does not hold when different filters are used for different patches, even if their norms are the same. short, their analysis treats different patches as "datapoints" in an augmented problem where only one linear function is applied each layer. If several choices of linear functions (dif- ferent weights for different patches) are allowed, the capacity of the function class would increase. Although all of these papers offer generalization guarantees for convolutional networks, they base their findings either on the number of trainable parameters or on weight sharing. Notably, none of these studies directly address the question of whether weight sharing is essential for the effective generalization of convolutional networks. Furthermore, none provide empirical evidence to confirm that their bounds reasonably tight in practical settings. In our previous work [46], we derived generalization bounds using a technique similar to the one employed here. The results in this paper extend those preliminary results more general and more detailed formulation.
1.2 Contributions
In this work, we study the generalization guarantees of a broad class of sparse deep neural net- works [4)). such as convolutional neural networks. Informally, a sparse neural network is a graph of neurons represented as a Directed Acyelic Graph (DAG), where each neuron a function of a small set of other neurons. We show how simple modification to the classic norm-based generaliza- tion bound of [4] yields significantly tighter bounds for sparse neural networks (e.g., convolutional networks). Unlike previous bounds 33 32 47 our analysis demonstrates how to obtain general- ization guarantees for sparse networks, without incorporating weight sharing, while having a weak dependence on the actual size of the network. These results suggest that it is possible to obtain good generalization performance with sparse neural networks without relying on weight sharing. Finally, conduct multiple experiments to evaluate our bounds for overparameterizeed convolutional neural networks trained on simple classification problems. These experiments show that in these settings, our bound is significantly tighter than many bounds in the literature [14] 33 32 47). As result, this research provides a better understanding of the pivotal influence of the structure of the network's 's on its test performance.
architecture 30
34 2
2 Problem Setup
We consider the problem of training a model for classification. Formally, the task is defined by distribution P over samples (I, E X' x V, where X' C Reoxd is the instance space (e.g.. images), and y C RCC is a label space containing the C-dimensional one-hot encodings of the integers 1, I,...,C. C. When thinking about the samples as images, we view co as the number of in- put channels and do as the image size. We consider a hypothesis class F C {ff' : X' + R (e.g., a neural network architecture), where each function fo E F is specified by a vector of pa- rameters w E R.N (i.e., trainable parameters). A function far E F assigns prediction to an input point x E X, and its performance on the distribution P is measured by the expected error, (fr == P( [[maax
2 (w:)): where I (TTue, False} - {0. 1} be the indicator function (i.e., I[True] = 1 and vice versa). Since we do not have direct access to the full population distribution P. the goal to learn predictor, fw, from some training dataset independent and identically distributed (i.i.d)) samples drawn from P along with regularization to control fu 's complexity.
S = {2 mm of
2.1 Rademacher Complexities
We examine the generalization abilities of overparameterized neural networks by investigating their Rademacher complexity. This quantity can be used to upper bound the worst-case generalization gap (i.e., the distance between train and test errors) of functions from a certain class. It is defined as the expected performance of the class when averaged over all possible labelings of the data, where the
3

---

labels are chosen independently and uniformly at random from the set [+ In other words, it is the
average performance of the function class on random data. For more information, see [48 49 50
Definition 2.1 (Rademacher Complexity). Let FF be set of real-valued functions f X R defined over a set X. Given a fixed sample X E X²m,, the empirical Rademacher complexity of F is
defined as follows: Rx(F) (F)
in E
sup Σ 1==1 Er= (x)))
In contrast to the Vapnik- Cinnik---heroneniiis (VC) dimension, the Rademacher complexity has the added advantage that it can be upper bounded based on finite sample. The Rademacher complexity can be used to upper bound the gap between test and train errors of certain class of functions [48]. In the following lemma we bound the gap between the test error and the empirical margin error err' (fw) 1 Ei=1 (ffax)+y(ffxx:)) + 7 2 (Ti))y
Lemma 2.2. Let P be distribution over Rood x [C] and F C {f X RC). Let S { yb) ii=1 be a dataset of ii.dd samples selected from P and X = { Then, with probability least ô over the selection of S. for any SNo F, we have
2v2 (x) + +3
log (2/6)
erpp(Sw) - (Sw) S
2m
The above bound is decomposed into two parts; one is the Rademacher complexity and the second scales (LL//m) which is small when is large. In section 3 we derive norm-based bounds on the Rademacher complexity of sparse networks. This lemma and the rest of the mathematical statements are proven in the appendix.
2.2 Architectures
A neural network architecture can be formally defined using Directed Acyclic Graph (DAG) G EV. The class of neural networks associated with this architecture is denoted as FG. The set of neurons in the network is given by V f2'... 2',, }. which is organized into L layers. An edge (2f, 2 ) E E indicates a connection between a neuron in layer I - and a neuron in layer The full of neurons the layer (th is denoted by of == (z))
neural network fur Roxd - C takes "flattened" images x as input, where co is the number of input channels and do is the image dimension represented IR computes a vector of size c (the number of channels in layer t). To avoid confusion, in our definition, we think of each neuron
vector. Each neuron 2 Reo -
vector of dimension ct. This is analogous to a pixel holding three coordinates of RGB. The set of predecessor neurons of 2/. denoted by pred i), is the set of all j E [dc-1] such that (2/, 2 E E, and of == (2)))eped)(..) denotes the set of predecessor neurons of 2/. The network is recursively defined as follows:
de-1
Vr [C]: fo) =
Σ
(w 24
I.-1(2)) (x)).
where w/ E R 2x) = of (x)), / E (a-
a weight matrix,
x = (=)) each =x(x) is a vector of dimension co representing the jth "pixel" of x and a is the ReLU activation function. For simplicity, we denote w == W (wr)r..
The degree of sparsity of a neural network can be measured using the degree of the graph, which is defined as the maximum number of predecessors for each neuron. Specifically, the degree of a neural network architecture G given by: deg(G) = max deg(G)), where deg(G); = maxze(d] pred((,,) the maximal degree of the /th layer.
Convolutional neural networks. A special type of compositionally sparse neural networks is convolutional neural networks. In such networks, each neuron acts upon set of nearby neurons from the previous layer, using kernel shared across the neurons of the same layer.
To formally analyze convolutional networks, we consider broader set of neural network architec- tures that includes sparse networks with shared weights. Specifically, for an architecture G with [t, h for all j e [di]. define the set of neural networks Fith to consist of all neural

---

networks fo FG that satisfy the weight sharing property w' := " = = for all j1. E [di] and 1 [L.. Convolutional neural networks are essentially sparse neural networks with shared weights and locality (each neuron is function of a set of nearby neurons of its preceding layer).
Norms of neural networks. As mentioned earlier, previous papers (e.g.. (44) proposed different generalization bounds based different types of norms for measuring the complexity of fully- connected networks. One approach that was suggested by [14 is to use the product of the norms of the weight matrices given by p(w) == I ||..
In this work, derive generalization bounds based on the product of the maximal norms of the kernel matrices across layers, defined as: p(w) == || II maxxe[[j || where || ||r and is the Frobenius norm. For a convolutional neural network, we have simplified form of p(w) = Ih ||00"| due to the weight sharing property. This quantity is significantly smaller than the quantity p(w) || M V E = ||u 11 used by [14]. For instance, when weight sharing applied, we can see that p(w) = p(w) v MI di which is significantly larger than p(w)).
Classes of interest. In the next section, we study the Rademacher complexity of classes of compositionally sparse neural networks that are bounded in norm. We focus on two classes: Fa, = {s E Fa p(w) S p} and F = {s F p(w) S p}. where G is a composition- ally sparse neural network architecture and p is bound on the norm of the network parameters.
Theoretical Results
In this section, we introduce our main theoretical results. The following theorem provides a bound on the Rademacher complexity of the class FG.p networks of architecture G of norm S p. Proposition 3.1. Let G be neural network architecture of depth L and let O. Let X (.)) be a set of samples. Then,
Rx S
P m
2(
log(deg(G))) log(C))
max Jo
II
pred 50)
Σ I (x.
where the maximum is taken over Jus J1, ju. such that, ji-1 E pred ji) for all I [4].
The proof for this theorem builds upon the proof of Theorem presented in Section 3.1 As show next, by combining Lemma 2.2 and Proposition 3.1 we can obtain an upper bound on the test error compositionally sparse neural networks.
[4 A sketch of the proof is
Theorem 3.2. Let P be distribution over Reods {+1]. Let {(x;, y:))," be a dataset of i..d. samples selected from P. Then, with probability at least 5 over the selection of S, for any fa FG.
2 2v2(p(w) +1) 1+
(ee(fa)ccTille -
2(log(2)L +
log(deg( +og(()))))))
7/m
L-1
log(2(p(w) 2)2/0)
max J0
II
|pred(1, jill
Σ 11 (x.)l + 3v
2m
where the maximum is taken over jo. Jo. such that, ji-1 E pred(l, ji) for all E [T.].
The theorem above provides generalization bound for neural networks of a given architecture G. To understand this bound, we first analyze the term A maxjo....jzz I (t, ji) Σm |1=] (x.) We consider setting where do 2". a 1 and each neuron takes two neu- rons as input, k; == [pred([, = 2 for all I [L] and j E [d.. In particular, [[/-] hq = 2 and (x:) is the jth pixel of z,. Therefore, have A
de 2 mmxx, Σm || (z,))l² We
5

---

note that in the worst-case, when all of the norm ||=:||| is concentrated in the first pixel 2 (2ze, we have A du Ei= |1=:1l But in practice, the norms of the pixels 27;) are typically 2
more evenly distributed. For instance, we can assume that the pixels are 3-balanced. Meaning,
Vi E [m]] max)) [12] (a::)l² S 3 Avgje(as) (x;) = d ||:;| 2 (for some constant > 0). Note that the rate /3 a property exclusively dependent on the data as independent of the ar- chitecture and the training process. In particular, we obtain that A < - |0x||? In addition, we note that the second term in the bound is typically smaller than the first term as it scales with Vlog( Mlg((((w)) w)) instead of p(w) and has no dependence on the size of the network. Therefore, in this case, our bound can be simplified to O p(an) LB A Avvg-1lllll 1 [2])
Bounds for convolutional networks. As previously stated in section 2 convolutional neural networks utilize weight sharing across neurons in each layer, with each neuron in the äth layer having k input neurons (each of dimension 4-1)). The norm of the network is calculated as p(w) I [|w"||r, and the degree at each layer is simply the kernel size deg(G); = k.. This results in simplified version of the theorem.
Corollary 3.3 (Rademacher complexity of convolutional networks). Let G be neural network architecture of depth I, and let > Let = {ra) be a set of samples. Then,
h-1
Rx S L. (1+ m
2(1og(2) + Σ log(Is) + log(C))
max JE(da]
where kı denotes the kernel size in the I' l'th layer
Comparison with the bound of [14]. The result in Corollary 3.3 is a refined version of the analysis in [14] for the specific case of convolutional networks. Theorem in [14] can of course be applied to convolutional networks by treating their convolutional layers as fully-connected layers. However, this approach yields substantially worse bound compared the one proposed in Corollary 3.3
Consider a convolutional neural network G. The Ith convolutional layer takes the concatenation of ,+1 as its output. Each 2) is computed as (a(2)),.... (=2,)) as input and returns (2/+) ...... Adzi1 follows //+1 wit1 (1) (z)). Therefore, the matrix W associated with the convolutional layer contains d++1 copies of w and its Frobenius norm is therefore vdi+i ||//++|| ||-- In particular,
by applying Theorem 1 in 14 we obtain a bound that scales as O V II di Σm ||=: ||::1P) ))
On the other hand, we have
L-1 1=1 k S M di and [x:)]= & || Therefore, our bound is al- M di E. || which is the bound we obtained with [1].
ways smaller than O m
In particular, if each convolutional layer has ky di = 2T- and the bound of [14] would scale as ( /L205L(L-1) (lg==]l|=:13])) On the other hand, in our bound we have the term I[ ky = 2L-1, and therefore, our bound scales as o (T / /L24 Avg/=1ll<:(33) which is significantly smaller. Finally, as we discussed earlier, the norms of the pixels of each sample are 8-balanced (for some constant / > 0), our bound scales as o ALg [ [P] which is smaller by a factor of 20.251((1-1) than the bound of [4]
with no overlaps and do 24, then,
Comparison with the bound of 33 for convolutional networks based on parameter counting. This bound roughly scales like NO (=11=++oogg()>)+boggggl
recent paper 33 introduced generalization bounds
where y a margin (typically smaller than 1), and N is
m
the number of trainable parameters (taking weight sharing into account by counting each parameter of convolutional filters only once). While these bounds provide improved generalization guarantees when reusing parameters, it scales 22( 2(vNN/m) which is very large in practice. For example, the standard ResNet-50 architecture has approximately N = 23M trainable parameters while the MNIST dataset has only m 50000 training samples.
Comparison with the bounds of [32 and 47 Recent papers introduced generalization bound for convolutional networks based on covering numbers and weight sharing. For example,

---

f iwilla vm
the bounds in Theorem 17 of 32
roughly scale as O
B(w)
la
where E(w)
ky is the kernel size of the Ith layer and W is the matrix corresponding to the linear operator associated with the /th convolutional layer, wi, is the ith row of a matrix w, a is either 2 or 2/3, la L. if = 2 and la- o.w. and uf are "reference" matrices of the same dimensions as w'.
Σ
New 1
18.
11
1 1
In general, neither our bounds nor those in better in different cases. The main difference between their bounds and our bound, is that while their bounds include both multiplicative complexity term and additive complexity term, our bound includes only a multiplcative complexity term. For instance, the bound in Theorem 17 in (32 features both [ [w0' I|2 and E(w), whereas our bound exclusively contains the multiplicative term p(w) II== ||w" [p. For certain cases, this works in favor of our bound, but at the same time, our term I |/= || is comparably larger than Il || due the smaller norms used in the former. As an example of a case where our bound is superior, consider the case described after Theorem 3.2, where each convolutional layer operates on oonrrlpplgpinng patches of size and the channel dimension is I at each layer. We choose u' = 0 for all E [L- 1] (which is a standard choice of reference matrices). We notice that || = || = || ||r since W a block matrix and w'
32 and 47 are inherently superior; with each being
is a vector. In addition, for any matrix A, we have rank(A) > | 11l11 Z
2 I and rank(A) 2
||
TAll
||A|a max; l2. 2 1 (see
[7].. Therefore, the bound
32 scales as at least
I 1l'lla 3/22, while ym
I vT. which is smaller by factor of T.. bound scales as 11 Vm
uniform convergence bound for class F is an upper bound on the gen- eralization gap that uniformly holds for all f F. i.e., sup/EF (f errs (typically tends to 0 as m + oo). The Rademacher complexity bound in Lemma 2.2 is a form of uniform convergence bound. The issue with these bounds is that in interpolation regimes, where there exists a function f E FG that fits any labeling of the samples (a; [m uniform convergence bounds are provably vacuous.
Vacuous bounds?
f) I <(m, F)
While the derivation of the bound in Theorem 3.2 follows the application of Rademacher com- plexities, we emphasize that it is not uniform convergence bound and is not necessarily vacuous. Throughout the proof, we sliced the class Fo into subsets Fa.p = {f Fo p(w) I p} (for E N) and applied Lemma 2.2 for each of these subsets. This approach yields a bound that is proportional (p/ / /m) for each of the slices FG. We then apply union bound to combine all of them to obtain bound that scales as ((p(w)/ mm). (m)) This does not give uniform convergence bound across all members of FG, since the bound individualized for each member fw E FG based on the norm p(w). For example, for w = 0, the bound will be 0 which is non-vacuous.
When the learning algorithm minimizes p(w) and the minimal norm required to fit the training labels is small, a tight bound can be achieved with a network that perfectly fits the training data. For example, suppose we have a dataset S {(xi, y: ) a target function y/x) = (w" ,x), and a hypothesis class F = {(wra)) .)) w E R.d). A classic VC-theory bound scales as d//m)). which is vacuous when d >> m. However, norm-based bound scales as O[] /m). which is non-vacuous for any ||w]| < ||w=||| (as long as m > ||w*||3 In addition, the function can be realized by x)) ||w|| < [|w*[]] F. Specifically, for smaller ||w')|, I|, we need fewer samples to ensure that the bound is non-vacuous for minimal norm model that perfectly fits the training data.
3.1 Proof Sketch
We propose an extension to a well-established method for bounding the Rademacher complexity of norm- boundee deep networks. This approach, originally developed by [13], utilizes "peeling" argument, where the complexity bound for depth L. network is reduced to a complexity bound for a depth I, 1 network and applied repeatedly. Specifically, the lth step bounds the complexity bound for depth / by using the product of the complexity bound for depth layer. By the end of this process, obtain bound that depends on the term Egg(1 >m E,21))
and the norm of the ith
7

---

(g(z) = in [3 and exp in (14,, which can be further bounded using mxx,ex || The final bound scales with p(w) max,ex ||=||, Our extension further improves the tightness of these bounds by incorporating additional information about the network's 's sparsity.
To bound Rxx (Fa.p) using p(w), we notice that each neuron operates on small subset of the neurons from the previous layer. Therefore, we can bound the contribution of a certain constituent w in the network using the norm ||wr) r and the complexity of (x) instead of the full layer (xx) To explain this process, we provide proof sketch of Proposi- tion 3.1 for convolutional networks G = (V, E) with non-overlapping patches. For simplicity, we assume that dg = 2", q = 1, and the strides and kernel sizes at each layer are k 2. In par- ticular, the network Jw can be represented as a binary tree, where the output neuron is computed as (x) = 2/ (z) = wh
function (z)
22 - (x)). 21 (x) = -w--1 (2 (x)), 22 (x)) and
22 (x)) wo2-1.of (=2--21 - 24 (x:))
and so Similar to [14. first bound the Rademacher complexity using Jensen's inequality,
Eg sup exp ( [
mRx log exp
XEg sup Σ Exf((())) $ 1 log c=1
(2)
1=1
where À > 0 an arbitrary parameter. As a next step, we rewrite right-hand side as follows:
Be sup exp fm
ΣE & Su(ai))
m
Be exp fm
Σ &
m
w a (x.), 22 (x,)))
m
I Tg supexp
>
||w
||?
E o (x:))
(as))
fm
We notice that each 2 -xx is itself a depth L binary-tree neural network. Therefore, intuitively we would like to apply the same argument L more times. However, in con- trast to the above, the networks (2 (z)) (ww--11 (x| (x), 22 (x))) and (())-(())) (w²-=(<z =((=(())) end with ReLU activation. To address this issue, [3 proposed a "peeling process" based on Equation 4.20 in (5I) that can be used to bound terms of the form exp (a ||_ & (W f (x:)) However, this bound not directly applicable
Eg sup
/' ||
when there is a sum inside the square root, as in equation 3 which includes sum over j = 1,2. Therefore, modified peeling lemma is required to deal with this case.
snsilie-homogeneour activation functionn which is applied element-wise (such the ReLU). Then for any class of vector-valued functions
Lemma 3.4 (Peeling Lemma). Let be I-Lipschitz,
F C {ʃ- = (ff,..., Sg)) Vj E [g) Sj Rdd - TRP), and any corvex and monotonically increasing function R - 00).
m
E
S 2E
sup eehl, JEF
Σ E ((s))
FET Wy IESR
By applying this lemma times with = exp and f representing the neurons preceding a certain neuron at a certain layer, we can bound the term in equation 3 as follows:
m
< 2 E' sup exp 3.w
11
2
E1o0yy
< 2"
Be exp
A24/2p-
Σ
< 4' supexp
x A Im
x2
70
1
where the last inequality follows from standard concentration bounds (see the proof for details). Finally, by equation 2 and properly adjusting
can finally bound Rx (FG.p).
4 Experiments
In this section, we empirically evaluate the generalization bounds derived in section 3 In each experiment, compare our bound with alternative bounds from the literature. We focus simple
8

---

SHELL & 203
GIEEE 203
CUINCE 2013
2012
550
122
Eaoch
CONV-3-200
CONV-3-600
CONV-3-1000
Figure 1: Comparing our bound with prior bounds in the literature during training. We plot our bound, the train and test errors, the generalization gap, and prior bounds from the literature during training. For each plot, we train a CONV-L-H network on MNIST with a different number of channels H.
15
CONV-4-H
CONV-6-H
CONV-8-H
Figure 2: Varying the number of channels. We plot bound, the train and test errors, the generalization gap, and prior bounds from the literature at the end of training. For each plot, we train CONV-L-II network on MNIST with different number of layers L and channels H.
convolutional neural networks trained on MNIST and investigate the behavior of the bound when varying different hyperparameters. Each experiment was averaged across five runs. For additional experimental details, please refer to the appendix.
Network architecture. We used convolutional networks with L layers and H channels per layer denoted by CONV-L-H. The networks consist of stack of L 2x2 convolutional layers with a stride of I, O padding, and H output channels, utilizing ReLU activations followed by fully-connected layer. The overall number of trainable parameters is at least 4H + 4(T 1)H².
Optimization process. Each model was trained using SGD for MSE-loss minimization between the logits of the network and the one-hot encodings of the training labels. We applied weight nor- malization [52) to all trainable layers, except for the last one, which is left un-normalized. In order regularize the weight parameters, we used weight decay for each one the layers of the network with the same regularization parameter À > 0. To train each model, we used an initial learning rate of μ 0.01 that is decayed by a factor of 0.1 epochs 60, 100, 300, batch size 32, momentum of 0.9, and À = 3e-3 3 by default.
Experiments. We conducted several experiments compare bound to alternative bounds from the literature, when applied for neural networks trained on the MNIST dataset for classification. Throughout these experiments, inequality in Theorem 2.1 of [33], Theorem 16 of [32), and Theorem 3.5 in [47 (explicitly as
compared our bound the one in Theorem of [14], the third
mentioned in their Table 3). To compute the bound in 14 for multi-class classification, we adopted
modified version based on the technique we utilized in the proof of Proposition [31]] which allows us extend these bounds for multi-clate classification. Since [33 did provide an explicit value for their coefficient C. we assumed it to be 1. In the first experiment we trained three models of different widths for MNIST classification. As can seen Figure [ our bound significantly smaller than the alternative bounds and is surprisingly close to 1, indicating its tightness. In the second experiment, we compared our bound with alternative bounds from previous literature, focusing on convolutional neural networks with varying depths and widths. As can be seen in Figure 2
even as

---

GUEIE 201
CUIICE
CONV-L-200
CONV-L-600
CONV-L-1000
Figure 3: Varying the number of layers. We plot our bound, the train and test errors, the gener- alization gap, and prior bounds from the literature the end of training. For each plot, train CONV-L-H network on MNIST with a different number of layers L and channels H.
DOUPCTILLE 200
Salvactal 250
17
H1 200
H
600
1000
Figure 4: Varying the regularization coefficient A. We plot our bound. the train and errors, the generalization gap, and prior bounds from the literature at the end of 500 epochs. For each plot, we trained a CONV-3-R network on MNIST with a varying number of channels H.
networks become highly overparameterized at large widths, the width does not appear to influence the results of any of the bounds. In Figure 3 showease the results for convolutional networks of different depths. Our bound increases exponentially with depth but rises more slowly than the bound from [1). As an ablation study, in Figure we compared our bound with alternative bounds, this time varying the regularization coefficient X. It is evident that our bound and some alternative bounds decrease concurrently with the generalization gap of the neural network, desired outcome.
Conclusions
We studied the question of why certain deep learning architectures, such as convolutional networks and MLP-mixers, perform better than others on real-world datasets. To tackle this question, we de- rived Rademacher complexity generalization bounds for sparse neural networks, which orders of magnitude better than naive application of standard norm- based gencralization bounds for fully- results do not rely parameter sharing between filters, suggesting that the sparsity of the neural networks is the critical component to their success. This sheds new light the central question of why certain architectures perform so well and suggests that sparsity may be a key factor their success. Even though our bounds are practical in general, experiments show that they are quite tight for simple classification prob- lems, unlike other bounds based on parameter counting and norm-based based bounds for fully-connected networks.
connected networks. In contrast to previous papers B3
32
10

---

Acknowledgements
We thank Akshay Rangamani, Lorenzo Rosasco, Brian Cheung and Eran Malach for many relevant discussions. This material is based on the work supported by the Center for Minds, Brains and Machines (CBMM), funded by NSF STC award CCF-1231216. This work has also been sponsored by DOE SEA-CROGS project (DE-SC002319)).
References
[1] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Im- age Recognition. Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 16, pages 770-778. IEEE, June 2016.
[2] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representutions, 2021.
[3] Xiaohua Zhai, Alexander Kolesnikov, Neil Houlsby, and Lucas Beyer. Scaling vision trans- formers, 2021.
[4] Ashish Vaswani, Noam Shazeer, Niki Parmar. Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, volume 30. Curran Associates, Inc., 2017.
[5] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers). Association for Compu- tational Linguistics, jun 2019.
[6]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah. Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert- Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33. Curran Associates, Inc., 2020.
[7] David Silver. Aja Huang. Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panncershelvam, Mare Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mas- tering the game of Go with deep neural networks and tree search. Nature, 529:484 489, 2016.
[8] Kai Arulkumaran, Antoine Cully, and Julian Togelius. Alphastar: An evolutionary computa- tion perspective, 2019. cite arxiv:1902.01777
[9] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino. Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Car,, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code, 2021.
[10] Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.
11

---

[11] Chiyuan Zhang. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning requires rethinking generalization. In International Conference on Learning Representations, 2017.
[12] Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism interpolation. Acta Numerica, 30:203 248, 2021.
[13] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Peter Grünwald, 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.
[14] Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. Information and Inference: A Journal of the IMA, 9(2) 504, 05 2020.
[15] Peter L. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. J. Mach. Learn. Res., 2001.
[16] Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension bounds for piecewise linear neural networks. ArXiv, abs/ (os///703.0230, 2017..
[17] Peter L. Bartlett, Dylan Foster, and Matus Telgarsky. Opectrally-normalizee margin bounds for neural networks. In Advances in Neural Information Processing Systems, volume 30. Cur- ran Associates Inc., 2017.
[18] Behnam Neyshabur, Srinadh Bhojanapalli, David A. McAllester, and Nathan Srebro. A pac-bayesian approach to spectrally margin bounds for neural networks. ArXiv, hiss/707.095544 2018.
[19] Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks, 2019.
[20] Amit Daniely and Elad Granot. Generalization bounds for neural networks via approximate description length. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[21] Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation, 2019.
[22] Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang- Learning and generalization in overpa- rameterized neural networks, going beyond two layers. Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019.
[23] Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond, 2018.
[24] Fengxiang He, Tongliang Liu, and Dacheng Tao. Why resnet works? residuals generalize, 2019.
[25] Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep networks via generalizing noise-resilience. In International Conference Learning Representations, 2019.
[26] Wenda Zhou, Victor Veitch, Morgane Austem, Ryan P. Adams, and Peter Orbanz. Non- vacuous generalization bounds the imagenet scale: a PAC-bayesian compression approach. In International Conference on Learning Representations, 2019.
[27] Sanae Lotfi, Mare Anton Finzi. Sanyam Kapoor, Andres Potapczynski, Micah Goldblum, and Andrew Gordon Wilson. baC-bayes compression bounds tight that they can explain general- ization. In Advances in Neural Information Processing Systems, volume 35, Curran Associates Inc., 2022.
(28) Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine- line-erained analysis of optimization and generalization for overparameteriiee two-layer neural networks, 2019.
12

---

[29] Dominic Richards and Iija Kuzborskij. Stability & generalisation of gradient descent for shal- low neural networks without the neural tangent kernel. Advances in Neural Information Processing Systems, volume 34. Curran Associates Inc., 2021.
[30] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11)) 2324, 1998.
[31] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x 1616 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010.11929, 2020.
[32] Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 35(9))8279-88)) 8287, May 2021.
[33] Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural net- works. In International Conference Learning Representations, 2020.
[34] Uya O Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, and Alexey Dosovitskiy. Mip-mixer: An all-mlp architecture for vision. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neu- Curran Associates, Inc.,
ral Information Processing Systems, volume 34, pages 24261-24272 2021.
[35] George Cybenko. Approximation by superpasitions of a sigmoidal function. Mathematics of Control, Signals and Systems, 2(4):303-3) -3444, 1989.
[36] Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural Net- works, 4:251-257, 1991.
[37] Hrushikesh N. Mhaskar. Neural networks for optimal approximation of smooth and analytic functions. Neural Comput., 8(1):164-177, 1996.
[38] Vitaly Maiorov and Allan Pinkus. Lower bounds for approximation by mlp neural networks. NEUROCOMPUTING, 25:81-91, 1999.
[39] Vitaly Maiorov, Ron Meir, and Joel Ratsaby. On the approximation of functional classes equipped with a uniform measure using ridge functions. J. Approx. Theory, 99(1)95-111, 1999.
[40] Vitaly Maiorov. On best approximation by ridge functions. J. Approx. Theory, 99(1), 1999.
[41] Boris Hanin and Mark Sellke. Approximating continuous functions by relu nets of minimal width, 2017.
[42] Hrushikesh Mhaskar, Qianli Liao, and Tomaso Poggio. When and why are deep networks better than shallow ones? In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, AAAI' 17, page 2343-23443002 2349. AAAI Press, 2017.
[43] Tomaso Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks. Proceedings of the National Academy of Sciences, 117(48):30039-30045 2020.
[44] T. Poggio. Foundations of deep learning: Compositional sparsity of computable functions. CBMM memo 138, 2022.
[45] Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where to find them. In International Conference on Learning Representations, 2020.
[46] Mengjia Xu, Akshay Rangamani, Qianli Liao, Tomer Galanti, and Tomaso Poggio. Dynamics in deep classifiers trained with the square loss: Normalization, low rank, neural collapse, and generalization bounds. Research, 6:0024, 2023.
13

---

[47] Florian Graf, Sebastian Zeng, Bastian Rieck, Mare Niethammer, and Roland Kwitt. On mea- suring excess capacity in neural networks. In S. Koyejo. S. Mohamed, A. Agarwal, D. Bel- grave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, vol- ume 35, pages 10164-10178. Curran Associates, Inc., 2022.
[48] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learn- ing. MIT Press, Cambridge, MA, 2 edition, 2018.
[49] Shai Shalev-Shwarz and S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge eBooks, 2014.
[50] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482, 2002.
[51] Michel Ledoux and Michel Talagrand. Probability Banach spaces. Springer Berlin, Heidel- berg, 1991.
[52] Tim Salimans and Diederik P. Kingma. Weight normalization: A simple reparameterizzaioon to accelerate training of deep neural networks, 2016.
[53] Gábor Lugosi Stéphane Boucheron, Olivier Bousquet. Theory of classification: a survey of some recent advances. ESAIM: Probability and Statistics, 9:323-375, 3 2010.
[54] Tong Zhang. Statistical analysis of some multi-category large margin classification methods. J. Mach. Learn. Res., 5: 5:1225-1251, dec 2004.
[55] Ambuj Tewari and Peter L.. Bartlett. On the consistency of multiclass classification methods. Journal of Machine Learning Research, 8(36); 2007.
[56] Andreas Maurer. A vector-contraction inequality for rademacher complexities. Ronald Ortner, Hans Ulrich Simon, and Sandra Zilles, editors, Algorithmic Learning Theory, pages 3-17, Cham, 2016. Springer International Publishing.
[57] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inqqualities A Nonasymptotic Theory of Independence. Oxford University Press, 2013.
14

---

6 Limitations
Our work demonstrates how simple modification to the proof in 14 can yield tighter generaliza- tion bounds for convolutional networks. Empirically, we have observed that our bound is reasonably tight in basic learning settings (e.g., training 3-layer neural networks on MNIST), which promis- ing. However, this bound is anticipated to be generally loose for more complex learning settings. One drawback of our bound is its dependence on depth. For instance, our factor p(w) represents a product of L weight norms, which could increase as the depth L grows. Additionally, our bound contains a product I1 kg, which increases exponentially with depth. As demonstrated in sec- tion 3 this indicates that the bound is likely reasonable only when L depends logarithmically on the input's dimension. Consequently, our bound may not be suitable for very deep convolutional networks. Finally, building upon the analysis in [4], our bounds are specific to a certain class of ReLU neural networks and do not readily extend to architectures with different activation functions.
Broader Impact
This paper delves into the theoretical aspects of deep learning, specifically examining the reasons behind the strong generalization capabilities of sparse neural networks. Such insights may enrich understanding of the success of deep learning and specific architectures, such convolutional networks (30) and MIP-mixers 34. However, since this is a theoretical study, we do not anticipate any direct negative societal impacts stemming from research.
8 Additional Experimental Details
Compute. Each of the runs done using single GPU for at most 20 hours computing cluster with several available GPU types (e.g., GeForce RTX 2080, GeForce RTX 2080 Ti, Quadro RTX 6000, Tesla V-100, GeForee RTX A6000, A100, and GeForce GTX 1080 Ti).
Calculating our bound. Before discussing the calculation of the bound, let us first define how we model a convolutional neural network within the framework outlined in section 2
We focus ReLU convolutional networks which comprise fully-connected layer top of series of convolutional layers. The ith convolutional layer possesses a kernel size of kn- Each neuron in this 1th layer accepts ky neurons from its predecessor layer input (therefore its degree is deg(G); each with dimension Qt11, and outputs a single output node of dimension following the series of convolutional layers receives a set of kr nodes input (this represents the image resultant from applying multiple convolutional layers), where each node is of the output channel dimension of the previous layer. The output of this layer is of dimension
kj), The top linear layer
The bound derived in Theorem 3.2
of the main text can be written as follows:
2v2(p(w))
1)
1+
2(log(2)
log(deg(G))) + log log(C))
L-1 [pred(l,
log (2g(2(((w) + 2)2/5)
II
Σ 1 (m:)1 + 3v
max J0
2m
To compute this bound, we set 5 = 0.001 (the bound holds uniformly with probability 1 5) and 7 = 1. The norm p(w) is calculated as the product of the norms of each one the network's layers ||w"|[F. The norm of each of these layers simply the Frobenius norm of the kernel tensor of the layer. For the last fully-comnected layer we calculate the norm of the full weight matrix. For the ith convolutional layer, h = (1, (t)
deg(G)) is the kernel's size. For instance, if the layer is a 3 x 3 or 2 x 2 convolutional layer, the size is 9 or 4, respectively. It is worth noting that the bound independent of the size of the image ky that the fully-connected layer receives as input.
Finally, to calculate max Em 11 (I:) with ji-1 E pred(l,j(). It is important to note that this term is bounded by ja En (x:) where the maximum is taken over all input patches. To calculate this quantity, we sum the squared norms of the joth pixel across all samples and return the maximum value across all possible jo choices.
15

---

Proofs
Lemma 2.2. Let P be distribution over RRdd x [C] and F C {f X - R Let
S {(1,,)) 31) 1= be a dataset of i..d. samples selected from P and X {
Then, with
probability at least - 8 over the selection of for any fw F, we have
2V2 emr((fw) - efw)
12g(2/6)
(x) 3V
7
2m
Proof. By Lemma 3.1 in 17]. with probability at least d over the selection of for any fwo E F, we have
log (2/6)
emr((f>) -mn](sw) & (Rx + 3/
2m
where Fix = ( f fw E FF.. (u, = min(1, max(0, (0, + _M
the ramp loss function and M(u. = U2 - maxi4 u, (these quantities are standard [53 54 55 Next, by Lemma A.3 in 17 (M(())) is (2ps)-Lipschitz function. Hence, by Corollary in [56].
2v2
2v2
Rx S
E [(+
sup Σ (r)r tw 8,
Rx
ym
which completes the proof.
Lemma 3.4 (Peeling Lemma). Let be I-Lipschitz, positive-homogeneon activation function which is applied element-wise (such as the ReLU). Then for any class of vector-valued functions
F Cf (J1, (f1....,fa, Sq) Vj E [g] fg Rd + }R),, and any convex and monotonically increasing function R + [0, 00).
m
E ((x)) !)
E5g
sup FEF Wy: [1, ER
g
2E
sup 9 jelg), feJ
Vall
Σ
Proof. Let W E Rgxp be a matrix and let wi...., Wi be the rows of the matrix W. Define (iill f(x)))) taking vector v E IR. We notice that
function Qÿ(t) = Em & ol T
2
Σ
Σ & o oW (WFf(
Wwjr Σ
J Tee 110 fz(xa))
| (,(w)))
j=1 r=1
For any Wyl...., With we have
1 (,(w)) < R- max Q)(w,r),
(4)
16

---

which is obtained for u......., wih, where dess 0 for all * r" and Wrr- of norm R for some r" [h]. Together with the fact that g is monotonically increasing function, we obtain
(
Bgg
sup FEF Wg: WWyllsR Sa
& (WW5S1(2)))
Eg
sup fEJ
g
E [(w} f(a))))²
oo Mog? 112
S Eg
sup
9
Σ
& (w} 8o (xx))))
sElol. FEF
wy Ge Mig 1wyll2
& o(w s(aiiil)
Eg
sup
g
Vg.
jE(g). fET 1
Since g(|=1) S 9(2) + 9(-2),
Bg sup
9
Vq
Σ E ow
f [
%l(g). fEr ||
1=1
Eg
sup
V Σ
E aww f,(x))))
jElol. JEF 1
1
+ Eg
sup
-V
E: olw {s(xi)
%Elol. JEF 1wll-a
2Eg
V Σ
aw f1(31)))
jelo fer
wo 1=
where the last equality follows from the symmetry in the distribution of the & random variables. By Equation 4.20 in [51] and Cauchy- Schwa-s, we have the following:
Eg sup jelal fer 12
9
Σe
E (w [s(ii))
V9 Σ E.. B((a))
sup
eEly). JEF [[
1=1
m Σ SL0es)
Bg
sup
va |wll2
gl JEF |
m Σ & 15(rr)
E
VQR
JElo). feF
Proposition 3.1. Let G be neural network architecture of depth L. and let O. Let {m be a set of samples. Then,
Rx(FG.) S
P. m
2(1og(2) +
log(deg(()), log((T)
L-1
max Jo 1.
II
pred
Σ = (z.) l1.
where the maximun is taken over jo Iı ... Ir. such that, j-- E pred(l,ji) all [4].
17

---

Proof. We denote by fw an arbitrary member of Fe.p and w/ the weights of the jeth neuron of the Ith layer. Due the homogeneity of the ReLU function, each function fwr FG can rewritten
" as Sü, where th := I and for all 1 < L. and ji E [di], un max 1 In particular,
we have FG.p C Fa.. == (sw || & and vi < L. E [di] |las) ll I 1) since the ReLU function is homogeneous.
We first consider that
mR == mRx(Foo) = Be
sup
firf to (zi),
Eg
sup
Ex
11 2 (xi))
12-1
Eg
sup
Σ
Σ
Σ Ein
1--1 (zi)
10
JL-1 r=l
p Eg
sup max TJL-1
Σ Eir (axs)
where the last inequality follows from moving the norm of wi to the vector vi for maximizing
the term Enn E (w ric ,) DE S1r (x;) and applying the Sauchy-Schwarde inequality. Next, we apply Jensen's inequality.
Bg
sup i
Σ E
m L-1 (1r))
1
log Bg sup exp
A
Σ
m
Si iz
L-1 (szi)
7J6-1
1=1
1 log B sup judjn-1
Σ
m
Sinzt do (axs)
exp
where the supremum is taken over the weights un (1 E [L]. ji [d:)) that described above. Next, we use Lemma 3.4.
m
mR: < A
P log
Eg sup
exp
A
Σ
Eor
21 (scs)
1-1
p. log
Eg sup
exp
X
Σ
or
o
(w 1-
/// (z:1)
32
<
P log
2Eg sup
exp
Σ
Eo /
2-2 (xx1)
P. log
2Eg sup
exp
A
Σ
Σ Enr
a v (xx)) $1.2
X
j1. -1- Eppeel 2
l
P X
log
MEg
sup
exp
A
|pred([ - 1,
Σ Eor 1
1-3 (ars)
where the supremum is taken over the parameters of fa and ji E pred(L, L. jo). By applying this process recursively L times, we obtain the following inequality,
L-1
())
mR < L log π
2 max exp
A
pred(t.
Σ Eir 20 (1zi
(5)
18

---

where the maximum is taken over Jo...., Jr. such that, ji-1 E pred(l. and r E [C]. We notice that
Eg max
exp
A
(red j0l
Σ
for
230 (zi)
Be exp
A
(r)d
Σ Eir
20
(1+))
(6)
2
L-1 c deg(G))
m
max vJ00-.332
Eg exp
A
pred
Σ
Eir
20
(1rs)
Following the proof of Theorem in [4, by applying Jensen's 's inequality and Theorem 6.2 in [57 we obtain that for any > O,
Σ Eir 230 (ee)) S exp a²
1 (2x 11E
Eg exp
Σ 11 (=:)
(7)
2
Hence, by combining equations 7 with x v I1 (1, we obtain that
mR < x
P. log C'C II deg(G)r
Ee exp T.a...d
max
A
(t. jo]
Σ Sar 250 (axs)
L-1
L-1
m
P. max log
C II
deg(G)) Ee exp
A
(1.
>
Eir 20 (Ir:)
0
X
P. (log(2)L+ + 16-1 (oog(deg(Co) G)) log(()))
Ap max M pred(1. Em (x:)11 rJo
+ P
max jo
pred (1,
12% (1))
The choice A-
2(log (2) L+ 5
log Hog)
gives the desired inequality.
max 5o ...
[r))( E 11=% (x
Theorem 3.2. Let P be distribution over Roods {+1}. Let S {(x, y,)), be dataset of i..d. samples selected from P. Then, with probability least 8 over the selection of S. for any fw E Fc.
2 2V2(p(w) +1)
efrp(fx) (fn &
1+
2(log(2)L +
log(deg(G))) + log(())
ym
log(2(p(w)) + 2)²/6)
[pred(1, jill Σ 11 (x.))13 + +3
max Jowndd
2m
where the maximum is taken over ja ju, such that, ji-1 E pred ji) for all l E [4].
Proof. Let & (U (0) and G. Fa. By Lemma 2.2 with probability at least 1 7(+ for any
function for Gr, we have
2v2 Rx + +3
log(2/8)
cTTp(fw) - crrz(fww) 5
(8)
2m
19

---

By Proposition 3.1 in the main text, we have
2.
Rx(9))
1
2(log(2)L
log(deg(G))) log(C))
L-1 (r.
max Jo
|1 (z:))li.
because of the union bound over all E N. equation T hoold uniformly for all E N and fy E 9r with probability at least 1 ò- For each Jo with norm p(w) we then apply the bound with / = [m(w) since Su Gr, we have
2 ym
(fr((f)) - -( v
1+
2(log(2)L
log(deg(G)i) + log(C))
11 (ax) + +3/ log(2(t + 1)3/8)
II (t))
max
2m
< 2v 2v2(p(w) +1)
(2) log(deg(G))) + log(O))
mm
log(2(p(w)) 2)2/8)
max J0
(t.
1 (a.) + +3/
2m
which proves the desired bound.
20


Reviews:
[{"review_id": "CI2n7y6Lyw", "reviewer": "Reviewer_oZvZ", "summary": "This paper presents a generalization bound for sparse neural networks, such as convolutional networks. The bound is based on a Rademacher complexity bound derived with a layer-peeling argument. Empirically, the bound is shown to be non-vacuous for a 3 layer network trained on MNIST.", "questions": "**Interpretation of the bound.**\n\nCould you add a short paragraph after Proposition 3.1 which describes the different factors in the bound. Specifically, how should the maximum term inside the square root be interpreted? And, how does $z^0_{j_L}(x_i)$ differ from $x_i$?  \n\nMinor question: Its not entirely clear how to read the product. I guess it's $\\big( \\prod_l |\\mathrm{pred}(l,j_{L-1})| \\big) \\sum_i z(x_i)$ and not $\\big( \\prod_l |\\mathrm{pred}(l,j_{L-1})|  \\sum_i z(x_i) \\big)$\n\n**Comparison with prior work \\& scaling with depth.**\n\nThe paragraph starting at line 224 presents a comparison with [1] and shows that under specific architecture constraints, your bound is superior compared to [1] when applied to \nconv nets. What about the other direction? When applying both bounds to an MLP, will both bounds be equal? Is yours still better or is it even worse?\nAt first sight, it seems that your bound has a malign exponential scaling with the network depth via $\\prod_{l=1}^L |\\mathrm{pred}(l,j_{L-1})|$ and will be worse for deep networks.\n\nHow does this exponential scaling affect the comparison with [3]? You state that your bound has a \"*significantly better*\" (explicit) dependence on depth (cf. l.253).\nI also want to remark that one of the strengths of [3] is its benign scaling with the number of classes, which, as far as I see, Corollary 3 does not possess.\n\nI would like to see a comparison with the generalization bound (♣) for conv nets from [4]. Both seem to scale similarly with a product of norms and a log term that is related to the number of parameters. \nMoreover, the capacity reduction experiments in this reference are quite similar to your training procedure with a decomposition into weight direction and magnitude, only that lipschitz norms are controlled instead. Yet empirically the computed bound values in [4] are far from vacuous. I wonder why. Is it due to a strict better scaling of your bound? Or is it due to the training procedure, e.g., the network architecture or the mse loss?\n\nYou state that your bound and [3] \"*cannot be directly compared, with each being better in different cases*\". Could you specify such a setting where your bound is superior to [3] and [4]? As I already mentioned, I would like to see numerical values for the bounds from [1,2,3,4] in the MNIST experiment. Presumably, the MNIST experiment is already a setting where your bound is superior, but empirical evidence is needed.\n\n**Notation.**\nI did not understand the notation at the top of page 8 and in the proof of Proposition 5.3. What is $w^L \\cdot \\sigma (z^{L-1}_1(x), z^{L-1}_1(x))$ Is it \n$w^ \\cdot \\sigma (z^{L-1}_1(x)) + w^L \\cdot \\sigma (z^{L-1}_2(x))$?\n\n**Typo.** \n\"om\" in line 145.\n\n**References.**  \n\n[1] Golowich et al., Size-independent sample complexity of neural networks, COLT 2018  \n[2] Long & Sedghi, Generalization bounds for deep convolutional neural networks, IMCL 2020  \n[3] Ledent et al., Norm-based generalisation bounds for deep multi-class convolutional neural networks. AAAI 2021  \n[4] Graf et al., On Measuring Excess Capacity in Neural Networks, NeurIPS 2021  \n[5] Maurer,  A vector-contraction inequality for Rademacher complexities, ALT 2016\n", "limitations": "There is a section called \"limitations\" in the supplementary material, but therein, limitations are hardly discussed, only that the proposed bound \"is generally loose and may be vacuous for certain settings\". I think the opposite would have been more honest, i.e., that the bound is non-vacuous for certain settings but should be expected to be vacuous in general.\n\nA limitation of the bound is that it only holds for certain activation functions and thus is not applicable to many network architectures, e.g. AlexNet. This is not sufficiently emphasized in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This is a good paper with a strong contribution. As far as I know, it presents the first generalization bound based on Rademacher complexities that is non-vacuous on MNIST! However, I have some doubts (see weaknesses).\n\nThe paper is well written and easy to follow. The results are put into context and compared with prior work [1,2,3]. (For references see end of § Questions)", "weaknesses": "As already mentioned, I have doubt if the bound is really vacuous.  \n- The bound is evaluated on MNIST, i.e. a multi-class dataset. However, it seems that the bound only applies to binary classification (see Theorem 3.2). Extending the bound to multi-class settings can be done, for example with results from [5], but this yields an additional factor 10 = number of classes.\n- In the provided source code, the maximum pixel sum is computed on the raw data, whereas training occurs on a normalized version of the training data from the data loader. This omits a factor $1/\\sqrt{0.13} \\approx 2.7$.\n- Overall, this yields a factor of $\\approx 27$ which results in a (comparably small but) vacuous bounds again.\n- To clarify, even if the bound is vacuous, it still contributes a novel and significant contribution.\n\nComparisons with prior work is presented, but I have some additional questions, particularly regarding the scaling with network depth, which appears to be unfavorable in this work. See § Questions.\n\nThroughout the paper it is claimed that the derived bounds are (or may be) *orders of magnitude* smaller than existing ones. However, this is not supported by empirical evidence, as existing bounds are not computed in the experiments. A table which lists numerical values of the bounds from [1,2,3,4] evaluated on the models from the MNIST experiment together with a short discussion would be insightful.\n\nThe bound is limited to homogeneous elementwise activation function (e.g. ReLU) and thus cannot handle some popular network components such as pooling layers. This is a weakness that is shared by all bounds proven with a layer-peeling argument, so this is only a minor concern, as long as it is clearly communicated and pointed out that existing bounds for conv nets are not limited in this regard (e.g. [2,3,4]).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Reviewer: It seems that the bound only applies to binary classification…\n\nAnswer: It’s possible to extend the bound to multiclass with only a logarithmic dependence on the number of classes. We will add a proof in the next version of the paper and we carefully reproduced the experiments with the new factors in the bound. \n\nThe idea: We combine Lemma 3.1 in [1] with Corollary 4 in [2] with the multiclass margin loss from [1]. Finally, we only need to bound: $\\mathbb{E}\\_\\{\\epsilon} [\\sup\\_\\{f \\in \\mathcal{F}}\\sum\\_\\{i,j} \\epsilon\\_\\{i,j} f\\_\\{j}(x_i)]$, where $\\mathcal{F}$ is the set of neural networks of the form $Wg(x)$, where $g \\in \\mathcal{G}$ is a convolutional network as in the paper (with one output neuron with $c$ channels) and $W:\\mathbb{R}^{c} \\to \\mathbb{R}^{k}$ is a matrix of norm at most $\\alpha$. We can now use the top of page 31 in [3] to get a bound that scales with $\\log(k)$ instead of $k$. This process eventually leads to replacing $1+\\sqrt{2L\\log(2deg(G))}$ with $2\\sqrt{2}(1+\\sqrt{2L\\log(2deg(G)) + \\log(k)})$ in our bound.\n\n[1] Bartlett et al., Spectrally-normalized margin bounds for neural networks, NeurIPS 2017.\n\n[2] Maurer, A vector-contraction inequality for Rademacher complexities, ALT 2016.\n\n[3] T. Galanti et al., Generalization Bounds for Few-Shot Transfer Learning with Pretrained Classifiers, 2023.\n\n> Reviewer: In the provided source code… whereas training occurs on a normalized version…\n\nAnswer: We apologize for this honest mistake. We updated the code to take the normalization into account and reproduced our results.\n\n> Reviewer: ...numerical values of the bounds from [1,2,3,4] evaluated on the models from the MNIST experiment together with a short discussion would be insightful.\n\nAnswer: Following the reviews, we conducted multiple experiments to compare our bound with the bounds in [1,2,3,4]. Please refer to the comment to all of the reviewers for details and the pdf for the plots. According to these experiments, our bound is smaller than the bounds in [1,2,3,4].\n\nAs for the magnitudes, we referred to the VC dimension bounds, Golowich et al. 2018 and Long et al. 2020. The VC and the Long et al. 2020 bounds scale with the number of trainable parameters, which make the bounds very loose for realistic networks (see lines 238-245) . A naive application of the Golowich et al. 2018 bound to convnets gives additional factors that we were able to avoid (lines 62-70). We will make these statements more specific and supported by the new experiments in the next version of the paper.\n\n> Reviewer: Could you add a short paragraph after Proposition 3.1… different factors in the bound?\n\nAnswer: We will add more information about each term in the bound and about calculating the maximum.\n\n> Reviewer: Its not entirely clear how to read the product…  \n\nAnswer: It is indeed the former expression, we will add brackets.\n\n> Reviewer: The paragraph starting at line 224 presents a comparison with [1] … When applying both bounds to an MLP, will both bounds be equal?\n\nAnswer: The bounds are equal for MLPs. We can think of a fully-connected layer from $R^{n}$ to $R^{m}$ as a conv layer with kernel size 1x1, stride 1, $n$ input channels and $m$ output channels. The inputs and outputs of the layer are tensors of shapes $n\\times 1 \\times 1$ and $m \\times 1 \\times 1$. In our formulation, this means that the size of the predecessor set of the single neuron is 1 and the norm of the weight matrix is the norm of the linear transformation. Therefore, the bound conforms with the bound in [1]. \n\n> Reviewer: “How does this exponential scaling affect the comparison with [3]? You state that your bound has a \"significantly better\" (explicit) dependence on depth (cf. l.253)... benign scaling with the number of classes…”\n\nAnswer: We agree that our bound’s dependence on depth is not completely clear (e.g., it incorporates $\\rho$ which implicitly depends on depth). We would like to mention that this is not the main point of the paper, as the goal of this work is to demonstrate the role of sparsity in generalization. We are happy to remove this claim. Regarding the scaling with the number of classes - as discussed above, we will extend our analysis to the multiclass setting and prove that the dependence on the number of classes is logarithmic (see above). \n\n> Reviewer: ...comparison with the generalization bound (♣) for conv nets from [4]... Is it due to a strict better scaling of your bound? Or is it due to the training procedure…?\n\nAnswer: In [4] they trained the models with CE which tends to increase the norms of the weights of the network and eventually leads to large bounds. Following the reviews, we compared our bound with theirs in our setting (see attached pdf) and observed that their bound is still loose. Partially, because of their constants: when combining their Rademacher bound (in their page 18) and their Lemma 3.1 we obtain a generalization bound $8/n + 24\\log(n)/\\sqrt{n} \\cdot \\sqrt{\\log(W)} \\cdot (\\sum^{L}\\_\\{i=1} (4 (\\sup ||x||/\\gamma) \\cdot \\prod\\_\\{l\\neq i} s\\_l \\cdot ||K_\\{i}||\\_\\{2,1})^{2/3})^{3/2}$. For example, their bound is at least 150 even if $\\gamma=1$ and for each $i$, $ \\sup ||x|| \\cdot \\prod\\_\\{l\\neq i} s\\_\\{l} \\cdot ||K\\_\\{i}||_{2,1}$ is equal to 1 (which is typically larger), and $W=500,000$, $n=50,000$, $L=5$.   \n\n> Reviewer: I did not understand the notation at the top of page 8 and in the proof of Proposition 5.3.\n\nAnswer: It is computed as follows: $w^L \\cdot \\sigma(z^{L-1}_1,z^{L-1}_2) = w^L_1\\sigma(z^{L-1}_1)+w^L_2 \\sigma(z^{L-1}_2)$, where $w^L_i$ is the $i$th component of $w^L$.\n\n> Reviewer: There is a section called \"limitations\"…  the bound is non-vacuous for certain settings but should be expected to be vacuous in general… only holds for certain activation functions\n\nAnswer: We agree and we will make it more explicit in the next version of the paper. We will highlight the limitation to ReLU networks.\n"}, {"review_id": "FKEpihEgpG", "reviewer": "Reviewer_U2qE", "summary": "The paper provides a generalization bound for a class of neural networks that consist of sparsely connected neurons. The class includes the class of convolutional neural networks and networks with weight sharing.  \t\n* The generalization bound (Theorem 3.2) is based on Rademacher complexity analysis (Proposition 3.1) that builds mainly on the work of Golowich et al (“Size independent sample complexity…”) and Peeling lemma (Lemma 3.4).  The Peeling lemma from Golowich et al cannot be directly used as there is a sum inside the square root in (3).\n* The bound has linear dependence on the number of layers and depends on the product of the Frobenius norms of the kernel matrices (with the maximum taken per layer).  \n* The dimension dependence of the bound is via the notion of predecessor $\\text{pred}(l,i)$, which capture how the neurons are connected across layers. \n\n* As a conclusion, the authors provide a generalization bound for convolutional neural networks (Corollary 3.3).  \n* The experiments are done for MNIST and CIFAR-5m datasets, and for 4-layer convolutional networks. The main contribution of the paper is the generalization bound for sparse neural networks and its special case for convolutional networks.\n\nTo summarize, the paper considers an interesting setting, and the results provide interesting insights about the impact of neuron connectivity and channel dimensions. However, it seems to me that the authors can do a better job in supporting these claims experimentally, formulate their claims more precisely and report the limitations clearly. \n", "questions": "* I am curious about the connection of this paper with two other works (see below). Arora et al also consider convolutional neural networks, and their analysis applies as well to sparse neural networks. Vardi et al prove a bound on a single hidden layer convolutional neural networks that is dependent on the spectral norm of the kernel, better than the bound in the paper, and the patch overlaps. They also need only Lipschitz  functions, which is also more general than the paper. I think it is useful to include this discussion and add these references to the main paper.\n\n  * Arora, Sanjeev, Rong Ge, Behnam Neyshabur, and Yi Zhang. “Stronger Generalization Bounds for Deep Nets via a Compression Approach.” In International Conference on Machine Learning, 254–63, 2018.\n  * Vardi, Gal, Ohad Shamir, and Nati Srebro. “The Sample Complexity of One-Hidden-Layer Neural Networks.” Advances in Neural Information Processing Systems 35 (2022): 9139–50.\n\n## Comments and suggestions:\n* The paper assumes 1-Lipschitz, positive-homogeneous activation functions (Lemma 3.4). Please clarify this throughout the paper. \n* Adding a visualization of predecessor sets can be useful.\n* I feel that the results on approximation guarantees (page 2) are not related to the generalization error and just motivate the case for sparse networks. I suggest moving it to the introduction.\n* In page 2, it is mentioned that the MSE loss is used for training the network to get tighter bounds. The authors justify this choice by claiming that the weight norms are higher for “the cross-entropy loss which implicitly maximizes the network’s weight norms once the network perfectly fits the training data.” It would be good to add a reference for this, for instance:\n** Daniel Soudry  et al, The Implicit Bias of Gradient Descent on Separable Data, JMLR 2018\n* Lemma 2.2, which is Lemma 5.1, is quite standard. It would be enough to mention it in the supplementary materials. The proof is also quite standard and can be removed in my opinion. \n\n", "limitations": "\nThe authors addressed some of the limitations in the supplementary materials, although this can be done more clearly.\n", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper is in general well written (see my comments below). Obtaining non-vacuous generalization bounds for convolutional networks is an important and challenging topic. I find the formalization of DNNs as DAG is quite elegant and can model convolutional networks with their feature maps nicely. It is an interesting fact that the number of channels $H$ do not impact the bound (see Section 4.2 in the supplementary materials).", "weaknesses": "* Even if the predecessor set is minimally chosen to have the cardinality 2, the term $\\prod_{l=1}^L |\\text{pred}(l,j_{L-l})|=2^L$, which means exponential dependence on the number of layers. This issue is circumvented by assuming that the model is $\\beta-$balanced (see Page 6 – line 211-212), and assuming $d_0 = 2^L$. This is a strong assumption, since  $d_0$, which is purely data dependent, becomes architecture dependent. It does not seem to me that this assumption is satisfied in practice, and is just used to remove the exponential dependence on the number of layers. The choice needs more justification. \n* Note that in the plots, the term term $\\prod_{l=1}^L |\\text{pred}(l,j_{L-l})|$ is ignored, and only $\\rho(w)/\\sqrt{m}$ is plotted. Therefore, the claimed tightness and non-vacuity can be questionable. \n* The proof seems to be a straightforward modification of the proof in Golowich et al, where only the Peeling lemma is updated. It seems to me that the technical novelty of the proof is limited, and the contribution lies mainly on the extension to the new case of sparse networks. This is fine, if the authors could provide better experiments. The considered architecture and datasets are simpler than what is typically tried in the generalization literature (see for example [44]; or in [17], AlexNet for cifar10 is considered). The message of the paper can become more compelling with better experiments.\n* The plots only show the correlation between the generalization error and the bound. To show that the true generalization error does indeed scale with $\\prod_{l=1}^L |\\text{pred}(l,j_{L-l})|$, it is good to have additional experiments.\n* I wonder about the message of Figure 2. The training and test errors saturate rapidly, and the plotted bound (red curve) does not seem to capture the correlation with the true generalization error (Figure 2  on supplementary materials seems to be even worse in terms of correlation). This might be because the true generalization error is already too small, and the authors might want to look for better visualizations.\n* There are certain imprecise statements in the text that harm the overall presentation. For example, it is claimed that the bound is “quite tight”, although it is not clear how the tightness is measured and with respect to which baseline this judgment is formed. As another example, in the abstract it is claimed that “these bounds may be orders of magnitude better than standard norm based generalization bounds”, although no numerical comparison with many existing norm based bounds is done. Also the claim about the bound being non-vacuous is not always true based on the numerical results.  Admittedly, these limitations are addressed in the supplementary materials, Section 1. It might be a good idea to transfer this to the main part. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Reviewer: “Even if the predecessor set is minimally chosen… the model is $\\beta$-balanced (see Page 6 – line 211-212), and assuming $d_0=2^L$. This is a strong assumption, since $d_0$, which is purely data dependent…”\n\nAnswer: Just to clarify, it is not the model that is assumed to be balanced but the data is balanced. The choice of $d\\_\\{0}=2^L$ is purely technical. This example would work perfectly with any other choice of $d_0$ and kernel size $k$. For example, we can still take $L=\\lceil log\\_k(d\\_0) \\rceil$ and kernel sizes $k$ with the last layer being fully connected. Then $\\prod^{L}\\_\\{l=1} k\\_l =k^{L-1}$, each term $z_{j}$ will be a patch of $k$ pixels. There are $\\lfloor d\\_\\{0}/k \\rfloor = k^{L-1}$ such patches. Therefore, we have $\\max_\\{j}\\sum_\\{i}||z\\_\\{j}(x_i)||^2 \\cdot  k^{L-1} \\leq \\beta \\cdot \\sum\\_\\{i}||x_i||^2$ assuming the patches are $\\beta$-balanced. \n\n> Reviewer: “Note that in the plots, the term $\\prod^{L}\\_\\{l=1} pred(l,j\\_\\{L-l})$ is ignored, and only $\\rho/\\sqrt{m}$ is plotted…”\n\nAnswer: We plotted the full bound as it is described in Theorem 3.2, including the above term (see line 351). \n\n> Reviewer: “The proof seems to be a straightforward modification… technical novelty of the proof is limited…” \n\nAnswer: Our contribution is more conceptual than technical. 1. We demonstrate that the compelling derivation of Golowich can be expanded to convnets in a simple way, by incorporating sparsity. 2. This reveals a relationship between sparsity and generalization, that we believe could be significant for learning theory. 3. Through our experiments, we reveal that the previously deemed loose bounds are in fact tighter than anticipated. These bounds were originally evaluated for models trained with cross-entropy, which is a case where the norms of the weight matrices tend to grow. However, when training with MSE, the bounds are actually reasonable (in the sparse, i.e. convolutional, case).\n\n> Reviewer: This is fine, if the authors could provide better experiments... see for example [44]; or in [17], AlexNet for cifar10 is considered…\n\nAnswer: It is difficult to experiment with off-the-shelf architectures (AlexNet) mostly because they incorporate layers that are difficult to handle with theory (e.g., pooling, dropout). Therefore, we took a vanilla architecture that we could easily analyze. It is worth noting that we still experimented with architectures of different sizes and depths and with CIFAR10 as in [17]. The goal of the experiments is to show that the bounds start to be reasonable in simple settings.\n\n> Reviewer: The plots only show the correlation between the generalization error and the bound... scale with $\\prod^{L}\\_\\{l=1} pred(l,j_\\{L-l})$...\n\nAnswer: As mentioned above, throughout the experiments we calculated the full bound in Theorem 3.2. Furthermore, the goal of this paper is not to introduce the bound as a metric that can faithfully predict generalization. After all, there are much better ways to measure generalization than to derive generalization bounds. The goal of introducing this bound is to learn something about the relationship between sparsity and generalization, which is reflected in this bound. \n\n> Reviewer: I wonder about the message of Figure 2… This might be because the true generalization error is already too small…\n\nAnswer: Indeed, the generalization gap appears fluctuating when plotted on logarithmic scales, primarily due to its comparatively smaller size relative to the other terms. However, it is actually quite flat and correlated with the other lines.\n\n> Reviewer: There are certain imprecise statements in the text… although no numerical comparison with many existing norm based bounds is done.\n\nAnswer: When mentioning that our bounds are orders of magnitude smaller than existing ones, we mainly referred to bounds based on VC dimension and to the classic bound of Golowich et al. 2018, Long & Sedghi 2020. Following the reviews we conducted multiple experiments to verify that our bound is much smaller in practice compared to multiple bounds from the literature (see the comments for all of the reviewers and the attached pdf file). We will tone down these statements, and make them more specific and supported by the new experiments.\n\nThe VC and the Long & Sedghi 2020 bounds scale with the number of trainable parameters, which make the bounds very loose for realistic networks (see lines 238-245). As we discussed in lines 62-70, a naive application of the Golowich et al. 2018 bound to Convolutional neural networks gives additional undesired factors to the bound that we were able to avoid. We will make it clearer in the next version of the paper.\n\n> Reviewer: Also the claim about the bound being non-vacuous… Admittedly, these limitations are addressed in the supplementary materials, Section 1. It might be a good idea to transfer this to the main part.\n\nAnswer: We are happy to make it more explicit in the main text. \n\n> Reviewer: I am curious about the connection of this paper with two other works (Arora, Vardi)...\n\nAnswer: We are happy to add these references along with discussions of these papers. Arora et al.’s paper presents a different type of bounds that apply to compressible networks. In essence, if a neural network is compressible then it is expected to have better generalization guarantees. While this work is relevant in fashion, it does not directly provide a fundamental distinction between fully-connected and convolutional networks. Looking at their bound in Tab. 1, it seems to be much looser than ours in practice. Regarding Vardi et al.'s paper, their findings seem to be similar in fashion to ours. However, as pointed out, their bound is only applicable to single-layer networks, which is considerably limiting. \n\n> Reviewer: comments and suggestions.\n\nAnswer: Thank you very much! We will incorporate all of the suggestions (e.g., visualization of processor sets, moving text, citing Soudry, etc'). \n"}, {"review_id": "8mF9QphyL1", "reviewer": "Reviewer_LtGn", "summary": "This work proposes an adaptation of Radamacher complexity analysis for deep neural networks specifically suited to those that are compositionally sparse, as in convolutional architectures. The authors characterize the specific model parametrization by a directed acyclic graph, and provide an upper bound to the Radamacher complexity of neurons that have only a few parents. By adapting the required lemmas to these cases, the authors provide a bound on the generalization gap that scales better with the norm of the weights for convolutional networks. Lastly, the authors demonstrate their bounds in practice for a couple of cases (CIFAR and MNIST).", "questions": "I liked this paper, and enjoyed reading it very much. \n\n1. My main concerns regard the authors depiction of the scaling of their bound with the depth of the network, L: when discussing the implications of theorem 3.2 (main result), the authors conclude that their bound is $\\mathcal O( \\rho \\sqrt{ L \\beta / m})$, and they therefore comment that their bound has a mild dependency on depth $O(\\sqrt{L})$. While I might be missing something, to my understanding this is incorrect for two independent reasons: \n\n    a) the bound on the network norm, $\\rho$, scales exponentially with $L$ in general (line 185). It is true that we don’t know what the correct scaling for this norm is, but since this norm is the product of Frobenius norms (of the filters), the only way for $\\rho$ not to grow exponentially with $L$ is for these norms to decrease exponentially with $L$. Naturally, this is not a reasonable assumption (unless the authors can demonstrate this numerically). Their bound, like all other works based on Radamacher complexities, have an exponential dependence on L.\n\n    b) on line 212, the authors explain that for some \"constant\" $\\beta$, one can upper bound $\\prod^L k_l max_j \\sum_m ||z_j(x_i)||^2 \\leq \\beta \\sum_m ||x_i||^2$. I do not believe it is possible for this upper bound to hold for a constant beta (i.e., $\\beta$ that is independent of $L$), right? If $L$ increases, then necessarily $\\beta$ should increase (and exponentially so) for the bound to hold.\n    \n    Therefore, by presenting their overall bound as $O( \\rho \\sqrt{ L \\beta / m})$, the dependence on L seems incorrect. I’d be happy to learn what I am missing if I'm incorrect about these points above.\n    \n\n1. The inclusion of numerical results that evaluate the obtained bounds is highly appreciated. While it is true that these bounds seem interesting and beginning to be reasonable, they do not provide non-vacuous bounds as stated in the abstract. I believe this should be rephrased. Indeed, in the conclusions the authors do mention, accurately, that their bounds are not yet practical.\n\n1. I am curious about how the authors choose the value for the network norm, $\\rho(w)$, in order to evaluate their bound. As presented, in Theorem 3.2, this value characterizes the hypothesis class and is fixed (i.e. chosen independent of data). In the experiments, the authors mention that they control the value of this norm via regularization, and obtain trained model $w*$. But then, what value for $\\rho(w)$ is chosen at the end to instantiate the bound? Naturally, the value $\\rho(w*)$ cannot be chosen, as it is data dependent. Alternatively, the authors could extend their results to hold uniformly over the choice of $\\rho$, but this comes at the expense of an additional statistical cost (which I don’t believe the authors are taking into account). Could you clarify?\n\n 1. The authors have done a reasonable job of comparing with existing literature in generalization theory. However, the sensitivity analysis/(modified layer-peeling process) bares resemblance to prior work (such as Singla et al) that studies the Lipschitz constant of convolutional networks. I encourage the authors to cite these works as well.\n\n2. The authors contend that the computed bounds are non-uniform as they rely on the norm-based measure $\\rho(w)$. However, the bounds *are* uniform for all similarly norm-bounded networks. This presents a limitation of the Rademacher analysis as the worst-case deviation between networks with $\\rho(w) < \\rho*$ could be much larger than the generalization gap of the trained predictor. While this phenomena is not specific to this work, I would encourage the authors to include/contextualize this in their discussion of vacuous bounds.\n\n**Smaller observations and typos:**\n\ni) In Eq.(1), the (-0.5) exponent should be (0.5).\n\nii) The numerical results (Figs 1 and 2) seem out of place on Page 5. Please move closer to Sec. 4.\n\niii) \\mathcal{F}_G should be \\mathcal{F}_{G,\\rho} in line 204\n\niv) It’s unclear to me why the authors stress so much that their bounds also hold when the network perfectly fits the data. This is true, but not particularly enlightening given that the networks they use, in practice, do not.\n\nv) “we rewrite right-hand” → “we rewrite the right-hand..”\n\nvi) The sentence “Furthermore, since our bound…” seems incomplete.\n\nvii) In the last sentence of their paper, the authors state that “..our experiments show that they are quite tight for simple classification problems, unlike other bounds based on parameter counting, suggesting that the underlying theory is sound and does not need a basic reformulation.” I have troubles with this, since every paper that states “this theory will never need a reformulation” is wrong. It’s clear that this paper makes some nice contribution to understand generalization in deep networks, but the claim seems an exaggeration (e.g., it suffices to note that the bounds are still vacuous!).\n\nviii) Subjective: The notation z_j^l(x) is a bit unnatural to me, as z_j^l was defined as node in a DAG instead of a function of the input. Maybe a footnote would clarify this.\n\nix) in line 127, the authors colloquially defined the Radamacher complexity of a function class as “the expected performance of the class on random data”. I understand that this is just a colloquial description, but it’s not quite accurate: this notion of complexity measures the *maximal* correlation of any function in the function class to random labeling of the empirical sample. \n\nx) line 145: “om” → “on”?\n\nxi) line 134: “the Rademacher complexity has the added advantage that it is data-dependent and can be measured from finite samples.” This is incorrect (unless the authors can solve the maximization over all f in the function class). What the authors likely meant is that it can be upper bounded based on a finite sample.", "limitations": "Their limitations have received little attention. It would be beneficial to expand on these. For example, their bounds (as they do mention) are not yet practical. What do the authors recognize as the main limitation in their analysis that prevents this from hapening?", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The majority of the generalization bounds for neural network does not make explicit use of the structure in convolutional filters, and this paper seeks to fill this important gap\n- The numerical evaluation of their bounds is highly appreciated\n- The writing and presentation are clear", "weaknesses": "- To my understanding, some claims are overstated or incorrect (see below).\n- Some further numerical evaluation would support their claims better (see below).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Reviewer: “the bound on the network norm, $\\rho$, scales exponentially with $L$ in general (line 185)... since this norm is the product of Frobenius norms (of the filters), the only way for $\\rho$ not to grow exponentially with $L$ is for these norms to decrease exponentially with $L$...”\n\nAnswer: We agree that $\\rho$ could potentially grow exponentially with $L$. The main contribution of the paper is not to improve the dependence of generalization bounds on depth, rather to better understand the role of sparsity in generalization. Just to note, $\\rho$ does not necessarily either grows exponentially with $L$ or the weight norms decay exponentially with $L$. For example, $\\rho \\approx e$ when each layer  is norm $(1+1/L)$.\n\n> Reviewer: “on line 212… \"constant\" $\\beta$, one can upper bound $\\prod^L k_l \\max_\\{j} \\sum_\\{i} ||z_\\{j}(x_\\{i})||^2 \\leq \\beta \\sum_\\{i} ||x_i||^2$. I do not believe it is possible for this upper bound to hold for a constant $\\beta$”\n\nAnswer: The constant $\\beta$ is designed to be independent of $L$. Specifically, it evaluates the highest ratio between the norm of the most intense pixel and the average pixel norm within an image. As this measure solely relies on the training samples and is not associated with the network architecture, it doesn't depend on $L$. We'll make sure to clarify this point in the next version of our paper.\n\n> Reviewer: While it is true that these bounds seem interesting and beginning to be reasonable, they do not provide non-vacuous bounds as stated in the abstract. I believe this should be rephrased. Indeed, in the conclusions the authors do mention, accurately, that their bounds are not yet practical.\n\nAnswer: Indeed, we do not argue that the bounds are practical at this point and agree that they are beginning to be reasonable. We will rephrase these statements to make it clearer that the bounds are not yet practical.\n\n> Reviewer: “I am curious about how the authors choose the value for the network norm, $\\rho(w)$, in order to evaluate their bound… but this comes at the expense of an additional statistical cost (which I don’t believe the authors are taking into account)...”\n\nAnswer: The norm $\\rho(w)$ is actually not fixed in Theorem 3.2. For each function $f_w$ we have a different norm $\\rho(w)$ without selecting $\\rho$ before seeing the data. Therefore, by selecting $w$ dependent on the data, $\\rho(w)$ could very much also be dependent on the data. To do so, we used a simple trick that is often repeated in the literature (see the proof of Lemma A.9 in Bartlett et al. 2017, pages 22-23). This comes with a minor cost (the bound scales with $\\rho+1$ instead of $\\rho$).\n\nThe idea is as follows: for each positive integer $t$, we combine Lemma 2.2 and Proposition 3.1 for $\\rho=t$, $\\mathcal{F}\\_{G,\\rho}=\\mathcal{F}\\_{G,t}$ and $\\delta\\_t = \\delta/(t(t+1))$ (see Eqs. 6-7 in the Appendix). This gives us a bound that holds for all functions of norm at most $t$. By taking union bound across all $t \\in \\mathbb{N}$, these bounds hold simultanously with prob $\\geq 1-\\delta = 1-\\sum_{t}\\delta/(t(t+1))$. Then, (with probability at least $1-\\delta$) for each $f_w$ any bound with $t \\geq \\rho(w)$ should hold. We choose the bound with $t=\\lceil \\rho(w) \\rceil \\leq \\rho(w)+1$. Then, with probability at least $1-\\delta$, for each $f_w$, the inequality in Theorem 3.2 holds.  \n\n> Reviewer: “... the sensitivity analysis/(modified layer-peeling process) bares resemblance to prior work (such as Singla et al)... I encourage the authors to cite these works as well.”\n\nAnswer: We are happy to cite and discuss these papers.\n\n> Reviewer: “The authors contend that the computed bounds are non-uniform as they rely on the norm-based measure $\\rho(w)$. However, the bounds are uniform for all similarly norm-bounded networks…”\n\nAnswer: Please refer to the comment above about adjusting the bounds to depend on $\\rho(w)$ instead of a pre-selected $\\rho^*$.\n\n> Reviewer: Multiple typos.\n\nAnswer: We will incorporate these suggestions in the next version of the paper.\n\n> Reviewer: It’s unclear to me why the authors stress so much that their bounds also hold when the network perfectly fits the data. This is true, but not particularly enlightening given that the networks they use, in practice, do not. \n\nAnswer: We will remove these statements.\n\n> Reviewer: “In the last sentence of their paper, the authors state that… does not need a basic reformulation...”\n\nAnswer: We agree and will remove this statement.\n\n> Reviewer: “in line 127, the authors colloquially defined the Radamacher complexity of a function class as “the expected performance of the class on random data”... not quite accurate…”\n\n> line 134: “the Rademacher complexity has the added advantage that it is data-dependent and can be measured from finite samples.” This is incorrect…\n\nAnswer: We agree and will modify these statements accordingly.\n\n> Reviewer: “Their limitations… For example, their bounds… not yet practical…. main limitation in their analysis…”\n\nAnswer: We will expand on the limitations section. The goal of this work in not to provide a quantitatively good estimator of generalization. After all, there are much better ways to estimate generalization. The main goal is to better understand the role of sparsity in generalization, the success of convolutional networks and whether weight sharing is necessary or not.\n\nWhile improving the bounds could be a challenging, we think that these bounds could be improved by thinking of ways to replace the Frobenius norms with spectral norms or smaller types of norms. Another approach could be deriving bounds that are data-dependent. Most of the bounds in the literature measure the “worst case” norm of the learned function quantified by the product between the complexity of the function (e.g., $\\rho(w)$) and the largest norm of a training sample (e.g., $\\sup ||x||$). This could be potentially relaxed by quantifying the complexity of the network on the specific training data.\n"}, {"review_id": "88jJ7koc3j", "reviewer": "Reviewer_dgpJ", "summary": "The authors present a bound on the Rademacher complexity of sparse neural networks, which include in particular convolutional neural networks. This bound improves over previously-known bounds for CNNs, and applies more broadly since it does not assume weight sharing, but only sparsity. The bounds are illustrated by numerical experiments.", "questions": "+ Line 124 (and elsewhere in the paper): you mention that you study the overparametrized regime, but your bounds hold independently of the under/overparameterization. I suggest to rephrase to avoid confusion.\n+ Lines 126-129: the interpretation of Rademacher complexity is misleading. It is not the expected performance of the class, but of the worse case error in the class. This is very different.\n+ Line 161: shouldn’t it be v_i^l and pred(l, i) instead of v_i^{l-1} and pred(l-1,i)? To fit with the definition of v_i^l two lines above.\n+ Line 197 and 205: I find the numbering of j_1 … j_L extremely confusing, I think it would be much more intuitive to reverse the order, in order to make pred(l, j_l) appear in the formula instead of pred(l, j_{L-l}). There is a related issue in the proof, line 134 of the Appendix, I believe it should be j_{L-l+1} instead of j_{l+1}. Also, an explanation on what’s going on (and a drawing?) would be most welcome. You’re basically enumerating the paths in the graph from the input to the output, right?\n+ Lines 261 to 282: ok, but I believe these explanations are not specific to your bound, but are true for any norm-based bound. This should be written more explicitely.\n+ Line 274: I don’t think the bound of Theorem 3.2 is equal to 0 if rho(w)=0? Could you elaborate on this?\n", "limitations": "See weaknesses.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper tackles the important question of the understanding of the advantages of the convolution structure from a statistical point of view. The proposed bounds improve over known bounds by leveraging modern proof techniques for the Rademacher complexity of deep neural networks. The paper is well-written and easy to follow. I checked the proofs partially, and the mathematical details are globally well-written as well.", "weaknesses": "I am not convinced by the numerical experiments as they are, because I do not think they back the claim of the authors on the tightness of their generalization bound. There are several orders of magnitude between the bound and the reported generalization gap. Of course, I am well aware of the difficulty of decreasing this spread, but I think it would be interesting to complement the experiments to prove the point by\n+ reporting the value of other generalization bounds in the same setting, in order to illustrate that the proposed bound is indeed tighter than others. \n+ varying the amount of regularization (I guess, the lambda parameter) described in lines 334-342. If rho(w) does indeed play a role in the generalization power of the neural network, I think you should observe a negative correlation between the regularization strength and the generalization gap. This would be more interesting than just reporting the value of rho(w) as in Figure 1, since this value in itself does not have a strong meaning.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Reviewer: reporting the value of other generalization bounds in the same setting, in order to illustrate that the proposed bound is indeed tighter than others. \n\nAnswer: Following the reviews we conducted multiple experiments to compare our bounds with other generalization bounds for convnets that were suggested by the reviewers. We consistently observe that our bound is much tighter than the other bounds. Please refer to the comments to all of the reviewers for details and the pdf for the plots.\n\n> Reviewer: varying the amount of regularization (I guess, the lambda parameter) described in lines 334-342. If rho(w) does indeed play a role in the generalization power of the neural network, I think you should observe a negative correlation between the regularization strength and the generalization gap. This would be more interesting than just reporting the value of rho(w) as in Figure 1, since this value in itself does not have a strong meaning.\n\nAnswer: Following the reviews, we conducted multiple experiments to validate this correlation. We observe that when increasing $\\lambda$, our bound decreases (since $\\rho$ decreases) as well as the generalization gap.\n\n> Reviewer: Line 124 (and elsewhere in the paper): you mention that you study the overparametrized regime, but your bounds hold independently of the under/overparameterization. I suggest to rephrase to avoid confusion. \n\nAnswer: We agree and will rephrase it accordingly.\n\n> Reviewer: Lines 126-129: the interpretation of Rademacher complexity is misleading. It is not the expected performance of the class, but of the worse case error in the class. This is very different. \n\nAnswer: We agree and we willl correct this issue in the next version of the paper.\n\n> Reviewer: Line 161: shouldn’t it be $v^l\\_\\{i}$ and $pred(l, i)$ instead of $v^{l-1}\\_\\{i}$ and $pred(l-1,i)$? To fit with the definition of $v^l\\_\\{i}$ two lines above.\n\nAnswer: Yes, we will fix it in the next version of the paper.\n\n> Reviewer: Line 197 and 205: I find the numbering of $j\\_1 … j\\_L$ extremely confusing, I think it would be much more intuitive to reverse the order, in order to make $pred(l, j\\_l)$ appear in the formula instead of $pred(l, j\\_{L-l})$. There is a related issue in the proof, line 134 of the Appendix, I believe it should be $j\\_{L-l+1}$ instead of $j\\_{l+1}$. Also, an explanation of what’s going on (and a drawing?) would be most welcome. You’re basically enumerating the paths in the graph from the input to the output, right?\n\nAnswer: We will reverse the order for simplicity and yes we are essentially enumerating the paths. \n\n> Reviewer: Lines 261 to 282: ok, but I believe these explanations are not specific to your bound, but are true for any norm-based bound. This should be written more explicitly. \n\nAnswer: We will make it more explicit in the next version of the paper.\n\n> Reviewer: Line 274: I don’t think the bound of Theorem 3.2 is equal to 0 if rho(w)=0? Could you elaborate on this?\n\nAnswer: That’s true, the bound in Theorem 3.2 would not be zero. It is a honest mistake since the bound in Corollary 3.3. We will fix this issue in the next version of the paper. \n"}, {"review_id": "4KVzQict0R", "reviewer": "Reviewer_G4im", "summary": "This paper presents the derivation of generalization bounds for sparsely connected neural networks. The authors extend the peeling arguments to establish a bound on the Rademacher complexity of these networks based on the number of connections between each neuron and its predecessors and norms of the network weights. The proposed bound is then applied to the specific case of Convolutional Neural Networks (CNNs), and the authors validate their bounds through experimental evaluations.", "questions": "1) Is it possible to adapt the proof technique to mitigate or eliminate the exponential dependence on $\\rho(w)$ (e.g.,  Lipschitz augmentation techniques mentioned in [1])?\n\n2) Can the explicit dependence on the filter size (number of connections) be replaced with an implicit dependence, for example, through incorporating weight norms? \n\n[1] Wei, C., & Ma, T. (2019). Data-dependent sample complexity of deep neural networks via Lipschitz augmentation. Advances in Neural Information Processing Systems, 32.\n", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) The paper demonstrates a clear and well-structured writing style.\n2) The related work is thoroughly cited, indicating a comprehensive understanding of the existing literature.\n3) The extended approach presented in the paper is interesting. ", "weaknesses": "1) The provided bounds exhibit exponential scaling in the network depth, even when disregarding the exponential dependence of $\\rho(w)$ on depth. \n\n2) The nature of the bound shares similarities with parameter counting bounds, as it explicitly relies on the number of connections between each neuron and its predecessors (e.g., filter size in CNNs). This explicit dependence remains present even if the learned network deviates minimally from its initialization.\n\n3) In comparisons of related work, the authors use unrealistic cases to demonstrate the superiority of their approach. For instance,  input dimension is 2^L, filter size =2.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> Reviewer: The provided bounds exhibit exponential scaling in the network depth, even when disregarding the exponential dependence of $\\rho(w)$ on depth. \n\n> The nature of the bound shares similarities with parameter counting bounds, as it explicitly relies on the number of connections between each neuron and its predecessors (e.g., filter size in CNNs). This explicit dependence remains present even if the learned network deviates minimally from its initialization. \n\nAnswer: While it may initially seem that our bound displays a dependence on parameter counting, we want to highlight that it is not always the case. In traditional norm-based bounds (e.g., Golowich et al., Bartlett et al.) the bounds typically scale with $(C(w) \\cdot \\max\\_i||x\\_{i}||)/\\sqrt{m}$, where $C(w)$ represents a measure of complexity (e.g., the product of the norms of the weight matrices). In our setting, we do introduce an additional term $\\prod^{L}\\_{l=1} k\\_{l}$, but rather than taking the maximal norm over the samples, $\\max\\_{i}||x\\_{i}||$, our bound scales with the maximal norm over patches, $\\max\\_{i,j}||z\\_{j}(x\\_{i})||$. \n\nAs we discuss in lines 224-237, if the patches within the various samples are relatively balanced and non-overlapping, then $\\sqrt{\\prod^{L}\\_{l=1} k\\_{l} \\cdot \\max\\_{i,j}||z\\_{j}(x\\_{i})||^2}$ is proportional to $\\max\\_{i}||x\\_i||$. Consequently, what might initially appear as an exponential dependence on depth via $\\prod^{L}\\_{l=1} k\\_{l}$ is not accurate because $\\max\\_{i,j}||z\\_{j}(x_i)||^2$ is much smaller than $\\max\\_{i}||x\\_{i}||^2$. Then, the only thing left to differ between our bound and Golowich’s bound is the notion of complexity $C(w)$. In our bound it measures the product of the norms of the parameter kernels at the various layers and in Golowich’s bound it is the product of the norms of the linear transformations associated with the convolutional layers. As we discuss in lines 62-70, this is significantly larger than our measure of complexity.\n\n> Reviewer: In comparisons of related work, the authors use unrealistic cases to demonstrate the superiority of their approach. For instance, input dimension is $2^L$, filter size =2.\n\nAnswer: The choice of $d_\\{0}=2^L$ is purely technical to illustrate the scales of the bound with respect to depth $L$. However, the same logic holds for an arbitrary choice of $d_\\{0}$ and any kernel size $k$. For example, we can still take a network with $L_0=\\lfloor log\\_\\{k}(d_0) \\rfloor$ convolutional layers with kernel sizes $k$ and multiple fully connected layers on top of them. Then, $\\prod^{L_0}\\_\\{l=1} k\\_\\{l} =k^{L_0}$, each term $z_\\{j}$ will be a patch of two pixels. There are $\\lfloor d_\\{0}/k \\rfloor = k^{L_0}$ such patches. Therefore, we have $\\max\\_\\{j}\\sum\\_\\{i}||z\\_\\{j}(x_i)||^2 \\cdot  k^{L_0} \\leq \\beta \\cdot \\sum\\_\\{i}||x\\_i||^2$ assuming the patches are $\\beta$-balanced.\n\n> Reviewer: Is it possible to adapt the proof technique to mitigate or eliminate the exponential dependence on $\\rho(w)$ (e.g., Lipschitz augmentation techniques mentioned in [1])? \n\nAnswer: That would be a very interesting future direction. Generally speaking, relaxing the dependence on Frobenius norms would be useful for making our bounds more practical. However, at this point we are not sure if it would be possible because the results in [1] rely on analyzing the covering number of the function class in order to derive a bound for the Rademacher complexity. Our analysis, on the other hand, relies on a repeated application of the peeling lemma without using covering numbers.  \n\nRegarding the scaling of $\\rho(w)$, we agree that it could potentially exponentially grow with $L$. However, it is not necessarily the case. Suppose we have $L-1$ layers with norms $(1+1/L)^{2}$ and one layer of norm $5(1+1/L)^{2}$, then $\\rho \\approx 5e^2$. \n\n> Reviewer: Can the explicit dependence on the filter size (number of connections) be replaced with an implicit dependence, for example, through incorporating weight norms?\n\nAnswer: It would be a very interesting research direction to explore to what extent we can replace the filter sizes with an implicit dependence. We think that one could potentially relax the dependence on the size of the predecessor set by taking into account the norm of the connections with the neurons in the predecessor sets. At least it might be possible to avoid counting neurons in predecessor sets if their weights are very small. However, it is still something we are exploring and has yet to be formalized.\n\nWe would like to reiterate that despite the existence of the term $\\sqrt{\\prod^{L}\\_{l=1} k\\_{l}}$, our bound also scales with $\\max_{i,j}||z_{j}(x_i)||$ instead of $\\max\\_{i}||x\\_{i}||$. As we discussed above, in some cases (see lines 224-237), the expression $\\max\\_{i}||x\\_{i}||$ scales as $\\sqrt{\\prod^{L}\\_{l=1} k\\_{l}}$ times the expression $\\max_{i,j}||z_{j}(x_i)||$. In such cases, $\\sqrt{\\prod^{L}\\_{l=1} k\\_{l} \\cdot \\max\\_{i,j}||z\\_{j}(x_i)||^2}$ is proportional to $\\max\\_{i}||x\\_{i}||$ and the bound scales as $\\rho(w) \\cdot \\max\\_{i} ||x\\_\\{i}||/\\sqrt{m}$ which is independent of the filter sizes.\n"}]

Author rebuttal:
We would like to thank all of the reviewers for their valuable time and feedback. Following the reviews we conducted several experiments to address the comments about the empirical results. Please see the attached pdf file for the plots.

Throughout the experiments, we compared our bound with several prior bounds appearing in [1,2,3,4]. We calculated the bounds for multiclass classification with 10 classes (with the additional factor depending on the number of classes that we added following the comments of reviewer oZvZ) and with margin $\gamma=1$ across all of the experiments for simplicity. We note that in [2] they did not explicitly mention their coefficient $C>0$ in their bound. We tried to calculate $C$ but it was very difficult as it relies on applying a complicated analysis from [5] (where constants are also not given). To compare with [2] we simply assumed $C=1$, even though we expect it to be larger than 1.

[1] Golowich et al., Size-independent sample complexity of neural networks, COLT 2018 

[2] Long & Sedghi, Generalization bounds for deep convolutional neural networks, ICML 2020 

[3] Ledent et al., Norm-based generalization bounds for deep multi-class convolutional neural networks. AAAI 2021 

[4] Graf et al., On Measuring Excess Capacity in Neural Networks, NeurIPS 2021

[5] Giné and Guillo, On consistency of kernel density estimators for randomly censored data: rates holding uniformly over adaptive intervals. In Annales de l’IHP Probabilités et statistiques, volume 37, pages 503–522, 2001.

Figure 1 (a): A convolutional network trained on MNIST. Following the comments of reviewers oZvZ, U2qE, dgpJ, we compare our bound with [1,2,3,4] when varying the width of the network. As can be seen, our bound is largely unaffected by increasing the width, while the bounds in [1,2,4] generally increase with the width (especially [1]). This is a very nice advantage of the bound because increasing the width grows the number of trainable parameters.

Figure 1 (b): Following the comments of all of the reviewers, we investigated the effect of depth on the various bounds. As can be seen, similar to [1,3,4], our bound seems to grow with the depth of the network. As mentioned in the responses to the reviewers, the focus of this paper is to extend the compelling derivation of Golowich to convolutional networks by incorporating sparsity, to reveal a relationship between sparsity and generalization, and to show that our bound is reasonable in practice. However, it would definitely be interesting to relax the dependence of this bound on depth as future work. 

Figure 2: Following the suggestion of reviewer dgpJ, we studied the correlation between different bounds and the generalization gap when varying $\lambda$. As can be seen, both the generalization gap and our bound decrease when increasing $\lambda$.

Figure 3: For completeness, we also plotted the bounds during training when considering the setting of Figure 2 with $\lambda=3e-3$.


Meta-review: This paper presents an interesting theoretical analysis of Rademacher complexity bounds for deep sparse neural networks. The reviewers agree that the theoretical contributions are solid, providing new bounds that leverage network sparsity and have the potential to improve upon previous results.

However, there are concerns about the empirical evaluation of the bounds and some of the resulting conclusions. In particular, there appear to be errors in numerically estimating the bounds that affect comparisons to prior work. This calls into question statements about the tightness of the bounds and their ability to be non-vacuous in practice.

I believe the core theoretical results are sound and provide value to the community's understanding of generalization bounds for sparse networks. However, the authors need to address the issues raised regarding the experiments and revise any overstated conclusions based on those results. Given the high quality of the theory, I recommend conditionally accepting the paper pending revisions to the empirical methodology and tempering of the conclusions.

Specifically, the authors should carefully re-evaluate the bound computations and comparisons to prior works, address any errors, and revise the conclusions accordingly. Claims about the tightness of the bounds and their non-vacuousness need to be qualified based on the corrected calculations. The limitations discussed regarding uniform convergence bounds should also be acknowledged.

With these revisions, I believe the paper will make a solid contribution. I recommend acceptance pending modifications to the experiments and conclusions.
Decision: Accept (poster)