The Sample Complexity of One-Hidden-Layer Neural Networks
Authors: Gal Vardi
Ohad Shamir
Nathan Srebro
Venue: NeurIPS 2022 Accept (2022)
Keywords: Sample complexity
one-hidden-layer neural networks
Rademacher complexity

Abstract: We study norm-based uniform convergence bounds for neural networks, aiming at a tight understanding of how these are affected by the architecture and type of norm constraint, for the simple class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We begin by proving that in general, controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees (independent of the network width), while a stronger Frobenius norm control is sufficient, extending and improving on previous work. Motivated by the proof constructions, we identify and analyze two important settings where (perhaps surprisingly) a mere spectral norm control turns out to be sufficient: First, when the network's activation functions are sufficiently smooth (with the result extending to deeper networks); and second, for certain types of convolutional networks. In the latter setting, we study how the sample complexity is additionally affected by parameters such as the amount of overlap between patches and the overall number of patches. 

The Sample Complexity of One-Hidden-Layer Neural Networks
Gal Vardi
Ohad Shamir
TTI Chicago and Hebrew University" galvardi@ttic.ed.
Weizmann Institute of Science
ohad. shamir@weizmm ac il
Nathan Srebro
TTI Chicago nati@ttic.edi
Abstract
We study norm-based uniform convergence bounds for neural networks, aiming a tight understanding of how these are affected by the architecture and type of norm constraint, for the simple class of scalar-valued one-hidden-layer networks, and inputs bounded in Euclidean norm. We begin by proving that in general, controlling the spectral norm of the hidden layer weight matrix is insufficient to get uniform convergence guarantees (independent of the network width), while stronger Frobenius norm control is sufficient, extending and improving on previous work. Motivated by the proof constructions, identify and analyze important settings where (perhaps surprisingly) a mere spectral norm control turns out to be sufficient: First, when the network's activation functions are sufficiently smooth (with the result extending to deeper networks); and second, for certain types of convolutional networks. In the latter setting, we study how the sample complexity is additionally affected by parameters such as the amount of overlap between patches and the overall number of patches.
Introduction
Understanding why large neural networks able to generalize is of the most important puzzles in the theory of deep learning. Since sufficiently large neural networks can approximate any function, their success must be due to strong inductive bias in the learned network weights, which is still not fully understood.
A useful approach to understand such biases is studying what types of constraints the network weights can lead to uniform convergence bounds, which ensure that empirical risk minimization will not lead to overfitting, Notwithstanding the ongoing debate whether uniform convergence can fully explain the learning performance of neural networks [Nagarajan and Kolter, 2019, Negrea et al., 2020, Kochler al., 2021], these bounds provide with important insights what norm- based biases can potentially aid in generalization. For example, for linear predictors, it is well- understood that constraints the Fuclidean norm of the weights imply uniform convergence guarantees independent of the number of parameters. This indicates that minimizing the Fuclidean norm (without worrying about the number of parameters) is often useful inductive bias, whether used explicitly or implicitly, or whether uniform convergence formally holds or not for some specific setup. However, neural networks have more complicated structure than linear predictors, and still lack a good understanding of what norm-based constraints imply a good inductive bias.
Work done while the author was at the Weizmann Institute of Science
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we study this question in the simple case of scalar-valued one-hidden-layer neural networks. which generally compute functions from IR to R of the form x ++ u a (WW), with weight matrix W Rnxd, weight vector u, and a fixed (generally non-linear) activation function a. We focus on an Euclidean setting, where the inputs x and output weight vector v are assumed to have bounded Euclidean norm. Our goal is to understand what kind of norm control on the matrix W is required to achieve uniform convergence guarantees, independent of the underlying distribution and the network width n (i.e., the number of neurons). Previous work clearly indicates that a bound on the spectral norm is generally necessary, but (as we discuss below) does not conclusively imply whether is also sufficient.
Our first contribution (in Subsection 3.1) is formally establishing that spectral norm control is generally insufficient to get width-independent sample complexity bounds in high dimensions, by directly lower bounding the fat-shattering number of the predictor class. On the flip side, if we assume that the Frobenius norm of W is bounded, then we can prove uniform convergence guarantees, independent of the network width or input dimension. The latter result is based on Rademacher complexity, and extends previous results (e.g., [Neyshabur et al., 2015, Golowich et al., 2018], which crucially required homogeneous activations) to general Lipschitz activations. In Subsection 3.2, we also prove a variant of our lower bound in the case where the input dimension is fixed, pointing at a possibly interesting regime for which good upper bounds are currently lacking.
The constructions used in these lower bounds crucially require activation functions which are non- smooth around 0, and arbitrary weight matrices W with bounded norm. Motivated by this, we identify and analyze two important settings where (perhaps surprisingly) these lower bounds can be circumvented, and where mere spectral norm control is sufficient to obtain width-independent guarantees:
The first case (studied in Sec. 4) is for networks where the activation function a is sufficiently smooth: Specifically, when it is analytic and the coefficients of its Taylor expansion decay suffi- ciently rapidly. Some examples include polynomial activations, sigmoidal functions such as the error function, and appropriate smoothings of the ReLU function. Perhaps surprisingly, the mere smoothness of the activation allows us to prove uniform convergence guarantees that depend only on the spectral norm of W and the structure of the activation function, independent of the network width. Moreover, we can extend our results for deeper networks when the activations is a power function (e.g., quadratic activations).
A second important case (studied in Sec. 5) is when the network employs weight-sharing on W, as in convolutional networks. Specifically, we consider two variants of one-hidden-layer convolutional networks, one with linear output layer, and another employing max-pooling. In both cases, we present bounds on the sample complexity that depend only on the spectral norm, and study how they depend on the convolutional architecture of the network (such as the number of patches or their amount of overlap).
Our work leaves open quite a few questions and possible avenues for future research, which we discuss in Sec. 6. For lack of space, all proofs of our results appear in the appendix.
Related Work
The literature on the sample complexity of neural networks has rapidly expanded in recent years, and cannot be reasonably surveyed here. In what follows, we discuss only works which deal specifically with the issues we focus on in this paper.
Frobenius vs. spectral norm Control, lower bounds. Fat-shattering lower bounds for neural networks were developed in Anthony and Bartlett [1999], but involve size or dimension dependencies rather than norm control. Bartlett et al. [2017] proved lower bound on the Rademacher complexity of neural networks, implying that a dependence on the spectral norm is generally necessary. Golowich et al. [2018] (0 extended this to show that a dependence on the network width is also necessary, if only the spectral norm controlled. However, their construction requires a rector-valuee (rather than scalar-valued) output. More importantly, the lower bound is on the Rademacher complexity of the predictor class rather than the fat-shattering dimension, and thus (as we further discuss below) does not necessarily imply that the actual sample complexity with some bounded loss function indeed suffers from such width dependence. Daniely and Granot [2019] do provide a fat-shattering lower bound, which implies that neural networks Rd with bounded spectral norm and width at most

---

d can shatter (2d²²) points with constant margin, assuming that the inputs have norm at most vd. However, this lower bound does not separate between the input norm bound and the width of the hidden layer (which both scale with d), and thus does not clarify the contribution of the network width to the bound. Moreover, their proof technique appears to crucially rely on the input's s norm scaling with the dimension, rather than being an independent parameter.
Frobenius vs. spectral norm control, upper bounds. A width-independent uniform convergence guarantee, depending on the Frobenius norm, has been established in Neyshabur et al. [2015] for constant-depth networks, and in Golowich al. [2018] for arbitrary-depth networks. However, these bounds are specific to homogeneous activation functions, whereas we tackle general Lipschitz activations (at least for one-hidden layer networks). Bounds based on other norms include Anthony and Bartlett [1999]. Bartlett et al. [2017]. Liang [2016], but are potentially more restrictive than the Frobenius norm, or do not lead to width-inndeendeene. Also, we note that the bound of Bartlett et al. [2017] has the nice property of depending on the distance to some fixed reference matrix, rather than the norm itself. However, we do not pursue this generalization here as is not the focus of our work.
Sample complexity with smooth activations. The Rademacher complexity for networks with quadratic activations has been studied in Du and Lee [2018], but assuming Frobenius norm constraints, whereas we show that mere spectral norm constraint is sufficient to bound the Rademacher complexity independent of the network width. The strong influence of the activation function on the sample complexity has been observed in the context of VC-dimension bounds for binary classification (see Anthony and Bartlett [1999, Section 7.2D.. However, we are not aware of previous results showing how the smoothness of the activation functions provably affects scale-sensitive bounds such as the Rademacher complexity in our setting.
Sample complexity of convolutional networks. Norm-based bounds for convolutional networks (including more general ones than the one we study) have been provided in Du et al. [2018]. Long and Sedghi [2019]. However, these bounds either depend on the overall number of parameters, or apply only average-pooling. For convolutional networks with max-pooling, Ledent et al. [2021] provide norm- norm-based analysis which we build on (see Sec. 5 for details). Cao and Gu [2019] showed an
sample complexity of learning mne-hidden-layee layer convolutional networks with non-overiapping filters and general activation functions. Additional works studying the generalization performance of convolutional networks in settings different than ours include Li et al. [2018), Arora et al. (201 8), Wei and Ma [2019], Hsu et al. [2020], Brutzkus and Globerson [2021].
2 Preliminaries
Notation. We use bold-face letters to denote vectors, and let [m] be shorthand for (1...., m]. Given a matrix M, Mr. the entry row and column j. Given a function (-)) on IR we somewhat abuse notation and let (x) (for vector x) or or (M) (for matrix M) denote applying element-wise. A special case when (-) H++ = maxt-; 0} is the ReLU function. We use standard big-Oh notation, with 2(.). (-), (-) hiding constants and 2(.). @()), Ō()) hiding constants and factors polylogarithmic in the problem parameters.
Norms. - denotes the operator norm: For vectors, is the Euclidean norm, and for matrices, the spectral norm (i.e., || = supx:||xi =1 [|. || ||r denotes the Frobenius norm (i.e., ||]]]
V EE, Mf, ). It is well-known that for any matrix M, ||M]| S ||M[|r so the class of matrices whose Frobenius norm is bounded by some B is subset of the class of matrices whose spectral norm is bounded by the same B. Moreover, if M is
x d matrix, then || || / //min(n, d].
Network Architecture. Most of our results pertain to scalar-valued mee-hddee--layer networks, of the form x + u (Wx), where x E Rd, W E Ruxd, u is a vector and or-) is some fixed non-linear function. The width of the network is n, the number of rows of W (or equivalently, the number of neurons in the hidden layer of the network).
Fat-Shattering and Rademacher Complexity, When studying lower bounds on the sample com- plexity of a given function class, we use the following version of its fat-shattering dimension:
Definition A class of functions on an input domain X shatters m points (xx) ) S X with margin if there exist number s, such that for all y {0, n we can find some E F such that
3

---

for all i E [m], f(x.) S s = 0 and f(x)) 2 c = 1. The fat-shattering dimension of F (at scale E) is the cardinality m of the largest set of points in X for which the above holds.
is well-known that the fat-shattering dimension lower bounds the number of samples needed to learn in a distribution-free learning setting, to accuracy (see for example Anthony and Bartlett [1999, Part III. Thus, by proving the existence of large set of points shattered by the function class, we get lower bounds on the fat-shattering dimension, and thus on the sample complexity.
As to upper bounds complexity of a function class F. which for our purposes can be defined as (F)
the sample complexity,
results utilize the Rademacher
(xp CX Ee Ju m > [x))([[( where 6 (e1:-..,f6y fm) is vector of m independent random variables e, uniformly distributed on {-1,+1). Upper bounds on the Rademacher complexity directly translate to upper bounds the sample complexity required for learning F: Specifically, the number inputs m required to make (F) smaller than some e is generally an upper bound on the number of samples required to learn F. up to accuracy using any Lipschitz loss (see Bartlett and Mendelson [2002]. Shalev-Shwartz and Ben-David [2014], Mohri et al. [2018]). We note that Rademacher complexity bounds can also be easily converted to margin-basse based bounds (where the 0 - 1 classification risk is upper-bounded by the proportion of margin violations the training data) by considering a composition of the hypothesis class with an appropriate ramp loss (which upper bounds the 0-1 loss and lower bounds the margin loss, as was done for example in Bartlett and Mendelson [2002], Bartlett et al. [2017]).
We note that although the fat-shattering dimension and Rademacher complexity of the predictor class closely related, they do no always behave the same: For example, the class of norm-bounded linear predictors (x + (w, x) w E Rd ||w/| S B} has Rademacher complexity O(B/ vm), implying O (((B/e)²) samples to make less than In contrast, the fat-shattering dimension of the class is smaller, e (min [B/e)²]) [Anthony and Bartlett, 1999, Bartlett and Mendelson, 2002]. The reason for this discrepancy is that the Rademacher complexity of the predictor class necessarily scales with the range of the function outputs, which not necessarily relevant we use bounded losses (that is, if we actually interested in the function class of linear predictors composed with bounded loss). Such bounded losses are common, for example, when we are interested in bounding the expected misclassification error (see for example Bartlett and Mendelson [2002], Bartlett et al. (2017)). For this reason, when considering the predictor class itself, we focus on fat-shattering dimension in our lower bounds, and Rademacher complexity in our upper bounds.
3 Frobenius Norm Control is Necessary for General Networks
We begin by considering mnc-hidden-layer networks x + u o (Wx), where a is function on I applied element-wise (such as the ReLU activation function). In Subsection 3.1, we consider the dimension-free case (where we are interested in bounds that do not depend on the input dimension d). In Subsection 3.2, we consider the case where the dimension is a fixed parameter.
3.1 Dimension-Fie Free Bounds
We focus on the following hypothesis class of scalar-valued, one-hidden neural networks of width n on inputs in Rd, where function on IP applied element- wise, and where we only bound the operator norms:
H B,dd == UL--TToWW : u ERR W ||u|| bb, |W]] < B}
The following theorem shows that if the input dimension is large enough, then under mild condition on the non-smoothness of a around 0, the fat-shattering dimension of this class necessarily scales with the network width
Theorem 1. Suppose that the activation function a (as function on R) is 1-Lipschitz on [-1, +1], and satisfies a (0) = 0 as well as inf inf (- 2 a. some a > 0.
Then there exist universal constants e, > such that the following hold: For any b. B, by, n, <> there is some do poly(b, B, by, n, 1/e) such that for any input dimension d 2 do. H B., can

---

shatter
ca. (bBba)² 2
6²
points from {x E IRd ||||| s bot with margin provided the expression above is larger than c( B + n).
To understand the condition on in the theorem, suppose that has left-hand derivative o'_ (0) and right-hand derivative a'_ (0) at Recalling that (0) = O, the condition stated in the theorem implies that (0)) =10)-a(-0))
2 a for all > 0. In particular, as 5 - 0, we get (0) o'_ (0) a. Thus, a is necessarily non-differentiable at O. For example, the ReLU activation function satisfies the assumption in the theorem with = 1, and the leaky ReLU function (=) - Bz (1 - [][=] (with parameter (3 satisfies the assumption with a = =
8
Remark 1. The assumption (0) = 0 is without much loss of generality: of(()) + O. then let (() = (22) - (0) be a centering of a, and note that our predictors can be rewritten in the form x u o (Wx) o()) u 1. Thus, our hypothesis class contained the hypothesis class of predictors of the form x uuā (Wx) +r for some bounded bias parameter E R. This bias term does not change the fat-shattering dimension, and thus is not of much interest.
The theorem implies that with only spectral norm control (i.e. where ||]|| is bounded), it is impossible to get bounds independent of the width of the network n. Initially, the lower bound might appear surprising, since if the activation function is the identity, Hj Bi,..n.d simply contains linear predictors of norm S bB, for which the sample complexity / fat-shattering dimension is well known be ObB (2) in high input dimensions, completely independent of (see discussion in the previous section). Intuitively, the extra n term in the lower bound comes from the fact that for random matrices M, [|a[M]]] can typically much larger than [|M]], even when a is a Lipschitz function satisfying (0) = 0. To give a concrete example, if M is n X matrix with i.i.d. entries uniform on {+ (++)) ). then standard concentration results imply that M|]] upper- bounded by a universal constant independent of n. yet the matrix a (M) (where is entry-wise absolute value) satisfies ||a (M)l = v (since o (M) ) is just the constant matrix with value /n at every entry). The formal proof (in the appendix) relies on constructing a network involving random weights, so that the spectral norm is small yet the network can return sufficiently large values due to the non-linearity. Remark 2. Thm. I has an interesting connection to the recent work of Bubeck et al. [2021], ), which implies that in order fit m points with bounded norm using width-n one-hddeen-layer neural network x + v a (W)), the Lipschitz constant of the network (and hence ||v|| [[W]]) must be generally at least D mm/n). The lower bound in Thm. 1 implies related statement in the opposite direction: If we allow ||v|| [|W]| to be sufficiently larger than /m/n, then there exist m points that can be shattered with constant margin. Thus, we seem to get a good characterization of the expressiveness of one-hidden layer neural networks on finite datasets, as a function of their width and the magnitude of the weights.
Considering the lower bound, and noting that Ban is an upper bound on ||]] which is tight in the worst-case, the bound suggests that a control over the Frobenius norm ||[| would be sufficient to get width-independent bounds. Indeed, such results were previously known when a is the ReLU function, or more generally, Golowich al., 2018], with the proofs crucially relying on that property. In what follows, will prove such a result for general Lipschitz functions (at least for one- hidden layer networks).
function degree 1 [Neyshabur et al., 2015,
Specifically, consider the following hypothesis class, where the previous spectral norm constraint on W is replaced by a Frobenius norm constraint:
Fb,B,nd == {x+ u (W u IR" W E Radd ||u|| S b, ||W S SB}
Theorem 2. Suppose o(-) (as function on R) is L-Lipschitz and a(0) = O. Then for any b, B, bas n, d,e > 0, the Rademacher complexity of Ff,B.n. on m inputs from {x E Rdd ||||| < bz} is at most e, if
m 2 c. (bBb,, 2) log (o (m))
2²
for some universal constant C 0. Thus, it suffices to huve in = Ö (bRb,L.)) -((MRA
5

---

The bound is indeed independent of the network width Also, the result (as an upper bound on the Rademacher complexity) is clearly tight up to log-factors, since in the special case where a(2) = - and we fix u = b e1, then FE, B.B.n.d reduces to the class of linear predictors with Euclidean norm at most 6BL (on data of norm at most bz), whose Rademacher complexity matches the bound above up to log-factors.
Remark 3 (Connection to Implicit Regularization), It was recently proved that training neural networks employing homogeneous activations on losses such as the logistic loss, without any explicit regularization, gradient methods are implicitly biased towards models which minimize the squared Euclidean norm of their parameters [Lyu and Li, 2019, Ji and Telgursky, 2020]. In our setting of one- hidden-layer networks x + uu ((Wx) x), this reduces to ||u]] ||| [|3. For homogeneous activations, multiplying u by some scalar and dividing W by the same scalar leaves the nefwork unchanged. Based on this observation, and the fact that min ||ou|| + 2 = 22|u||| [[W]], it follows that minimizing ||ull2+ [[ (under any constraints on the network's 's outputs) is equivalent to minimizing ||u|| [|W]F (under the same constraints). Thus, gradient methods are biased towards models which minimize our bound from Thm. 2 in terms of the norms of u, W.
3.2 Dimension-Dependee Lower Bound
The bounds presented above are dimension-free. in the sense that the upper bound holds for any input dimension d, and the lower bound applies once d is sufficiently large. However, for neural networks the case of d being a fixed parameter is also of interest, since we often wish to apply large neural networks on inputs whose dimensionality is reasonably bounded (e.g., the number of pixels in an image).
For fixed d, and for the predictor class itself (without an additional loss composed), it is well-known that there can be a discrepancy between the fat-shat dimension and the Rademacher complexity, even for linear predictors (see discussion in Sec. 2). Thus, although Thm. 2 is tight bound on the Rademacher complexity, one may conjecture that the fat-shattering dimension (and true sample complexity for bounded losses) is actually smaller for fixed d.
In what follows, we focus on the case of the Frobenius norm, and provide a dimension- lower bound on the fat-shattering dimension. We first state the result for a ReLU activation with a bias term (Thm. 3), and then extend it to the standard ReLU activation under slightly more stringent condition (Corollary 1).
Theorem 3. For any b. B, bn, D,,,, 6, and any d larger than some universal constant, there exists choice of B E 10, ( Bb, ) such that the following hold: If (()) = [z - B]+, then F shatter
vdn
B.B.n can
á min { nd, bBbr val)
(1)
points from {x E TR.:
||x|| & bz) with margin e, assuming the expression above is larger than for some universal constant e >> O, and where át hides factors polylogarithmic in d, n,,, b, B, bas 1
Corollary 1. The lower bound of Thm. 3 also holds for the standard ReLU activation a(z) (z)= = [z] 3 < Bhg (which happens if the input dimension d is larger than a factor polylogarithmic in the Vn
problem parameters).
The lower bound is the minimum of two terms: The first is nd, which is the order of the number of parameters in the network. This term to be expected, since the fat-shatt dimension of F is at most the pseudodimension of F. which indeed scales with the number of parameters nd (see Anthony and Bartlett [1999], Bartlett et al. [2019]). Hence, we cannot expect to be able shatter many more than nd points. The second term is norm- and cemensioonddpendeee the overall lower bound if the network width n is large enough. Comparing the theorem with the Ö(bBb,/<)) upper bound from Thm. 2, it seems to suggest that having bounded dimension d may improve the sample complexity compared to the dimension-frr case, with a smaller dependence on the norm bounds. However, at the moment we do not have upper bounds which match this lower bound, or even establish that bounds better than Thm. 2 are possible when the dimension d is small. We leave the question of understanding the sample complexity in the Dime-dimennionn regime as an interesting problem for future research.
and dominates

---

Remark 4 (No contradiction to upper bound in Thm. 2, due to implicit bound on d). Thm. 3 requires that Eq. (1) least order of d for the lower bound to be valid. This in turn requires that bBba vd 2 d, or equivalently d < (bBb=)² Thus, the theorem only applies when the dimension d not too large with respect to the other parameters. We note that this is to be expected: If we allow d >
(Bbba) (and sufficiently large), then the lower bound in Eq. (1) will be larger than bBb and this would violate the O ((bbb=/e)?) upper bound implied by Thm. 2.
Spectral Norm Control Suffices for Sufficiently Smooth Activations
The lower bounds in the previous section crucially rely on the non-smoothness of the activation functions. Thus, one may wonder whether smoothness can lead to better upper bounds. In this section, we show that perhaps surprisingly, this is indeed the case: For sufficiently smooth activations (e.g.. polynomials), one can provide width- width- independent Rademacher complexity bounds, using only the spectral norm. Formally, we return the class of me-hidden-layer neural networks with spectral norm constraints,
Hi B,n.d (x+ u ((Wx) EUER" WE | bb, |[I| S B)
and state the following theorem:
Theorem 4. Fix some b, B, bz n,, d, > O. Suppose - - Ozzd for some 01, a.,.... E IR, simultaneously for all 2 |z| S Bb Then the Rademacher complexity of B.,.nnd on m. inputs from {x E Fd ||x||| S bz) most if
b.. (bbb(Bb))
00
where a(2) = Σ laglod
m
(assuming the sum converges).
We note that the conditions imply (0) = O, which is assumed for simplicity (see Remark 1). We emphasize that this bound depends only on spectral norms of the network and properties of the activation a. In particular, of W. We also note that the bound is clearly tight in some cases: For example, if (-) is just the identity function, then Hg, reduces the class of linear predictors of Euclidean norm at most bB, whose Rademacher complexity on inputs of norm at most by is well-known to equal O ((bBb,//e) This also demonstrates that the dependence on the spectral norm B necessary, even with smooth activations.
independent of the network width n as well as the Frobenius norm
The proof of the theorem (in the appendix) depends on algebraic manipulations, which involve 'unrolling' the Rademacher complexity as a polynomial function of the network inputs, and employing certain technical trick to simplify the resulting expression, given bound on the spectral norm of the weight matrix.
We now turn to provide some specific examples of (-) and the resulting expression ä ō(Bba):
Example 1. (2)(2) is a polynomial of degree k. then ā( (Bbz) ((Bb))** for large enough Bbg-
In the example above, the output values of predictors in the class are most ((BB)))* ), it is not surprising that the resulting Rademacher complexity scales in the same manner.
The theorem also extends to non-polynomial activations, long as they are sufficiently smooth (although the dependence on Bb, o (Bbb) generally becomes exponential). The following is an example for sigmoidal activation based the error function:
Example 2. [f)(z) erf(rz) (where erf is the error function, and r > 0 is scaling parameter). then ō Bbxx) < BrB exp((r Bbb.)).
See the appendix for a proof. A sigmoidal activation also allows us to define smooth approximation of the ReLU function, to which the theorem can be applied:
Example 3. If (y) (y + SN erf(r2)dz), then ō ((bb)) S Bb +
r(Bb.)² v
exp((rBb.))
7

---

We note that a oo, (vy) converges uniformly to the ReLU function.
Although the last examples imply exponential dependence on the spectral norm bound B in the theorem, they still imply that for any fixed B, we can get finite size-independent sample complexity (regardless of the network's s width input dimension) while controlling only the spectral norm of the weight matrices.
4.1 Extension Higher Depths for Power Activations
When the activation functions are powers of the form ((2) zh for some k. then the previous theorem can be extended to deeper networks. To formalize this, fix integers k > 1 and L 2 1, and consider a depth-(L + 1) network fL+1 (x) (parameterized by weight matrices W W .?...., W of some arbitrary fixed dimensions, and weight vector u) defined recursively as follows:
fo(x) x Vj {0, , -11, 1}, fz+((x) = (Wi+1f((x))* fL+1(x)= = fz(x).
where (v)s* denotes applying the k-th power element-wise on a vector V.
Theorem 5. For any integers k, L 2 1 and choice of matrix dimensions at each layer, consider the
class of neural networks fL+1 as above, over all weight matrices w*...W? W such that [[Wi]| S B for all and all u such that ||u|| < b. Then the Rademacher complexity of this class on m inputs from {x: ||x] < by3 is at most if
b B.ttt&++ +..kk bbc
For constant i and constant-depth networks, the sample complexity bound in the theorem is b poly(Bba)) /m, where B bounds merely the (relatively weak) spectral norm. We also note that the expooential/doubly-expeeettt dependence on k. L to be expected: Even if consider networks where each matrix a scalar B, and the input is exactly ly. then multiplying by B and taking the
k-th power L 1 times over leads to the exact same B + b%2 factor. Since the Rademacher complexity depends on the scale of the outputs, such factor is generally unavoidable. The proof of the theorem (in the appendix) builds on the proof ideas of Thm. 4, which can be extended to deeper networks at least when the activations are power functions.
Convolutional Networks
In this section, we study another important example of neural networks which circumvent our lower bounds from Sec. 3, this time by adding additional constraints on the weight matrix. Specifically, we consider one-hidden-layer convolutional neural networks. These networks are defined via set of patches & {Ø,}ī=1, where for each the patch Φ, Ed + R" projects the input vector x Rd into some subset of coordinates, namely d,(x) = (Iq.....,..) for some
(e.....,&. S (1....,,d, d}. The hidden layer is parameterized by a convolutional filter vector E Rm" and given an input x, outputs the vector (a(w TTTT()))) (xxx))...,, on, (x))) R., where is some activation function (e.g.. ReLU). Note that this can be equivalently written as (WWx), where each row j of W embeds the w vector in the coordinates corresponding to (.)(.). In what follows, say that a matrix W conforms to a set of patches = { if there exists a vector w such that (Wx), w T (x) for all x. Thus, convolutional hidden layer corresponds to standard hidden layer (same as previous sections), but with the additional constraint on W that it must conform to a certain set of patches.
In the first subsection below, we study networks where the convolutional hidden layer combined with a linear output layer. In the following section, we study the case where the hidden layer is combined with a fixed pooling operation. In both cases, we will get bounds that depend on the spectral norm of W and the architecture of the patches.

---

5.1 Convolutional Hidden Layer + Linear Output Layer
We begin by considering convolutional networks consisting of a convolutional hidden layer (with spectral norm control and with respect to some set of patches), followed by a linear output layer:
H6. B. (x+ u (Wx)
E IR", W E Raxd, |ul| < b, || S B, W conforms to b
The following theorem shows that we can indeed obtain a Rademacher complexity bound depending only the spectral norm of W, and independent of the network width n, under mild assumption about the architecture the patches:
Theorem 6. Suppose a(-) is L-Lipschitz and (0) O. Fix some set of patches D, and let O& be the maximal number of patches that any single input coordinate (in {1....,dy appears in. Then for any &
b, B, b n, d,e > O, the Rademacher complexity of Hf, n,,d B,,,B,, on m inputs from fx E RR | S by} is at most if
(BbbLL
2 2-
Other than the usual parameters, the bound in the theorem also depends on the architectural parameter which quantifies the amount of "overlap" between the patches. Although it can be as large as in the worst case (when some single coordinate appears in all patches), for standard convolutional architectures it is usually quite small, and does not scale with the input dimension or the total number of patches. For example, it equals if the patches are disjoint, and more generally it equals the patch size divided by the stride. Nevertheless, an interesting open question whether the Og factor in the bound can be reduced avoided altogether.
Oo E (1....; n.).
5.2 Convolutional Hidden Layer + Pooling Layer
We now turn consider slightly different one-hidden-layer convolutional networks, where the linear output layer is replaced by a fixed pooling layer. Specifically, we consider networks of the form
x + (Wx) = - (a (x))...... o. on (x))),
where R R is activation function as before, and p: IR" R is 1-Lipschitz with respect to the 2o norm. For example, p(-) may correspond to a max-pooling layer z + maxje[n] 2j. or to an average- everage-pooling layer z + 1 Σ jEj] Zj. We define the following class of networks:
B,ndd = {x p o (Wx) W Bxdd, |W]| < B W conforms to $
This class is very closely related to class of convolutional networks recently studied in Ledent et al. [2021] using elegant covering number argument. Using their proof technique, we first provide Rademacher complexity upper bound (Thm. 7 below), which depends merely on the spectral norm of the network width n. Although logarithmic dependence
W. as well logarithmic dependence is relatively mild, one may wonder if we can remove it and get fully width-independent bound, same as our previous results. Our main novel contribution in this section (Thm. 8) is to show that this is not the case: The fat-shattering dimension of the class necessarily has a log(n) factor, so the upper bound is tight up factors polylogarithmic in the sample size m.
Theorem 7. There exists a universal constant e > such that the following holds. Suppose that R + R is L-Lipschitz and a (0) O, and that p: R -> IR is 1-Lipschitz w.r.t. foo and satisfies p(0) = 0. Fix some set of patches = {Ø, 1 Then, for any B, n, d, by e > 0, the Rademacher
complexity of H. on m imputs from {x Rd [1o,(x)) < by for all j E [n]] is most e,
T. L.
2 log2(m) (m) log)om)))).
m 2 c.
E
Thus, it suffices to have m δ LBb. 2
For the lower bound, we focus for simplicity on the case where p(z) max, 2j is a max max-pooling layer, and where the ReLU function (which satisfies the conditions of Thm. with = 1). However, we emphasize that unlike the lower bound we proved in Sec. 3, the construction does not rely on the non-smmoth of a, and fact can easily be verified to apply (up constants) for any satisfying (0) 0 and o(e) > (where > 0 is constant).

---

Theorem 8. For any B, b2, c O, there is d, Db such that the following hold: The class H. with being the ReLU function and being the max function, can shatter
B.a.d'
Bb
2
log(n)
points from {x E R |||||| S ] with margin e.
Moreover, this claim holds already where & corresponds to a convolutional layer with constant stride 1, in the the following sense: we view the input IR. vectorization of a tensor of order (n)), then & corresponds to all patches of certain fixed dimensions $1 tensor.
X Sp in the
Conclusions and Open Questions
In this paper, studied sample complexity upper and lower bounds for one-hidden layer neural networks, based on bounding the norms of the weight matrices. We showed that general, bounding the spectral norm cannot lead to size- iizeiindependent guarantees, whereas bounding the Frobenius norm does. However, the constructions also pointed out where the lower bounds can be circumvented, and where spectral norm control suffices for width-independent guarantees: First, when the activations are sufficiently smooth, and second, for certain types convolutional networks.
Our work raises many open questions for future research. For example, how does having fixed input dimension affect the sample complexity of neural networks? Our lower bound Thm. indicates small d might reduce the sample complexity, but currently we do not have good upper bounds that actually establish that. different direction, we showed that spectral norm control does not lead to width-free guarantees with non-smooth activations, whereas such guarantees are possible with very smooth activations. Can we characterize what we can get for other activation? As to convolutional networks, we studied two particular architectures employing weight-sharing One with a linear output layer, and one with fixed Lipschitz pooling layer mapping to R. Even for one-hidden-laye layer networks, this leaves open the question of characterizing the width-independent sample complexity of networks x + u o (Wx), where W implements weight-sharing and is pooling operator mapping to IR" with p 1 (Ledent al. [2021] provide upper bounds in this setting, but they are not size-independent and we conjecture that they can be improved). Beyond these, perhaps the most tantalizing open question is whether our results can be extended deeper networks, and what types of bounds we might expect.
Acknowledgements
This research is supported in part by European Research Council (ERC) grant 754705, and NSF-BSF award 1718970. We thank Roey Magen for spotting some bugs in the proof of Thm. 2 in a previous version of this paper, and the anonymous reviewers for helpful comments.
References
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundations. Cambridge University Press, 1999.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018
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.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky, Epectrally-normalie margin bounds for neural networks. Advances in Neural Information Processing Systems, 50:6240-62244 2017.
Peter I. Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20(1):225--3301, 2019,
10

---

Alon Brutzkus and Amir Globerson. An optimization and generalization analysis for max pooling networks. In Proceedings of the Thirty-Seventi Conference on Uncertainty in Artificial Intelligence. 2021.
Sébastien Bubeck, Yuanzhi Li, and Dheeraj M Nagaraj. A law of robustness for two-layers neural networks. In Conference on Learning Theory, pages 804- 820. PMLR, 2021.
Yuan Cao and Quanquan Gu. Tight sample complexity of learning one- mee-hidden-baee layer convolutional neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Amit Daniely and Elad Granot. Generalization bounds for neural networks via approximate descrip- tion length. Advances in Neural Information Processing Systems, 32:1 12:13008-4 110000000861,11.1111111111111116 2019.
Simon Du and Jason Lee. On the power of over- ver-parrametrizatioon in neural networks with quadratic activation. In International Conference on Machine Learning, pages 3229-333. PMLR, 2018.
Simon S Du, Yining Wang, Xiyu Zhai, Sivaraman Balakrishnan, Russ R Salakhutdinov, and Aarti Singh. How many samples are needed to estimate a convolutional neural network? Advances in Neural Information Processing Systems, 31, 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXivv 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size Size-independent sample complexity of neural networks. In Conference On Learning Theory, pages 297-299 PMLR, 2018.
Daniel Hsu, Ziwei Ji, Matus Telgarsky, and Lan Wang. Generalization bounds via distillation. In International Conference on Learning Representations, 2020.
Ziwei Ji and Matus Telgarsky. Directional convergence and alignment in deep learning. Advances in Neural Information Processing Systems, 33, 2020.
Frederic Kochler, Lijia Zhou, Danica Sutherland, and Nathan Srebro. Uniform convergence of inter- polators: Gaussian width, norm bounds, and benign overfitting, arXiv preprint 11Xiv:200.009276 2021.
Antoine Ledent, Waleed Mustafa, Yunwen Lei, and Marius Kloft. Norm-based generalisation bounds for deep multi-class convolutional neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 8279-8287, 8287, 2021.
Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23, Springer Science & Business Media, 1991.
Xingguo Li, Junwei Lu, Zhaoran Wang, Jarvis Haupt, and Tuo Zhao. On tighter generalization bound for deep neural networks: Cnns, resnets, and beyond. arXiv preprint wxXv::806.00559, 2018.
Percy Liang- Cs229t/stat231: Statistical learning theory (winter 2016) lecture notes. https:
//web. weabbsstaffor..omo caau/clas////e/caccceceaaaeaaeaa cs229t/notes pdf, 2016.
Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In International Conference on Learning Representations, 2019.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. In International Conference on Learning Representations, 2019.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable explain generalization in deep learning. In Advances in Neural Information Processing Systems, volume 32, 2019.
Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform convergence: Generalization via derandomization with an application to interpolating predictors. In International Conference Machine Learning, pages 7263-7272. PMLR, 2020.

---

Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pages 1376-1401. PMLR, 2015.
Yoav Seginer. The expected norm of random matrices. Combinatorics, Probability and Computing, (2):149-166, 2000.
Shai Shalev-Shwarzz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.
Colin Wei and Tengyu Ma. Improved sample complexities for deep networks and robust classification via an all-layer margin. arXiv preprint arXiv: (xtiv:9100 10.04284, 2019.
Tong Zhang. Covering number bounds of certain regularized linear function classes. Journal of Machine Learning Research, 2(Mar):527-550, 2002.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] The paper purely theoretical in nature, and we do not see any potential negative societal impacts that should be discussed.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are in the appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsoureing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "z7sBLRRBbZD", "reviewer": "Reviewer_6M6u", "summary": "This paper studies the sample complexity of simple neural network model classes. The focus is on upper and lower bounds under various norm constraints on the network coefficients. It is shown that a spectral norm constraint is not sufficient to obtain bounds that are independent of the network width. To prove this, the authors estimate the fat shattering dimension of the considered hypothesis class. The surprising aspect of this result is that it does not hold if the activation is the identity but crucially depends on the nonlinearity. As a second contribution the authors show that a Frobenius norm constraint yields hypothesis classes whose sample complexity is independent of the network width. Finally, the authors identify two interesting settings where a spectral norm constraint is sufficient for getting bounds independent of the width. ", "questions": "I would like to ask the authors to comment more on the novelty of their proof techniques. ", "limitations": "This has been adequately addressed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think that this is an interesting paper, well written, and adding to the current body of knowledge on understanding the generalization behaviour of deep learning algorithms. \n\nIn terms of originality I am not sure if the paper introduces new proof techniques; maybe they can elaborate the novelty of their technical and mathematical contributions a bit more? ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "wgF1gFTG7W", "reviewer": "Reviewer_UHEf", "summary": "Based on bounded norms of the weight matrices, the authors investigated the upper and lower bound sample complexity for neural networks with one hidden layer in this research.  They demonstrated that in contrast to bounding the Frobenius norm, however, bounding the spectral norm generally cannot result in size-independent guarantees - although it is not surprising that the spectral norm is insufficient to get width-independent sample complexity bound -  the paper and its theoretical analysis are very important. \n\n\nThe constructions did, however, highlight two situations in which the lower bounds can be avoided and a spectral norm control is sufficient to provide width-independent guarantees. The first scenario is when the activations are sufficiently smooth, and the second is in certain situations involving convolutional networks. \n\nIn general, this is a very important paper as deep neural networks still lack a very basic understanding of their behavior.", "questions": "Some definitions are missing. What is the definition of a Lipschitz function in your work? Is it the standard definition, (intuitively) a continuous function that is limited in how fast it can change?\n\nCan you give more examples of other used Lipschitz functions?\n\nIs σ(0) = 0, necessary in all the theorems, or it can be avoided (used for simplicity)? \n\n\n\n", "limitations": "some simple numerical experimentss would help justify the theory.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. A very solid theoretical paper - the theorems and proofs are exciting.\n2. The paper deals with very important and required questions in the field of deep learning, not many papers focus on the theoretical side of deep learning - I find this paper a very important step towards better understanding DNNs. \n\nWeaknesses:\nAlthough it is clear that the paper is a theoretical paper, however, I have the following minor comment. The writing could still be improved, giving some intuitive explanation and details as to what and why each theorem holds and what each theorem mean -- it took some time to understand the theorems and the details. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "XBCtsUkSP5G", "reviewer": "Reviewer_NAae", "summary": "This paper studies the norm-based uniform convergence bounds for two-layer neural networks. Their results give a tight understanding of spectral-norm-based uniform convergence. In particular, they proved that spectral norm is not sufficient for general settings to get a uniform convergence result. However, for NNs with certain smoothness conditions or some convolution structures, the spectral norm is sufficient. ", "questions": "The uniform convergence guarantees derived in Sections 4 and 5 are size-independent. I wonder whether they also work for infinite width neural networks such as mean-field settings?", "limitations": "The authors have addressed their work's limitations and potential negative social impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this paper is well-written and clear. The authors show that, in general, bounding the spectral norm cannot lead to size-independent guarantees. This negative result is quite interesting and insightful. However, I have a concern about the significance of the results. Since the size of the parameters is known through the training, it seems unnecessary to get a size-independent guarantee. Moreover, the spectral-norm-based convergence result seems hard to apply both empirically and theoretically, which may limit the application of the convergence result. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NKxgfY0WOIr", "reviewer": "Reviewer_poyY", "summary": "The paper presents various upper bounds (Rademacher complexity based) and lower bounds (fat shattering dimension based) on single hidden layer neural networks. These bounds shed light on the question whether the bounded spectral norm of the weight matrix is sufficient for having width independent uniform convergence guarantees. Moreover, there are similar discussions for Frobenius norms and input dimension dependence. The paper considers both generic and convolutional neural networks. \n\nContributions of the paper are summarized in 8 theorems:\n\n* Theorem 1 shows that the fat shattering dimension is scaled with the network width for nonsmooth activation function, if only the spectral norm is bounded. \n* Theorem 2 generalizes Golowich et al 2018 and Neyshabur et al 2015 to show that Frobenius norm bound is sufficient to bound the sample complexity for Lipschitz activation functions (width independent bound) using Rademachar complexity analysis.\n* Theorem 3 shows that the fat shattering dimension for Frobenius norm bounded networks is input dimension dependent (for smaller input dimensions).  \n* Theorem 4 shows that the spectral norm is sufficient to bound the sample complexity for polynomial activation functions. \n* Theorem 5 extends the result to the multilayer case for polynomial activation functions of type $z^k$. Lemma 4 and 5 are crucial for the proof of Theorem 4 and 5.\n* Theorem 6 shows that the spectral norm is sufficient for convolutional networks with linear last layer.\n* Theorem 7 shows that Rademacher complexity bound for convolutional networks with pooling  has logarithmic dependence on width.\n* Theorem 8 shows, using fat shattering dimension, that the logarithmic width dependence is unavoidable. \n", "questions": "* Regarding Theorem 1: Anthony and Bartlett 1999 also provide an expression of fat shattering dimension although with slightly different assumptions (Theorem 14.18) and limitations. For example, the bound is input dimension dependent, the class of activation functions is different, etc. It would be good to add a discussion regarding this to the related works.\n* Regarding Theorem 2: the proof, like Theorem 5 of Golowich et al, seems to be based on McDiarmid’s lemma and not relying on Dudley’s integral, which is also used to bound the Rademacher complexity using covering numbers. Is there any reason behind why Dudley’s integral is not used? Does it provide worse result if applied to this context with Lipschitz activation function? This can be an interesting theoretical insight and valuable to add.\n* Theorem 4 and 5 prove that for polynomial activation functions, the spectral norm bound is sufficient for uniform convergence bound. However, the question remains if the lower bound, based on fat shattering dimension, can be further improved for these activation functions. A comment on this point can be a good add to the paper, if it is straightforward.\n* The authors mention that they build on Ledent et al 2021 for Theorem 7. However, it is not currently clear, neither in the main paper nor in A.8,  what is the main difference between Ledent et al 2021. The difference in the respective proofs and bounds should be specified.\n* If $[M]_{+}$ is the ReLU applied on $+/- 1/\\sqrt{n}$, I cannot see why it “is just the constant matrix with value $1/\\sqrt{n}$ at each entry” (page 5). It will be a combination of 0 and $1/\\sqrt{n}$.\n* I felt that Remark 4 is a bit confusing, although I got the point: namely, the presence of d in the lower bound does not contradict Theorem 2, since it assumes that “the above expression” is bigger than cd (according to the theorem) meaning that $(bBb_x/\\epsilon)\\sqrt{d}$ is bigger than $cd$, and therefore, d is smaller than $(bBb_x/\\epsilon)^2$. I think this remark can be re-written. I suggest adding equation and theorem labels and refer to them explicitly instead of using demonstratives.\n* The authors mention that “when the network employs weight-sharing”, it is possible to get width independent bound (actually logarithmic dependence for CNNs with pooling). This is not fully precise. The term $O_\\Phi$ hides the dependence on kernel size. Consider a discrete circular convolution for which the matrix $W$ is a circulant matrix. In this case, $O_\\Phi = n$. Even for a vanilla convolutional kernel, $O_\\Phi$ is equal to the kernel size, which is a more intuitive notion of width for convolutional networks. This is clear at the end of A.7 right above A.8 where two summations range over m and n inside the square root.\n* How do the current results change (or not) if one introduces a margin-based loss? For classification tasks, if one disregards the margin, it is possible to rescale the last layer without changing the classification accuracy, which would mean arbitrarily changing the product of spectral norm. Many previous works, e.g., Bartlett et al 2017, consider margin-based bounds. Why is this not considered in this work?\n", "limitations": "As mentioned by the authors themselves, there is a debate whether uniform convergence can explain generalization in neural networks mainly supported by some carefully designed experiments. It is not clear how one should understand the bounds of this paper in light of papers like Nagarajan et al 2019.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n\nFrom technical perspective, the paper provides a valuable contribution by clear exposition of the role of spectral and Frobenius norm in uniform convergence results. \nThe paper is well written. Given the sheer volume of works on explaining generalization error for neural networks, the authors do a good job connecting the results to the existing works for instance in Remark 2 on Bubeck et al 2021 or Remark 3 on implicit regularization. The paper contains many theoretical results of interest, combines many ideas from previous works and provide new proof techniques notably Theorem 4 and 5 (to the best of my knowledge). The proofs are well presented and are sound. Overall, this is a great paper and I enjoyed reading it.\n\n**Weaknesses:**\n\n* Although this might seem like a gratuitous comment and request, I think having numerical support, even a toy example, can be good to support the theory. \n* I have some concerns about O_\\Phi term in Theorem 4 (see below).\n* I feel that the authors do not adequately comment about implications of the current result for a general theory of generalization for deep learning. Covering all existing works are of course not possible, however, works like Nagarajan et al 2019, or Zhang et al ICLR 2017 are widely discussed. It is at least expected that the authors clarify in which regime their bounds are applicable and do not suffer from examples of those papers. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept