Initialization-Dependent Sample Complexity of Linear Predictors and Neural Networks
Authors: Roey Magen
Ohad Shamir
Venue: NeurIPS 2023 poster (2023)
Keywords: sample complexity; learning theory; neural networks; linear predictors
TL;DR: We provide new results on the sample complexity of vector-valued linear predictors, and more generally neural networks,  showing that it can be surprisingly different than the well-studied setting of scalar-valued linear predictors

Abstract: We provide several new results on the sample complexity of vector-valued linear predictors (parameterized by a matrix), and more generally neural networks. Focusing on size-independent bounds, where only the Frobenius norm distance of the parameters from some fixed reference matrix $W_0$ is controlled, we show that the sample complexity behavior can be surprisingly different than what we may expect considering the well-studied setting of scalar-valued linear predictors. This also leads to new sample complexity bounds for feed-forward neural networks, tackling some open questions in the literature, and establishing a new convex linear prediction problem that is provably learnable without uniform convergence.

Initializatinn-Deendeer Sample Complexity of Linear Predictors and Neural Networks
Roey Magen Weizmann Institute of Science roey. magen@we zmann, ac. il
Ohad Shamir
Weizmann Institute of Science ohad. shami hamiir@we zmann ac il
Abstract
We provide several new results the sample complexity of vector-valued linear predictors (parameterized by matrix), and more generally neural networks. Fo- cusing on -izeeindeeendent bounds, where only the Frobenius norm distance the parameters from some fixed reference matrix Wo is controlled, we show that the sample complexity behavior can be surprisingly different than what may expect considering the well-studied setting of scalar-valued linear predictors. This also leads to new sample complexity bounds for feed-forward neural networks, tackling some open questions in the literature, and establishing new convex linear prediction problem that is provably learnable without uniform convergence.
Introduction
In this paper, we consider the sample complexity of learning function classes, where each function is composition of one more transformations given by
f(Wx),
where x is a vector, W is a parameter matrix, and f is some fixed Lipschitz function. A natural example is vanilla feed-forward neural networks, where each such transformation corresponds layer with weight matrix W and some activation function f. A second natural example are vector- valued linear predictors (e.g., for multi-class problems), where W is the predictor matrix and corresponds to some loss function. A special case of the above are scalar-valued linear predictors (composed with some scalar loss nonlinearity f). namely x + f(w x), whose sample complexity is extremely well-studied. However, we are interested in the more general case of matrix-valued W. which (as we shall see) is far less understood.
Clearly, in order for learning to be possible, we must impose some constraints on the size of the function class. One possibility is bound the number of parameters (i.e., the dimensions of the matrix W), in which case learnability follows from standard VC-dimension or covering number arguments (see Anthony and Bartlett [1999]). However, an important thread in statistical learning theory is understanding whether bounds on the number of parameters can be replaced by bounds on the magnitude of the weights say, a bound on some norm of W. For example, consider the class of scalar-val valued linear predictors of the form
{x x --ww x:
Rd ||w|| S B)
and inputs ||||| < 1, where || || is the Fuclidean norm. For this class, it is well-known that the sample complexity required achieve excess error (w.rt. Lipschitz losses) scales O(B² /e2), independent of the number of parameters d (c.g., Bartlett and Mendelson [2002], Shalev-Shwartz and Ben-David [2014]). Moreover, the same bound holds when we replace x by f(w x) for some I-Lipschitz function f. Therefore, it is natural to ask whether similar size-independent bounds can be obtained when W a matrix, as described above. This question is the focus of our paper.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

When studying the matrix case, there are two complicating factors: The first is that there are many possible generalizations of the Euclidean norm for matrices (namely, matrix norms which reduce to the Euclidean norm in the case of vectors), so it is not obvious which one to study. A second is that rather than constraining the norm of W, it is increasingly common in recent years to constrain the distance to some fixed reference matrix Wo. capturing the standard practice of non-zero random initialization (see, e.g., Bartlett et al. [2017].. Following a line of recent works in the context of neural networks (e.g.. Vardi et al. [2022], Daniely and Granot [2019, 2022I), we will be mainly interested in the case where we bound the spectral norm || of Wo. and the distance of W from Wo in the Frobenius norm ||| ||., resulting in function classes of the form
{x + f(Wx) W E Radd I|W -oole S
(I)
for some Lipschitz, possibly non-linear function f and a fixed Wo of bounded spectral norm. This is a natural class to consider, as we know that spectral norm control is necessary (but insufficient) for finite sample complexity guarantees (see, e.g., Golowich et al. [2018]), whereas controlling the (larger) Frobenius norm is sufficient in many cases. Moreover, the Frobenius norm (which is simply the Euclidean norm of all matrix entries) is the natural metric to measure distance from initialization when considering standard gradient methods, and also arises naturally when studying the implicit bias of such methods (see Lyu and Li [2019]). As to Wo, we note that in the case of scalar- valued linear predictors (where W. Wo are vectors), the sample complexity is not affected by Wo- This is intuitive, since the function class corresponds to a ball of radius B in parameter space, and Wo affects the location of the ball but not its size. A similar weak dependence Wo is also known to occur in other settings that were studied (e.g., Bartlett et al. [2017]).
In this paper, we provide several new contributions on the size-independent sample complexity of this and related function classes, in several directions.
In the first part of the paper (Section 3), we consider function classes as in Eq. (I), without further assumptions on f besides being Lipschitz, and assuming x has a bounded Euclidean norm. As mentioned above, this is a very natural class, corresponding (for example) to vector vaatur linear predictors with generic Lipschitz losses, or neural networks composed of single layer and some general Lipschitz activation. In this setting, we make the following contributions:
In subsection 3.1 we study the case of Wi = O, and prove that the size-independent sample complexity (up to some accuracy e) is both upper and lower bounded by g5(B²/e") This is unusual and perhaps surprising, as it implies that this function class does enjoy finite, size-independent sample complexity bound, but the dependence on the problem parameters B, are exponential. This is in very sharp contrast to the realar-valued case, where the sample complexity is just O(B²/ /²) as described earlier. Moreover, and again perhaps unexpectedly, this sample complexity remains the same even if we consider the much larger function class of all bounded Lipschitz functions, composed with all norm-bounded linear functions (as opposed to having a single fixed Lipschitz function).
Building on the result above, we prove a size-independent sample complexity upper bound for deep feed-forwane neural networks, which depends only on the Frobenius norm of the first layer, and the product of the spectral norms of the other layers. In particular, it has no dependence whatsoever on the network depth, width or any other matrix norm constraints, unlike previous works in this setting.
subsection 3.2, we turn to consider the case of W/ A 0, and ask if it is possible to achieve similar size- iizeiindependent sample complexity guarantees. Perhaps unexpectedly, we show that the answer is no, even for Wo with very small spectral norm. Again, this is in sharp qualitative contrast to the scalar-value valued case and other settings in the literature involving a Wo term, where the choice of Wo does not strongly affect the bounds.
In subsection 3.3, we show that the negative result above yields a new construction of a convex linear prediction problem which is learnable (via stochastic gradient descent), but where uniform convergence provably does not hold. This adds to a well-established line of works in statistical learning theory, studying when uniform convergence is provably unnecessary for distribution-free
'More precisely, it is an easy exercise to show that the Rademacher complexity of the function class {x f(w x) : w E gd ||w woll S B). for some fixed Lipschitz function f. can be upper bounded independent of wo.

---

learnability (e.g., Shalev-Shward et al. [2010], Daniely et al. [2011], Feldman [2016], see also Nagarajan and Kolter [2019], Glasgow et al. [2022] somewhat different direction).
In the second part of our paper (Section 4), turn different and more specific choice of the function f. considering mee-iddenn-layer neural networks with activation applied element-wise:
(loo(x)) Σ u, x)),
with weight matrix W E Raxd weight vector u E RR and fixed (generally non-linear) Lipschitz activation function or (.). As before, We focus on Euclidean setting, where x and has a bounded Euclidean norm and | WollF is bounded, for some initialization Wa with bounded spectral norm. In this part, our sample complexity bounds have polynomial dependencies on the norm bounds and on the target accuracy e. Our contributions here are as follows:
We prove fully size-independent Rademacher complexity bound for this function class, under the assumption that the activation a--) is smooth. In contrast, earlier results that we are aware of were either not size-independent,
assumed Wo = Although do not know whether the smoothness assumption is necessary, we consider this an interesting example of how smoothness be utilized in the context of sample complexity bounds.
With Wo O, we show an upper bound on the Rademacher complexity of deep neural networks (more than one layer) that is fully independent of the network width or the input dimension, and for generic element-wist Lipschitz activations. For constant-depth networks, this bound is fully independent of the network size.
These two results answer some of the open questions in Vardi et [2022]. We conclude with a discussion of open problems in Section 5. Formal proofs of our results appear in the appendix.
1.1 Comparison to Previous Work
Deep neural networks and the Frobenius norm. A size-independent uniform convergence guaran- tee, depending the product of Frobenius norm of all layers, has been established in Neyshabur et al. [2015] for constant-depth networks, and in Golowich et al. [2018] for arbitrary-depth networks. How- ever, these bounds specific element-wiss homogeneous activation functions, whereas tackle general Lipschitz activations. Bounds based on other norms include Anthony and Bartlett [ [1999], Bartlett et al. [2017], but potentially more restrictive than the Frobenius norm, or not independent of the width. All previous bounds of this type (that we are aware of) strongly depend on various norms of all layers, which can be arbitrarily larger than the spectral norm in size-independent setting (such as the Frobenius norm and the (1, 2)-norm), or make strong assumptions on the activation function.
Rademacher complexity of vector-valued functions. Maurer [2016] showed a contraction inequality for Rademacher averages that extended to Lipschitz functions with vector-valued domains. As an application, he showed an upper bound on the Rademacher complexity of vector-valued linear predictors. However, his bound depends polynomially where we focus on iizeiindeenndent bounds, which do not depend on the input's dimension or number of parameters. The sample complexity of vector-valued predictors has also been extensively studied in the context of multiclass classification (see for example Mohri et al. (2. However, these results generally depend polynomially the vector dimension (e.g., number of classes), and size-independent.
the number of parameters (i.e. vn),
Non-zero initialization. Bartlett et al. [2017] upper bound the sample complexity of neural networks with non-zero initialization, but they used a much stronger assumption than ours: They control the (1, mmatrxx norm (sum of norms of the columns), and the gap between this norm and the Frobenius norm can be arbitrarily large, depending on the matrix size. Daniely and Granot [2022] also recently studied the non-zero initialization case, with element wise activations and Frobenius norm constraints. However, their results in this case are not iizeeindeeendent and employ a different proof technique than ours.
Non-element-wise activations. Daniely and Granot [2022] provide fat-shattering lower bound for general (possibly non-element-wise) Lipchitz activation, which implics that neural networks on Bd
3

---

with bounded Frobenius norm and width n can shatter points with constant margin, assuming that the inputs have norm vd and that = O22)). However, this lower bound does not separate between the input norm bound and the width of the hidden layer. Therefore, their result does not contradict our upper bound (Thm. 2) which implies that it is possible to achieve a size-independent upper bound on the sample complexity, when the input norm fixed independent the network width.
Preliminaries
Notations. We use bold-face letters to denote vectors, and let [m] be shorthand for {1,2.... ... Given a vector x, 2; denotes its j-th coordinate. Given matrix W, w, is its j-th row, and W its entry row and column Let Onxd denote the zero matrix in Bexd and let Taxa be the d x d identity matrix. Given a function a--) on R. we somewhat abuse notation and let (x() (for a vector x) or a (M) (for a matrix M) denote applying a()) element-wise. We use standard big-Oh notation, with (-), St-), O()) hiding constants and (()), Ō() hiding constants and factors that polylogarithmie in the problem parameters.
We let |l-Il denote the operator norm: For vectors. it is the Euclidean norm, and for matrices, the spectral norm (i.e., || = >==>:||>/=1 [| p denotes the Frobenius norm (i.e., [|
V VEi Mz It well-known that the spectral norm of matrix is equal its largest singular value, and that the Frobenius norm is equal to Σ, o. where 0 02.... are the singular values of the matrix.
When we say that a function f is Lipschitz, we refer to the Euclidean metric unless specified otherwise. We say that f IRd IR is j--mooth if f continuously differentiable and its gradient V is y--Lipschizz
Given a metric space (X, d) and 6 > O, we say that N C X is an e-cover for V S X if for every x E U. there exists x' N such that d(x, x') S e. We say that P C X' is an E e-packnng (or seperated), if for every x, E P such that + x' we have that d(x, x²) 2 E.
Sample Complexity Measures. our results and proofs, we consider several standard complexity measures of given class of functions, which are well-known to control uniform convergence, and imply upper or lower bounds on the sample complexity:
Fat-Shattering dimension: It is well-known that the fat-shattering dimension (at scale e) lower bounds the number samples needed to learn in a distribution -fretiooon-eeeeeeee learning setting, up to accuracy (see for example Anthony and Bartlett [2002]). It is formally defined as follows:
Definition 1 Shatteratt)) A class of functions F on an input domain X' shatters m points
xI,,.., Xmm X with margin e, if there exists a number s, such that for all y E {0, 10,1) m we can find some J E F such that
Vi E [m]. f(x;) S if yi = and f(x.) 28 if y/- 1
The fat-shattering dimension of (at scale e) is the cardinality m of the largest set of points in X for which the above holds.
Thus, by proving the existence of a large set of points shattered by the function class, we get lower bounds on the fat-shatterigg dimension, which translate to lower bounds on the sample complexity.
Rademacher Complexity: This measure plexity: Indeed, the number of inputs m required to make the Rademacher complexity of a function class F smaller than some is generally an upper bound the number of samples required to learn FF up to accuracy e (see Shalev- Sawlev-Shwartz and Ben-David [2014]).
be used obtain upper bounds the sample com-
Definition (Rademacher complexity). Given a class of functions Fon a domain X, its Rademacher complexity is defined as (F) = (x,((x)),, )m E, [sup]eF 1 E - (x,())))
where (e1,...,6m)) is uniformly distributed on {-1,+1)m.
Covering Numbers: This a central tool in the analysis of the complexity of classes of functions (see, e.g., Anthony and Bartlett [2002]), which we use in our proofs.
Definition 3 (Covering Number). Given any class of functions F from to Y, a metric d over functions from X to y and 0, we let the covering number N [J, d, e) denote the minimal

---

number functions fi. f2..... from X' to V such that for all f E F. there exists some f; with d(f.. f) In this case we also say that {f1, fn. is an e-cover for F.
In particular, will consider covering numbers with respect to the empirical L2 metric defined as (f, - v -i= [lf(x;)) /l? for some fixed set of inputs : In addition, if (fi, f2,..... fnr FFF then we say that this cover is proper. It is well known that the distinction between proper and improper covers is minor, in the sense that the proper e-covering number is sandwiched between the improper e-covering number and the improper 2 covering number (see the appendix for a formal proof):
Observation 1. Let F be class of functions. Then the proper c-covering number for F is least (FF, c) and at most N d. 2).
3 Linear Predictors and Neural Networks with General Activations
We begin by considering the following simple matrix-parameteriied class of functions on X {x Rdd ||x|| $ 1}:
F.Wo B.n.d = (x W Raxd IIW Wolle S B}.
where is assumed be some fixed L-Lipschitz function, and Wo is fixed matrix in ind with bounded spectral norm. As discussed in the introduction, this can be interpreted as class of vector-valued linear predictors composed with some Lipschitz loss function, or alternatively as generic model of one-hidden-lae
neural networks with generic Lipschitz activation function. Moreover, Wo denotes an entiaalization/referennce point which may or may not be
In this section, we study the sample complexity of this class (via its fat-shattering dimension for lower bounds, and Rademacher complexity for upper bounds). Our focus is on size-ineppendent bounds, which do not depend on the input dimension d or the matrix size/network width n. Nevertheless, to understand the effect of these parameters, we explicitly state the conditions d, n necessary for the bounds to hold.
Remark 1. Enforcing f to be Lipschitz and the domain X to be bounded is known to be necessary for meaningful fize-independent bounds, even in the case of scalar-valued linear predictors + f(w x) (e.g., Shalev-Shwartz and Ben-David [2014]). For simplicity, we mostly focus on the case of X being the Euclidean unit ball, but this is without much loss of generality: For example, we consider the domain {x E Rd ||x|| < by in Euclidean space for some by 2 0, we can embed by into the weight constraints, and analyze instead the class F..b, -bbbW, Wo
over the Euclidean unit ball {x RRd ||||| S 1}.
bgB.nd
3.1 Size-Independent Sample Complexity Bounds with Wo = 0
First, we study the case of initialization zero (i.e. Wo Onxa). Our first lower bound shows that the size-independent fat-shattering dimension of F..Wo
B,n,d (at scale e) is at least exponential B /
Theorem 1. For any B, 2 1 and E (0, 1] s.l.
1.
2 20, there exists large enough d 1282
@LL (1L2B"/ē), eXp and an L-Lipschitz, f : :R" - R. for which J.f. Wo=0 can shalter
B.ndd
exp(eL2B"* /2)22
points from {x Rdd ||x|| 1] with margin c, where > O is universal constant.
The proof is directly based on the proof technique of Theorem 3 in Daniely and Granot [2022], and differs from them mainly in that we focus on the dependence on B, c (whereas they considered the dependence on d). The main idea is to use the probabilistic method to show the existence of XI, Xm E Rd and W,, W,,.., Wzm Raxd for m ( /e2, with the property that every two different vectors from (W,x : E m, y E [2m]] are far enough from each other. We then construct an I-I ipschiit function which assigns arbitrary outputs to these points, resulting shattering range over W Wgm.
5

---

We now turn to our more novel contribution, which shows that the bound above is nearly tight, in the sense that we can upper bound the Rademacher complexity of the function class by similar quantity. In fact, and perhaps surprisingly, much stronger statement holds: A similar quantity upper bounds the complexity of the much larger class of all I--Lipschitz function f on IR."" composed with all norm-bounded linear functions from Rd to R":
Theorem 2. For any L. B 2 1 and E (0. s.t. LB 2 L, let V L. be the class of all L- Lipschitz functions from {x E R" ||x|] S B3 to R. which equal some fixed a IR at O. Let WB. be the class of linear functions from R to IR" over the domain {x E Rd ||x|| S 13 with Frobenius norm at most B, namely
WB. == (x + Wx: : W ERR ERaxd [[ S B).
Then the Rademacher complexity of Va o WB, == (bog 1o E V Vr.an. E WR, } on m imputs
c22g2
from {x E Rd ||x|| - 13 is at most e, if 2
LB
for some universal constant c >> O.
Since F/-Wo=D C L.,, WB.. for any fixed f, the Rademacher complexity of the latter upper bounds the Rademacher complexity of the former. Thus, we get the following corollary:
Corollary 1. Let f IR" + R be a fixed LLipschitz,function Then the Rademacher complexity of
o1.2 g²
F. on m from fx Rdd ||x|| S 1} at most c, if Z LB
2²
for some universal
constant e >> O.
Comparing the corollary and Theorem we see that the sample complexity of Lipschitz functions composed with matrix linear ones is exp (2 (regardless of whether the Lipschitz func- tion is fixed in advance or not). On the one hand, it implies that the complexity of this class is very large (exponential) as a function of L, B and e. On the other hand, it implies that for any fixed L, B, e, it is finite completely independent of the number of parameters. The exponential dependence on the problem parameters rather unusual, and in sharp contrast to the case of scalar-valued predictors (that is, functions of the form x + f(w [x) where ||w woll < B and f is L-Lipschitz/ ), for which the sample complexity is just O(L2B2/e)
The key ideas in the proof of Theorem 2 can be roughly sketched as follows: First, we show that due to the Frobenius norm constraints, every function + f(Wx) x) in our class can be approximated (up to some E) by a function of the form + f(Wx)), where the rank of We is at most B² /e2. In other words, this approximating function can be written as f(UV),, where V maps to R n/? Equivalently, this can be written as (Vx), where g(z) = f(Uz) over B2 This reduces the problem to bounding the complexity of the function class which the composition of all linear functions to RR BBB//² and all Lipschitz. functions over BR=² /e? which we perform through covering numbers and the following technical result:
Lemma 1. Let F be class of functions from Euclidean space to fx E R" ||x| S B.. Let V L.o be the class of all L-Lipschitz functions from {x E R" ||x|| I B} to R. which equal some fixed E I. at O. Letting V L.a o F.F == {bb o E v L f E F}, its covering number satisfies
8BL
8BL
log N(V L.a o FF dm, c) S 1+
log
+ log N(J, dm 4L 1
The proof for this Lemma is an extension of Theorem 4 from Golowich et al. 2018, which considered the case r = 1. We emphasize that the exponential dependence on r arises from the covering of the class V L.a, which is achieved by covering its domain {z E I",, |||||| < B} by set of points N₂ of size (1+ BL)e)" and covering its range (a - LB, a + LB by a set N, of size 2LB/e. As we will show, this implies that the set of all functions from N₂ to N2 is cover for V
Application to Deep Neural Networks. Theorem 2 which we established above can also be used to study other types of predictor classes. In what follows, we show an application to deep neural networks, establishing size/dimension-ing sireddimensoonnnideeeeeeen sample complexity bound that depends only on the Frobenius norm of the first layer, and the spectral norms of the other layers (albeit exponentially). This is surprising, since all previous bounds of this type we are aware of strongly depend on various norms of all layers, which can be arbitrarily larger than the spectral norm in iizeiindependent setting

---

(such as the Frobenius norm), or made strong assumptions on the activation function (e.g., Neyshabur al. [2015, 2017], Bartlett et al. [2017]. Golowich al. [2018]. Du and Lee [2018], Daniely and Granot [2019], Vardi et al. (2022]..
Formally, consider scalar-valued depth-k "neural networks" of the form
FA - fz Wafa- (Wa- (W] |wal S SE. Vj ||W - Sj. [WillF S B) where each W is a parameter matrix of some arbitrary dimensions, Wa is a vector and each fy is some fixed 1-Lipschitz" function satisfying (0) = O. This is rather relaxed definition for neural networks, as we do not assume anything about the activation functions fz. except that it is Lipschitz. To analyze this function class, we consider F& as a subset of the class
{ I(Wx): W SB, I: R I is L-Lipschitz)
where L 11; Sj (as this clearly upper bounds the Lipschitz constant of z By applying Theorem (with the same conditions) we have Corollary 2. For any B, 2 and e E (0, 1] s.f. E 2 1, we have that the Rademacher complexity of Fk on m inputs from {x E IR"; |x|| s 1 is at most 6, if
WaJK- (Wk-1Ja J2 (a..:/-----11.............
st 22
LB
m
where L = 11 Sj and c > 0 some universal constant. =
Of course, the bound has bad dependence on the norm of the weights, the Lipschitz parameter and e. On the other hand, it is finite for any fixed choice of these parameters, fully independent of the network depth, width, nor on any matrix norm other than the spectral norms, and the Frobenius norm of the first layer only. We note that in the azz-independeet setting, controlling the product of the spectral norms is both necessary and sufficient for finite sample complexity bounds (see discussion in Vardi et al. [2022]). The bound above is achieved only by controlling in addition the Frobenius norm of the first layer.
3.2 No Finite Sample Complexity with Wo
In subsection 3.1, we showed size-independent sample complexity bounds when the initializa- tion/reference matrix W, is zero. Therefore, it is natural to ask if it is possible achieve similar size-independent bounds with non-zero Wo. In this subsection we show that perhaps surprisingly, the answer is negative: Even for very small non-zero Wo. it is impossible control the sample complexity of B.n.d independent of the size/dimension parameters d, n. Formally, we have the following theorem:
Theorem 3. For any N and (0,, 1.1 there exists d = m + 1, 2m, Wo E Buxd with ||Wll = 2-2-c and a function f IR" + R which is 1-Lipschitz. for which Ff.Wo
B=1,ndd can shatter
m points from (x E R ||x|| S 1} with margin
The theorem strengthens the lower bound of Daniely and Granot [2022] and the previous subsection, which only considered the Wa 0 case. We emphasize that the result holds already when ||Wll is very small (equal to 2 e). Moreover, the proof technique can be used to show similar result even if we allow for functions Lipschitz w.r.t. the infinity norm (and not just the Euclidean norm as we have done so far), at the cost of a higher required value of n. This is of interest, since non-element-wise activations used in practice (such as variants of the max function) are Lipschitz with respect to that norm, and some previous work utilized such stronger Lipschitz constraints obtain sample complexity guarantees (e.g., Daniely and Granot [2019]).
Interestingly, the proof of the theorem is simpler than the Wo = 0 case, and involves direct non- non-probabilistic construction. It can be intuitively described as follows: We choose a fixed set of
"This is without loss of generality, since if f, is Lipsshhit, we can rescale it by 1/L, and multiply S441 by Lj.
7

---

vectors Xi..... Xm and a matrix Wo (essentially the identity matrix with some padding) so that Wix; encodes the index For any choice of target values y { we define a matrix W (which is all zeros except the values of half column that are located in a strategic location), so that Wyx; encodes the entire vector y. Letting Wy = W + Wy, we get matrix of bounded distance Wo. so that Wx; encodes both and y. Thus, we just need f to be the fixed function that given an encoding for y and i, returns yı, hence x + fW) shatters the set of points.
3.3 Vector-valued Linear Predictors are Learnable without Uniform Convergence
The class F which we considered in the previous subsection, is closely related the natural class of matrix-valued linear predictors (x Wx) with bounded Frobenius distance from initialization, composed with some Lipschitz loss function É. We can formally define this class as
B == (x) {(Wx;y) W E RRaxd J|W - Woll B)
For example, standard multiclass linear predictors fall into this form. Note that when y is fixed, this is nothing more than the class Fl..Wo Wo where (2) {): The question of learnability here boils down to the question of whether, given an i.i.d sample fx., y ) from an unknown distribution, we can approximately minimize E(x.y) (ex,))[(Wxx, x, y)] arbitrarily well over all W ||W -Woll S B, provided that m is large enough.
For multiclass linear predictors, it is natural to consider the case where the loss E is also convex in its first argument. In this case, we can easily establish that the class BB,n. is learnable with respect to inputs of bounded Fuclidean norm, regardless of the size/dimension parameters n. d. This is because for each (x, v). the function W + E(Wx;( x; y) is convex and Lipschitz in W, and the domain {W : 1| WollF S B3 is bounded. Therefore, we can approximately minimize Exx.)) ( x, y)l by applying stochastic gradient descent (SGD) over the sequence of examples fx, ys ) This is consequence of well-known results (see for example Shalev-Shward and Ben-David (2014]), and is formalized follows:
Theorem 4. Suppose that for any y, the function E(.,y) is convex and L-Lipschitz. For any B > O and fixed matrix Wo. there exists a randomized algorithm (namely stochastic gradient descent) with the following property: For any distribution over (x. y) such that ||x]| S 1 with probability 1, given an i.idd. sample (xx, (.).:))) F= ym the algorithm returns a matrix W such that IIW WollF S B and
BL
(((x((())))) Bw E l(
min W: W.WW -.W-Wlll Woll
((x:)(((Wx:))))
v m
Thus, the number of sumples mn required to make the above less than e is at most
1² ea
Perhaps unexpectedly, now turn to show that this positive learnability result is not due to uniform convergence: Namely, we can learn this class, but not because the empirical average and expected value of ((Wx; y) are close uniformly over all W I|W - Woll B. Indeed, that would have required that a uniform convergence measure such as the fat-shattering dimension of our class would be bounded. However, this turns out to be false: The class R.nnd can shatter arbitrarily many points of norm S and any scale S 1, for some small Wo and provided that n. d are large enough?. In the previous section, we already showed such a result for the class F.WWW which equals gf Wo when y is fixed and f(W) f(Wx; y). Thus, it enough to prove that the same impossibility result (Theorem 3) holds even if is a convex function. This is indeed true using slightly different construction:
Theorem 5. For any m E and E (0, 41, there exists large enough (m)), n ((exp(m)), Wo E Rxd with [|Wlll = 4/2- e and a convex function f R" R which is 1 1-Lipschitz with
"This precludes uniform convergence, since it implies that for any m. can find set of 2mn points (xx; yi ) such that if we sample m points with replacement from a uniform distribution over this set, then there is always some W the class so that the average value of E(W x; y) over sample and in expectation differs by a constant independent of m. The fact that the fattshat dimension is unbounded does not contradict learnability here, since our goal is to minimize the expectation of É(W WW:; y). rather than view it as predicted values which then composed with some other loss.
8

---

respect to the infinity norm (and hence also with respect to the Euclidean norm), for which F.WWo can shatter m points from {x E Rdd ||x|| - 1} with margin c.
B=1,ndd
Overall, we see that the problem of learning vector-valued linear predictors, composed with some convex Lipschitz loss (as defined above), is possible using a certain algorithm, but without having uniform convergence. This connects to line of work establishing learning problems which are provably learnable without uniform convergence (such as Shalev-Shwartz et al. [2010], Feldman (2016]). However, whether these papers considered synthetic constructions, we consider an arguably more natural class of linear predictors of bounded Frobenius norm, composed with a convex Lipschitz loss over stochastic inputs of bounded Euclidean norm. In any case, this provides another example for when icarnability can be achieved without uniform convergence.
4 Neural Networks with Element-Wise Lipschitz Activation
In section 3 we studied the complexity of functions of the form x f(Wx) (or possibly deeper neural networks) where nothing is assumed about f besides Lipschitz continuity. In this section, we consider more specifically functions which are applied element-wise, as common in the neural networks literature. Specifically, we will consider the following hypothesis class of scalar-valued, one-hidden-layer neural networks of width n on inputs in {x E Rd ||x| S ba where o-) is Lipschitz function on IR applied element-wiss and where we only bound the norms as follows:
Fo. B.B.ndd (x u (Wx): R", W Raxd ||||| S b, ||W
Woll P S B}
where u _ [T([W)) = E, [ x). We note that we could have also considered more general Namely, where the constraint ||u|| < b is replaced
version, where is also initialization-deeenee by ||u uoll S b for some fixed ug- However, this extension is rather trivial, since for vectors u there is distinction between the Frobenius and spectral norms. Thus, to consider in some ball of radius around some ug. we might as well consider the function class displayed above with the looser constraint ||u|| < b + ||oo| ||. This does not lose much tightness, since such dependence on ||np|| is also necessary (see remark 2 below).
The sample complexity of Fo.W. n.B. was first studied in the case of Wo = 0. with works such as Neyshabur et al. [2015, 2017], Du and Lee [2018], Golowich et al. [2018]. Daniely and Granot [2019] proving bounds for specific families of the activation o--) (e.g., homogeneous or quadratic). For general Lipschitz a (.) and Wo O, Vardi et al. [2022] proved that the Rademacher complexity of
Fo.Wo=0 for any L-Lipschitz (-) is at most c, if the number of samples is Ô ( ()² Theyy left the case of Wo * 0 innovative technique to prove a bound in this case, but not a fully size-independent one (there remains logarithmic dependence on the network width n and the input dimension d). In what follows, we prove a bound which handles the Wo + 0 case and is fully size-indepe iizeeindee,n,,t,, under the assumption that (-) is smooth. The proof (which is somewhat involved) involves techniques different from both previous papers, and may be of independent interest.
open question. In recent preprint, Daniely and Granot [2022] used an
Theorem 6. Suppose (-) (as function on RR) L-Lipschitz, , p--mooot (i.e, o'(-) is j-Lipchitz) and (0)- = 0. Then for any b, B, n, D.E e O such that Bb, 2 2, and any Wo such that [|Woll S Bo- the Rademacher complexity of Fo,Wa on inputs from {x RRd ||x||| S by) is at most c, if
m 2 1 (((1 (L. + (... L)B(L B)bb))))b)))))) B)b
Thus, we get a sample complexity bounds that depend on the norm parameters by, Bo. the Lipschitz parameter L, and the smoothness parameter μ4, but is fully independent of the size parameters n, d. Note that for simplicity, the bound as written above hides some factors logarithmic m, B, L, by see the proof in the appendix for the precise expression.
We note that if Wn = O. we can take Bn 0 in the bound above, in which case the sample complexity
scales Ó((( + B)) This is is the same in Vardi et al. [2022] (see above) up the dependence on the smoothness parameter J..
Remark 2. The upper bound on Theorem 6 depends quadratically on the spectral norm of Wo (iee Bo). This dependence is necessary in general. Indeed, even by taking the activation function o to

---

be the identity, B = 0 and b = 1 we get that our function class contains the class of scalar-valued linear predictors {x + v x X, v R R=vllvil S Bo}. For this class, it is well known that the
ensure that the Rademacher complexity of that class is at number of samples should be O Pi most e.
4.1
Bounds for Deep Networks with Lipschitz Activations
As final contribution, we consider the case of possibly deep neural networks, when Wo = 0 and the activations are Lipschitz and element-wist Specifically, given the domain {x E Rd ||x|| S 6,) in Euclidean space, we consider the class of scalar- valued neural networks of the form
X + W 0- 1 (Wx-100-2(.... ((Wi)))
where We is vector (i.e. the output of the function is in IR) with ||wa|]| S b. each W, is parameter matrix s.t. |[l & Bj, || S Sj and each , (as a function on IR) an I.-Lipschitz function applied element- wise, satisfying or (0) 0. Let F(a;) (B,)))(BB)) be the class of neural networks as above. Vardi al. [2022] proved a sample complexity guarantee for k = 2 (one-hidden-layer neural networks), and left the case of higher depths as an open problem. The theorem below addresses this problem, using a combination of their technique and a "peeling" argument to reduce the complexity bound of networks of depth A: to those of depth (k 1).. The resulting bound is fully independent of the network width (although strongly depends on the network depth), and the first of this type (to the best of our knowledge) that handles general Lipschitz activations under Frobenius norm constraints.
Theorem 7. For any b, > 0, ( with Si...., 1,-1, 2 1, the Rademacher complexity of F(a,}
(B,)) inputs from fx E Rd ||x|| - by is at most if
kT.. < -2 log الططل
(m)
B
m
where Ry-2 bbLk 2 II
S,. Ro by and is universal constant.
We note that for k = 2, this reduces to the bound of Vardi et al. [2022] for one-hidden-layer neural networks.
5 Discussion and Open Problems
In this paper, we provided several new results on the sample complexity of vector-valued linear predictors and feed-forward neural networks, focusing on size-independent bounds and constraining the distance from some reference matrix. The paper leaves open quite few avenues for future research. For example, in Section 3, we studied the sample complexity of F/.W, B,ndd when n. d are unrestricted. Can we get a full picture of the sample complexity when d are also controlled? Even more specifically, can the lower bounds in the section be obtained for any smaller values of d, n? As to the results Section 4, our Rademacher complexity bound for Fo.Wo (one-hidden-layer networks and smooth activations) the tightest possible, or can it be improved? Also, can we generalize the result to arbitrary Lipschitz activations? In addition, what is the sample complexity of such networks when n, are also controlled? In a different direction, would be very interesting to extend the results of this section to deeper networks and non-zero Wo.
Acknowledgements
This research is supported in part by European Research Council (ERC) grant 754705, by the Isracli Council for Higher Education (CHE) via the Weizmann Data Science Research Center, and by a research grants from the Estate of Louise Yasgour.
References
Martin Anthony and Peter I.. Bartlett. Vapnik- Chervnnchervsnnniis Dimension Bounds for Neural Networks, page 108-130. Cambridge University Press, 1999. doi: 10. 00.1017778809888551622266.66.
10

---

Martin Anthony and Peter L. Bartlett. Neural Network Learning- Theoretical Foundations. Cam- bridge University Press, 2002. ISBN 978-0-521-57353-5.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(No)):4633444 482, 2002.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally-normaliie margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
Amit Daniely and Elad Granot. Generalization bounds for neural networks via approximate descrip- tion length. Advances in Neural Information Processing Systems, 32, 2019.
Amit Daniely and Elad Granot. On the sample complexity of two-layer networks: Lipschitz vs. element-wise lipschitz activation. CoRR, abs/221 1.09634, 2022. doi: 10.48550/arXxv.2211 .09634.
Amit Daniely, Sivan Sabato, Shai Ben-David, and Shai Shalev-Shwartz. Multiclass learnability and the erm principle. In Proceedings of the 24th Annual Conference on Learning Theory, pages 207-232. JMLR Workshop and Conference Proceedings, 2011.
Simon Du and Jason Lee. On the power of wer-paraaeerizatioo in neural networks with quadratic activation. International conference on machine learning, pages 1329-1338. PMLR, 2018.
Vitaly Feldman. Generalization of erm in stochastic convex optimization: The dimension strikes back. Advances in Neural Information Processing Systems, 29, 2016.
Margalit Glasgow, Colin Wei, Mary Wootters, and Tengyu Ma. Max-margin works while large margin fails: Generalization without uniform convergence. In The Eleventh International Conference on Learning Representations, 2022.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. In Conference On Learning Theory, COLT 2018, volume 75 of Proceedings of Machine Learning Research, pages 297-299. PMLR, 2018
Sham M. Kakade, Karthik Sridharan, and Ambuj Tewari. On the complexity of linear prediction: Risk bounds, margin bounds, and regularization. In Advances in Neural Information Processing Systems 21, 2008.
Kaifeng Lyu and Jian Li. Gradient descent maximizes the margin of homogeneous neural networks. arXiv preprint arXiv: 1XXi::990600580) 2019.
Andreas Maurer. A vector-contraction inequality for rademacher complexities. In Algorithmic Learning Theory: 27th International Conference, ALT 2016, Bari, Itll, October 19-21, 2016, Proceedings 27, pages 3-17. Springer, 2016.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018
Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain generalization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on learning theory, pages 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally- normalized margin bounds for neural networks. arXiv preprint arXiv: 1707.09900 2017.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, 2014. ISBN 978-1-10-705713-5.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability
and uniform convergence. The Journal of Machine Learning Research, 1 11:2635-2670, 2010.
Nathan Srebro and Karthik Sridharan. Note on refined dudley integral covering number bound. URL
https: htww///ww.cooo/ooooo http:/wwww....eellllll///
cornell edu/~sili htt///sridharrrr hiddaaa/ddddllyyy d/ddey.dyy.....//ooo .pdf.
Gal Vardi, Ohad Shamir, and Nathan Srebro. The sample complexity of one-hidden-layer neural networks. CoRR, abs/2202.06233,, 2022.

---

A Proofs
A.1 Proof of Observation
The first part follows immediately from the definition. For the second part, let =- N d, 5) and N = (9,,,.., 9k be an 5-cover for F. For every 9; E N, let f; E F be some function such that d(f(. I 2: there must exist f, with this property, otherwise we can remove 9i from N and still get an --coeer for F, contradicting the minimality property of the covering number. For every f E let gi d(J, S d(Si,g)) + d(g.,) f) S Therefore (J1...,, [k....]]]]] a proper e-cover for F.
be the function with d(gr, f) S 5. then by the triangle inequality
A.2 Proof of Theorem
We use the following lemmas from Daniely and Granot [2022]:
Lemma 2. For d > 20, there exists set of vectors X1,...,,, Xm E TRd and set of matrices W1:-.. 2m E Igadd with (exp(d)) that have the following propertiex:
1. |x L, for each [m]]
2. m TÜ
3. [|aal?? 2d, for each [2
4. [[, 2 f. for each i, E [mi] and 8, L, E 12Th s.I. (8, + (1,5)
Lemma 3. Let X1,..., Xm be a fffiite set of disferent points in some metric space (X, d). such that for each # [mm), d(xi, xj) 2 Let further be Ply..--Pm T. any set of points. Then there exists an
f : X - IR where
2
L min max lps C
a C20 [m(m]
such that for each i [m], [(x:) Pc-
Proof of Theorem I. Let 2 1, e I 1, and d that will be chosen later. Let X Xm. R and Wi. ... W E R be the vectors and metrices that are defined in Lemma 2. Note that (ee and m = (n).
Let W, 8e W for each s E [2 By property from that Lemma we have that | < 128de2/L'* for each E [2" Thus, by setting : _ J. we get that ||Wllle S Moreover, have that m (n)) 20(12B²/e)) By property 4 from that lemma, we have that the set Q (W,x;: [m],s E [2 contains m22 different elements such that for each pair W,x; + W,X,
L.
we have
8c I
2c L I|W' W/x,
[W, W
Order the elements of the set 2mm as Si, g:
Sym some arbitrary order, and define the function
m
2 + { as:
g(k, fe i E S i Sk
Apply Lemma with the Euclidean metric space, to get an L-Lipschitz function, : - IR, such that for all i [m], [2
f(W,x,) = ik
Moreover, we have that x + f(W.x) belongs to Ff= for each s [2r"]. Therefore, Wo= can shatter (n) exp (0(L2B?/2)) points from {x E Rd ||x|| S 1} with margin 0
12

---

A.3 Proof of Lemma
Define the Lo distance
dxo(g,g)) = sup [1f(z) f2)ll,
=E2
where 2 is the domain of g and g'. Let Up Observation 2 there exists set N₂ IR" with |N + SBL for every Ug, there exists x' E N₂ with
{x Rd x|| S B} and fix O. By
c ||x x'1 4L
Note that (x) E BL, + BL] for any & E V Vr, X E Un. For simplicity, we assume that 0 (the proof for any other a essentially the same). Let Ny. = {0, + i + 5...... ....... BL/4e 4e) be 1-cover for the closed interval [-BL, BL]. Given any & E V L,a=0 and x E Ug. construct vi/ .N2- Ng as follows: let be the point in N₂ that is nearest to x, and let (/((x) be the point in Ny that is nearest to (xx'). We get that
(*)x) (x) S (x) xxxx1+++++ 1wxx) of (x) ++ (x)x))
< -- ||x - x
2
The number of such functions is at most
|all
therefore
log I doa: 9) = NN log|/,,)) = -11 8BL
8BL
log
Next, we argue that
log N (( 1.e=0 F, dm, e) S log N (V doa: 5) log N NFF (F,dms aT.)
from which the result will follow. To see this, pick any vi E v1.=0 and g F. By observation I there exists a proper 37, -cover for F of size N(F, dm. ) Let V : be the respective closest functions in the cover of V v,a=0 and the proper cover of J (at scale á and z7 respectively). Since g' belongs to proper cover e.g. g' E F, its range is Up. By the triangle inequality and since vp is L--Lpschitz, we have
dm(Vg v'g S dm (vgg vgg') + dm (vgg', i .''') s dm (mg vg'' do (''g)
L dm (g. g/) + dig' )'g') <
A.4 Proof of Theorem
Observation 2. Let Ug = fx E E |x|| S B} and e > 0. There is a set N S Ug with
(B/c)* & NI s (1 20)" such that:
1. For every x E Ug. there exists a x' E N with ||x- - x'|l < <N is an e-cover for Ug).
2. For every x,y E N, we have that ||x y-- E (N is an e-packing for Ug).
Proof. This is a well-known volume argument. Let fx E RT |x|| S B} and fix some
Choose N to be maximal c-packing (c-seperated) subset of Ug. In other words, N C MB is such that for all x, N2 x y y and no subset of Ug has this property. The maximality property implies that for every x E Ug, there exists x' E N with ||x x' S c (i.e. N is an e-cover for Ug).. Otherwise there would exist x E Un that is at least e-far from all points in N. Thus NU (x) would still be e-eeaarated set, contradicting the maximality property. Moreover, the separation property implies via the triangle inequality that the balls of radius centered at the points in N are disjoint(up to null set). On the other hand, all such balls lie in (B B) where B denotes the unit Euclidean
2 ||-
13

---

ball centered at the origin, Comparing the volume gives vol ( B2) INN S vol ((B + 5) B5)
and
|N] . (o)) 2 vol(B. B B²). Since vol(cBī) = c'vool B5) for all 2 0 we have
|N Σ vol ( 5) Bb)
B
vol (5 Bi)
2
N cBl Bb)
B
vol(E B5)
We conclude that (0) - N & (1 yr required.
The next lemma is shown in Corollary in Kakade et al..
Lemma 4. Let W {x + (w,x) ||| B} be the class of norm-bounded linear predictors over inputs from {x x < 1). Then for every > 0
cB² =2
log Ngg,W,,dk dm e) 1
for some universal constant c O.
Lemma 5. Let
F F= Wx W E ERdd | < B} be class of functions over inputs from {x |X|| S 1). Then for every >
2
log NF,, dm, 6)
2
for some universal constant O.
Proof. Applying Lemma 4 with e' VF we get a class of functions No with |NNwl B such that for every function fw W: fx w x: /w|| B), there exists far Nw with
dm(fur fuo) s Vr
Now we are ready to define a cover for F. Let
N
{(x), x,) -
13 E No).
Let E
F be f(x) Wx. Then
f(x) (w) x,... w, x).
where w, is the j-th row of W. Define fx() == w/ Since |Wlle S B, we have that l/w, $ B, in particular fy E W. Remember that No is cover for W, so there exists f/ E No s.t.
dm(ss,ff) s Vr
Let 8' E N be the function
fx() = (x)())... .... (x)).
Hence,
m dm dm (f) Σ [1((x)) - f((x)) m 1=
ΣΣ
- - f5(x2)11 Σ
- -
1=1
j=l i=1
Σ dm (f,, 22 1=1
Therefore, N an e-cover for with
ozd2 (2
cx2 n2 ,2
|N| |Nwll"
,2
= 2
14

---

Proof of Theorem 2. Assume for now that L = and let W E Rnxd be matrix such that | 1 S B. The singular value decomposition of W is factorization of the form W = USVT, where E R and V Rdxd are orthogonal matrices and S E =x is a diagonal matrix with non-negative real numbers on the diagonal. We also can assume W.L.O.G that the upper-left submatrix of S is of the form "i, minu(d.))) and that 0 2 ... 2 miin(d,n) Let W. :- U., V be a low-rank approximation to W. where, Se is defined by setting all the elements in S that Σ to Formally, let r E [min me, d]] be the largest number such that 0, > e (or 0 if no such number exists) and partition U, S and V follows:
Si 0 U2 1,S-=
U -
Vi
V2
S
where U1 E RRxx,, S1 = ( σr) E <Rrx and V E Rxxd We define
5. = 8 0 0
which means that W. = U.S.VVT. The proof strategy consists of two parts: First, we argue that W. approximates W in spectral norm. Second, we argue that W. has low rank, so it is enough to find a small cover for the class of functions L= WB.r where r == rank (W). to get a small cover for V.a..n WB... Details follow. Let x E IRd such that ||x[] S 1. Since U an orthogonal matrix, we have that |Ux||| ||||| < 1. Moreover, since the spectral norm of a matrix is equal to the largest singular value
||S - -511 = ||S = S
Altogether we have
||Wx Wx|| = IUSV x- U.SV x = ||SV x V S IS 5.11
||V xx| S
which means that W. indeed approximates W, in the sense of the spectral norm. Moreover,
min {d.n}
B² M W =
Σ
and since of 2 2 for each i S r, we have that r S
B² Thus, we have that Rank(W.) =r = B² 62.
2
If we approximate W up to then we can argue that for each f E v L=
If(Wx) f(Wxx) S |Xx Wxx| Sc.
Define
W. (W. || S
then we have by the triangle inequality that
log N(W L=1.e, W, dm 26) S log L= 0 We d)
(2)
Therefore, now turn to find small cover for
I.=1lan o W. C
B² f(Wx) x Rd, W gaxd [[]]e s B, Ronk(W) = 2² Wi=L.am
Remember that by the singular value decomposition, if Ran = r, then W = USVT where U E Rexr diag(o)....,0 o,) E Rexr and V Rxx Also, U and V are orthogonal matrices.
and || < B. Thus, the class from above is equal to
B² { f(USVx) U. are orthogonal, S = diag(o1, ... or), S B,r é 2 f @VLLIa
15

---

Now we want to get rid of U. Observe that
{U' + f(Ux) U is orthogonal, / E Vn.=l,an) C Vi.llam
where we remind that V -=1.a.r is the class all I-Lipschitz functions from (x E R": |||| S B} to R, such that f(0) for some fixed E R. Moreover,
or), or) B,r= B
x SV x V is orthogonal, S diag(o ...
x x
B
v R oo E l/ = - B²
2
where vi is the i-th column of V. Combining these observations, have that the class of functions defined in Equation 3 is subset of
B 22
x - Sww]x x, w, x) S Vi Σ [|wll?== B²,
V V- o WB.--
(4)
This class is composition of all linear functions from R& to R² of Frobenius norm most B, and all I-Lipschitz functions. The covering number of such linear functions analyzed in Lemma 5, and the covering number of such composed classes analyzed Lemma 1. Altogether, we have that the covering number of the class in Eq. 4 is upper bound by
log N N(VL=1.a,r WB,r, dm e)
1+
8B -e
log
8B
+ log (WB,,, 2)
= (1
8B
8B
B B²
log
for universal constant and constant that may change from line line. Combining with Eq. 2 and the assumption that 2 1, we have
Ba
From this point, 0 represents some universal
2
B
log (N W, dm, e) <
Observe that c. V W=1lan V L=ccea,n for O, and hence it is easy verify that N( L=1,a.n W, dmn c) = N(V W,dm Therefore, for general L-Lipsehitz functions we have
2n2
LB
log (N o W, dm. c) S
To convert the upper bound on the covering number to an upper bound on the Rademacher complexity, we turn to use the Dudley integral covering number bound (see Srebro and Sridharan). In particular, since g(x) < LB for each g E L, WB,, and x E Rd with |X|| S 1, we have
Rm ( L.a,n o WB.n)
< inf E20
4e
12
LB
V Vlgg N NN WB, dmn r)dT
mm
12LB
12LB
inf <20
+
V
log NVVi.an
L.a,n Wi, dmn
S inl e20
+
Vm V
log NNV maam o WB dmn
vm
2
e22
12LB
LB
inf <E[0.1]
+
(5)
2
m
Moreover, there exists universal constant d' O, that for any e E [0,
1], if 2
(B
then
eL2g2
12LB
LB
mm
E
2
16

---

Combining with Eq. 5, the Rademacher complexity of LL,.. o WB. on m imputs from {x E R
LB d2
||x|| I 1) is at most e, if m 2
A.5 Proof of Theorem 3
Let e denote the indicator vector in RS with value one in the i-th coordinate, and value zero in the other coordinates. d is clear from the context, we just use e; for simplicity. Let d = m + 1 and
2m. Let : Xm E (0, 1]d be defined by
1 V2 (e + od mn))
Let E (0, }] and define
I Imxm 0mx1 0mx(mn+1)
Wo = 2.2
E Ruxd
By observation 2 (part 2, with B = 1, 6- = 1/2), there exists Zi, ... 62 E Rm
such that || <
1, || 2j 2 1/2 for any i.j E [2nh] + For any y E {= associate different number from [2rh] and we denote this number by y. For any E [2 define
0mx1 Zy
Opxxm
E Ruxd
where by E 10,1) 1m is a column vector. Note that
1
0mx1
Wox: 2e
R", Wixi
Rr.
0mx1
V2
Zy
Let W,, Wo + wy for each y E [2 then
2c edt (1/v (1/v2)zg
]
W,x;
for all E [m]. Thus,
2c(e +g) [ Wixy (1/v2)(z, ze
]|
2
for each i,j E [m] and y, E [2n] s.t. (y, i) * (1,j). Note that the last inequality holds since < 1/4. Apply Lemma 3 with the Euclidean metric space, the set Q { [W,,; i [m]. E [2 that contains m22 different elements, to get a 1-Lipchitz function f R" + such that
f(Wxx;) yt
Vi [m]. y E [2 { m
Moreover, note that since | FF 1, we have
IW, Wollr |[ $ | 2v2
Namely, we have that the function f(W,x) belongs to Ff.Wo B=1,ndd with [Wll| = 2-2-c for each
3/ E [2 Therefore, F can shatter points from {x Rd ||x|| S 1} with margin
A.6 Proof of Theorem
This theorem is adaption of Corollary 14.12 (page 197) in Sawlar-Swwarz and Ben-David [2014]. The stochastic gradient descent (SGD) algorithm, with projection step and initialization at Wo. is describes as Algorithm above. Observe that we just describe plain SGD on convex Lipschitz stochastic optimization problem (over matrices, which is vector space). The only nonstandard thing is the initialization at Wo and the projection around Wo instead of O. We state the key technical result as Lemma (in turn an adaptation of Lemma 14.1 from Shaley-Shwar and Ben-David [2014]), and sketch its proof for completeness.
17

---

Algorithm Stochastic Gradient Descent (SGD), with projection step and initialization at Wo
parameters: Scalar 17 > 0, integer T > 0, vector Wo
initialize: W(L) = 0
forl= 1,,..... do
Sample (Iz, 3/)
pick subgradient V of &W, vi) w.n. We update ((++ (()) n/
update W(+1) arg min
W w((+))
Projection step
end for
output: W + EE ((
Lemma Vi,..,, VT be an arbitrary sequence of matrices. Any algorithm with an initialization W1 Wo and an update rule of the form
w(+++) ((t) 7/V
W(++1) = arg Wolll
W w(++
satisfies
W Woll.
Σ (w W Vi)
"
II
2n
where (U,V) Eng Un, Vi.j- In particular, for every B, T. >> 0, for all we have that [Vell $ T
and if we set 17 v LT, then for every W* with | -WollF S B we have
T Σ (w W", V)) < VT 1=
BL
Proof sketch of Lemma 6: Lemma 6 different than Lemma 14.1 in Shalev-Shwartz and Ben-David [2014] in two aspects: first, add projection step, but still Lemma 14.1 holds (see Subsection 14.4.1 from Shalev-Shwartz and Ben-David [2014]). Second, the initialization is at Wo and not O, but this is also not problem since that at the end the proof Lemma 14.1, Shalev-Shwartz and Ben-David [2014] showed that
Σ (w W Vi) S 2n
n Σ M 2
In our case ((1) Wo. this proves the first part of the Lemma. The second part follows by upper bounding Wo W by B, V by L which is true since fis L-Lipschitz, dividing by T, and plugging in the value of 17.
With Lemma hand, the rest of the analysis follows directly as Corollary 14.12 Shalev-Shward and Ben-David [2014], only instead of Lemma 14.1 from that book, we use Lemma 6.
A.7 Proof of Theorem
Observation 3. Let f1...., fi be LLiischitz,functionn from IR to IR with respect to the Lp norm (with E [1, ool), then
f(x) = max (x(
15iSk
is also an funiiiooit with respect to the Lp norm.
18

---

Proof. First, we show known property about Lo.. If E R², then
max 34 15i5k
max Vil ISiSA
S max
J. Yil
(6)
1
Indeed, assume that max; 24 max; Dr- In this case, have
max x; yi maxI; max
let us denote by tn the index in E [k] such that Fig = max, 25. Then we have
zi max yi Tio max yi I Fio Vig max(x; ye) max [.; Vil-
The case max; y4 2 max; 2; symmetric. By Eq. and the assumption that fi is L--Lipsciizz for each i E [m] we get
lf(x) f(y) = max fi(x) max fi(y)] & max [f(x)) fi(y) & L||x - x-lb
from which the result follows.
Proof of Theorem 5. Let e denote the indicator vector in IRd with value one in the i-th coordinate, and value zero in the other coordinates. If d is clear from the context, we just use for simplicity. Let m + and n 2 + m. Let X1,..., Xm {0, 1}d be defined by x; v2 (ef ed +1)) Define
1
Imxm 0mxi
Wo = ..
RRaxd
Ozm x2mx(m++) (m++1)
For any E { we associate different number from [2 and we denote this number by For any y E [2nh] define
W
Onxm
O
By
where By E {0, 1) is column vector. Note that Woxi 4e e, and Wxx, 1 " Letting
W, Wo + W y> we have that
1
Wy 4c0, +
a
V2
m+y
Now are ready to define ʃ R RR
max f(x) [e[m].=E(("" [2 s.t.y
(0.5 ef + +m x;
(/8 +e),
v8
for any j [m]. 2 E [2mh] and x E R We emphasize that z E {+c} is the vector that associated with the number z E [2mh] By Hölder's inequality, we have that
(0.55 c. + 0.5 2 Tx y)1 ||0.5 cj + 0.5 en ch ||x (ix-ylon ylloo I |x yl
for any x, E R", Therefore, the function x - (0.5 e" + 0.5 -. em x is 1-Lipschitz with respect to the infinity norm for each j E [m]. E [2mh. This implies by Observation that f is also 1-Lipchitz function with respect the infinity norm. Since the composition of affine map, nonnegative weighted sums, maximum, and adding constant are all operations that preserve convexity, we have that ff is convex function. Finally, for any y E {+e) and x, have
If y; = e, then
f(W,x,) f(4ce, + (1/V2)em
(0.5e) + 0.5e (Ace," + +ejtm) -
max jc 2 s.Z,
(0.5e," 0.5ee (Ace," + (L/V2)ee (L/V8++)))
19

---

If = c and exists & E [m] with yk = e, then
f(Wxx:) = S(Ace) + (1/V2)em myy)
(0.5e) + 0.5e (4ce, (1/V2)e" my))) -1/V8++ - s...y me
max
]e(m]]=c
(0.5e) + 0.5em.ty) 1 (4ee) + (1/V2)e -
(L/V8 +c) =-,
where in this case, the max obtained for some [m]] with y& =c
Otherwise, for every k have yk -e, then
f(W,x,) = f44co +
In all cases, we get that
f(W
Therefore, B=l,nd with |Woll| v2 4e can shatter points from {x E R ||x|| S 11 with margin
A.8 Proof of Theorem
Lemma 7. Let a R TR be L-Lipschitz and p-smooth. Let I T (when 1 := (1, 12, Iz) = R2) be the function (I, 7 d(vxty)-aip Olub² + Li-Lipschitz.
If 11 = [-b by] and Is = (0, 00), then ub is
Proof. We show that 2a is Lipschitz in each coordinate, which implies that va is Lipschitz. To that end, it is enough to upper bound the norm the gradient:
= (
dub dr
del
2
dub
2
dv
du
dv
V
+
+
I 0
+
dy
dv
dx
dx
dx
Indeed,
dg/
vo vo'(w: + y)
< L.
dx
Since (-) is y-smooth, namely d-() is p-Lisschitz we have
dub
o'(ux + v) (y))
4 vr
11 1||1 I pbz.
dy
Moreover,
dvb
uxro (vx + y) - (o(ez + v) 0()))
o (o(ex + v) + o o'(vr' + (x)=
du
22
0²
Note that ayy) (a y) d'(ux + v)( is exactly the reminder between a (y) and the first-order Taylor expansion of (vv) at uæ y. In Observation 4 we analyzed such reminder of smooth function and thus we can upper bound the above equation by
(wx)
12 22 2
2
where is a middle point between y and vx + y. Therefore, vb is a O(ub² + Li-Lipchitz function, as required.
Observation 4. Let a R + R be continuously differentiable function. For all x. y E R, the first-order Taylor expansion of (g) at define by o(z) + o' (') x), and the reminder R. is define by
oly) (xx) + to' ( x) + R.(y)- (o(-) is a p-smooth i.e. d'(-) is L-Lipschitz functionn, then
(2) <
# y 22
2
20

---

Proof. Since o-) is continuous, we have that
L (d'(x My (1y+((ly))) z)) ( d'(x) (y x)d o d' - x),
then we can write
a (())= x) x)+ (d'x+ttly x)) d'(x)) (y z)dt.
Since (()) a j--mmooth
R.(1)) - (o 2)) - o'())) (y r)dt -
L ((o -o) (y x)) S ply a12 S[¹ ldl 2/ x=|
Lemma 8. Let v/ R + be an f-niischitefuunctinn.
function. Namely for all a, 3 E R² we have (v((a)
((3) & L|la - B11. For fi.... functions from R to R and x E R4, let vo (fi,.., fx)(x) = (fi(x). ..... fx)). For FI...., class of functions from R.d to R, ler
wo (FI...,Fh Fx) fx (f fx)( f1 E A...A...EEE..
Then,
log N (1v (Fi, Fh), dm, viLr) & log N (F1, dm, r) + + log N ((Fk: dm, r)
Proof. Define B = to (F1, ... Fa). Let Fi, Fy be r-covers of Fi,..., Fu respectively. Define B' 3 o (FI,..,, Fra). For all fi E Fi f& FR. there exists fí E F1, ...,.... fh E F s.t.
dm Sr
For = 1,....k. k. Therefore,
1 m
dm((/f1,.. ..... fa),
vbb (f1 ..., fa)(x)) v (fr...., fx)x))))
m
2
[[i(x)) [(((x))... (.. fxx:)) T1?
L
(fi(x:) 1(xx))) +... L Σ fx
==1
d' (f1, f1)2 ... + L'd (fx, f2)² < kI
Hence, B' is an (VkLr) - cover for B. Moreover, since |B' S F 1F we have
N(w o (Fi, Fx), dmy Vilr) S fm, N(F dm,r)
Lemma 9. Let F (x (w. x) ||wl| B) be the class of Euclidean norm-bounded linear predictors. Let and > be some parameters, then for every e E (0, L.).
1. Vlog N NFF, dm, e)
cBh
2. f Vlog NF, dm, kT)dT I cBb (log(L) log(e))
For some universal constant c 0.
21

---

Proof. The first part of the lemma is shown in Corollary in Kakade et al.. For the second part,
J." VN(F, dm KT) {/ cBbb
cBbb (log(L) log(e))
dr
kr
k
Lemma 10. Let B 2 2 and let F= (x E (0, } be the class of constant functions. Let L> 0 and k > 0 be some parameters, then for every E (0, l..
1. log (F, dm c) $ (B)
2. ft Vlog (F, dm: kr) s 2log, B) (log( ()) - log(e))
Proof. Using numbers
represent every number in [0, B] with accuracy of c Thus,
NF, (F,,mm $) < n. namely log (FF, dm.e) < log([ # < B) for each 0 < S and B 2 2, which proves the first part of the lemma. Moreover,
c/. 2lg //"
Kt dr 2lgg(B) [log()) - log(e))
V log N(F, dm, kt ddT S
k
Proof of Theorem 6. Fix some set of inputs XI, Xm with norm at most by. The Rademacher complexity equals
1 T
m
E sup
ev ((W + wo)x;
sup |
Σ
co
Wox,)
||
m
m
b
m
m Σ
b m
$ E
sup
(W + Wox;)
Go (Wox;)
+
Σ co
(7)
m
W
Let's start by upper bound the right-hand side of Equation 7, namely
b
E Go (Wox,)
m
By definition of the spectral norm, have that Woxil S Boba- Since o-)) is L-Lipschitz and (0) = 0 we have that (Woxs) < LBobz. Let yi = o (Wox)) where ||uall S LBobz. Then the expression above equals
2
b E
b
-
Σ 1=1
Ei
Ei3/
E
EdVi
E
Eiflis
j=1
1=1
b
b
m
LBabb
2
1|ai11
<
(8)
m
m
vm
1
Moving back to the left-hand side of Equation We have
let = x/1 |x| for any non-zero x (or 0 for x 0).
E
sup
(o Wox;) Σ (o(x)
[W]]FSB
2
b
<
sup
Σ
Σ c (a bb, xi) - obb w ,o,xx,i))
m
where Wo, is the j row of Wo.
22

---

Each matrix in the set {W: : F S B) is composed of rows, whose sum of squared norms is at most (Bb2)². Thus, the set can be equivalently defined as the set of d x n matrices, where each row j equals ; for some v; > 0. ||wl|l I 1 and ||v|| < (Bb,)². Noting that each f is positive, we can upper bound the expression in the displayed equation above as follows:
E
sup [|v| lisllls
(ol1,,, x, by wo o
olb2 (baw oo (osxx)))
E
sup
[o(o;w] +b 0 (be wo)x
||v|l
-
E
sup || vlls Bb. 1111
Σ of?
(o(,,,]
(o(u, x + bb ob (bb {x:)
f/j
1=1
For any choice of c, v and W1, wi, Wa. the expression inside the expectation above can written as
T
sup ||v|||
sup E (Bbb))
for some numbers d1,..., On- Clearly, this is maximized by letting v'y. Bb, for some j E arg max; af. and vy = 0 for j + jr. Plugging this observation back into the above expression, we can upper-bound the displayed equation by
bBby E
Σ
(o(u,w)
x; + b, a abb, (bbn
sup
max
Bl.
Uy
Since the spectral norm upper bounds the norm of each row in matrix, we can upper bound the above equation by
bBb S
m
E
sup
(awww) Tx, + wy x;) - ob..wo oi))
m
vE(0,
wo
Let 1b: I R be
(a, y. v) olva + v) o(v)
v
where I = [] x |- BBbb, Bob x - Bb,, Bby). Note that | x, S |w |||||||||||
S
1 and
1b x,| < || ||||||||| < Bob,. Therefore we can upper-bound the above expression by
bBb
E
sup wE (E ].I]
Xx, Ga (w X,, wo Tx,, v)
(9)
wo 2
By Lemma we have that d is c(μ L) -)-Lspcchitz for some constant By Taylor expansion and the fact that (-)) is smooth we have that (B3) o + 3) + o' ('()) where is some middle point between 3 and va + 3. Therefore,
((a, ovva + B) - ( o' (1))()v -ao
since |a|
< 1 and |o' 17)( < L, we have that eb is bounded on by L. Let
F = {x - (w T x, wo Tx, v) ||w]] s 1, 1,//woll S Ba, ||vl|| S Bba),
Fi = (x - w T x: [w] < 1}.
Fz = (x + wo Tx Wo S Ba).
Fa = [x + Ne:EE (0, Bb
23

---

Considering Equation 9, this is b times the Rademacher complexity of the function class vó o F. For every E > O, using the Dudley Integral (see Srebro and Sridharan) we can upper bound the Rademacher complexity of to o F by
+ 12 / log (( Olbbo,dde F, T)
dr.
m
From this point, > 0 represents some universal constant that may change from line to line. By Lemma 8 (with lo we can upper bound the above expression by
log ( dm p+L 4c + 12 f log ( dm #+L dr + 12 /"
/
log ( dm, ptt) dr.
dr +
m
m
By Lemma and Lemma 10, for any E 2 O, we can upper bound the above expression by
4e + c(u - Li) (log(L) log(e) Bab, log(L) Boby log(e) + log( log(Bbx) log(t))
Vm
By choosing e
we can upper bound Eq. 9 by
Vm
4 cu + (log(()) + log(m) + Bob log(L, L) Bub, log(m) + looo log(L) + log Bb,,) log(m))
Vm
Combining with Eq. 8, we get an upper bound on the Rademacher Complexity of Fo.Wo B.B.ndd of the
form
4 + duu L)bbb,, (Log(L) + log(m) Bob, log(L) + Boba log(m))
Vm
cp L)bBbb (log( Bl,,) log( L) + log( (bb)) log(m)) L.Bobb m
mm
Upper bounding this by and solving for m, the result follows.
A.9 Proof of Theorem
x(a))
To simplify notation, we rewrite
k.(8,)_1B,} simply Fg. For convenience, for any 5 S k define the class Fi slightly differently, Each function in Fi has the form
x x <W ((Wx))
(10)
with the same constraints on the weights and the activation functions. We also define Fo to be the class that contains just the identity function. The next Claim captures the "peeling" argument. Lemma 11. For any integer S slsk-
!)
E sup SEF
1
(x;)
2cBBL
R + log (m)E
sup JEA-1
1 m 1=1
Σ
Vm
1=1
where Ry-1 T.
W -
1| .... Wi|l Ry by and >> O is universal constant.
Proof.
1
m
E sup SER
-
(x,,
sup
sup
Σ
G. WiS(x;)
m
m
IEFi1
Wi
1
E sup
sup Wi
Σ
EoT (w] f(xx))
FEFL1
==1
where w, is the j-th of Wi. Each matrix in the set {W |||e - Bt} is composed of rows, whose sum of squared norms is at most B3. Thus, the set be equivalently defined as the set of

---

matrices, where each row j equals ij w for some 0j > 0. / each By is positive, we can upper bound the expression in the displayed equation above as follows:
|| - and ||v < Bf. Noting that
1 E sup sup m
Σ
Σ
(1/w] f(xi)) f(xi))
ca
feFi-1 wy.0
-E B sup sup feFi-1 Wy.0
U
fi oj (2/w] f(xi)) f(x)))
U
E sup sup feJi-1 Wa
Σ
f(x1))
Where 1/v/|| B? (note that must also satisfy this constraint). Moreover, for any choice of c, v and Wi..., Wn. the supremum over v' is clearly attained by letting o/-- Bt for some jr. Plugging this observation back, we upper-bound the displayed equation by
B E sup sup max m FEF Wg.V
Σ U
(0,w3] f(x)))
B E
oi (ow [(x:))
sup
sup
fETi-1 wil (1
Bi
E sup
sup (L.
Σ capo (w [(xi))
(11)
m
fET
where (2) (1(2)) for any 2 E R. Since of is L-Lipschitz, it follows that (.) (.) is also L-Lipschitz regardless of u, since for any 2, 2 E R,
(w(()) (b)() (o(uz) - o(uz')
L v'zl L|= z'1.
As result, we can upper-bound Eq. 11 by
B
m Σ E (w f(x:))
sup
sup wellwl| L.V.
m
JEF
where L is the class of all L-Lisschitz functions which equal the origin. To continue, it will be convenient to get rid of the absolute value in the displayed expression above. This can be done by noting that the expression equals
B1 E sup m
Σ GOb (w f(xi))
m
Eas ca (w f(xs)))
sup
max
JEFT 1 w::lw]|sL..ew.
(+) B E
m
m
sup
sup an: [r:[wW|ST..EV
Σ
Eash (w f(x;))
sup
Σ 1=1
Gab ((xi))))
m
FEF-1
":]lw
(**)
2B
E
sup
sup
cib (wl f(xx)))
m
JEF w
where (+) follows from the fact that max (a, b) < a + for non-negative a, and the observation that the supremum is always non-negative (it is only larger, say, than the specific choice of & being the zero function), and (w*) is by symmetry of the function class Vr (if s Vz. then 1 V z. as well).
Note that for every / Fi-1 and w with |/|| S 1 have |w f(x)) S |w -1/( S R where R₁ bb W .... [W]]]- This class is subset of the class of composition of all functions from _d to [RR-1, R1-1), and all univariate L-Lipschitz functions crossing the
25

---

origin. Fortunately, the Rademacher complexity of such composed classes was analyzed in Golowich al. [2018] for different purpose. Applying Theorem from that paper, we get the upper bound of
R1-1 + log Rm)mml Rm FI-1))
LcBBL
m
where >> O is universal constant, and
Rm FI-1) == E
sup |
Gw f(x)) S E sup JEA-1
Σ (fxi)) i=1
==1
From this, the result follows.
Proof of Theorem 7. Remember the new definition of Fk (see Eq. 10), note that we just removed Wk. and therefore we turn to analyze the Rademacher complexity of
{wg f ||wx|| & B f E Fk-1)
on m inputs from fx E Rd ||x| S b. Fix some set of imputs X1.... Xm with norm at most by. The Rademacher complexity equals
E sup sup SEFx-1 we m
1 Σ G. f(x,)
Bx E sup
Σ
cf((x)
(12)
JEFr-1
i=1
By applying Lemma 11 repeatedly (i.e. k times) we get
sup SEFL-1
cf((x)
m i=1
R
1 m
< 10BB--1 T
+ log llgg)(m) sup
Σ (x((x))
Vm
fEF
m
2cL 2cIBB-11A
(2cI.) BB- 1 BB 2- 2 log
1 (m) +...
Vm
vm
(2cL)=-1
[Tisk-1 Bj
log
k(k-2
(m)
(2cL)
II jSk-1
B₁
log
3(4-1)
(m)lE
1
Σ
E;Xi
Vm
m
(13)
where Rs by L k- 21 W 22 inequality
||Wk-
||Wil| and Ro = by Note that by Cauchy- -chhhy
1
1
1
by
E
6XXi
E
EX;;
E
G X
X
<
V
mb
171
5,²=1
i=
Plugging this back into Eq. 13, get the following upper bound:
2cLB RE-2
(2cL) By
B 2 RR
log (m)
Vm
m
(2cL)* k-
1issk-1 Bj log
(m)
(2cL)*
II B, log
(m)b.
Vm
Vm
(2cL)f. (1i5k- Bj)
RE-1-i log
3(6-13
(m)
(2eI.)*11
B, log
x(--1)
(m)
b
Vm
mm
jSk-1
Altogether we have k terms, each one of them upper bound by
(2eL) k- (-IL)~-RRx- Rx
[ B,
log 3(k-1)
(m)
Vm
26

---

where we use the assumption that L and ||a]| 2 1, which implies also that 1 2 1. Therefore, we can upper bound the displayed Eq. by
log 2(k-1) (m)
1(2el.)* h Rk-2
-iss-1 Bi)
Vm
Combining with Eq. 12, the Rademacher complexity of Fr is upper bounded by
((2cL)=1bB4, bR [Ilis--1 B,
log
(m)
Vm
from which the result follows.
27


Reviews:
[{"review_id": "UK7IO1NQqg", "reviewer": "Reviewer_9YyA", "summary": "The authors provide various sample complexity results for linear and nonlinear networks in initialization dependent and independent cases. Here is the summary of results.\n* For the class of predictors $f(Wx)$, the fat-shattering dimension is characterized and gives a lower bound on sample complexity where the dependence of the bound on the distance from initialization $B$ is exponential (Theorem 1). The output dimension, however, is assumed to be exponential in $B$: $n=\\exp(\\Theta(L^2B^2/\\epsilon^2))$.\n* The upper bound is driven by Rademacher complexity analysis in Theorem 2, and is shown to be tight.\n* The proof of Theorem 2 relies on covering number arguments, Dudley’s inequality and utilizing covering bounds from Lemma 1 and 5.\n* Corollary 2 extends the result of Theorem 2 to neural networks by replacing the function $f$ by all the layers and activations after the first layer. The Lipschitz constant of the new function is equal to the product of spectral norms.\n* Theorem 3 shows that the fat shattering lower bound holds as well for non-zero initialization, although $\\Vert W_0\\Vert$ should be as small as $2\\sqrt{2}\\epsilon$.\n* Theorem 4 adapts the classical result for convex learning in context of learning vector-valued linear predictors. Theorem 5 adapts Theorem 3 for convex functions. The overall message is that linear predictors combined with convex functions are learnable.\n* The authors provide generalization bounds to single hidden layer networks with elementwise Lipschitz activation function and with initialization dependence in Theorem 6. This is the extension and improvement of Vardi et al 2022, and Daniely and Garnot 2022.\n* Theorem 7 provides a generalization bound on deep neural networks with Lipschitz activation under Forbenius norm constraints. The proof is based on Rademacher complexity analysis, and adapts Golowich et al’s peeling lemma to Lipschitz activation.\n\nTo summarize, the paper contains various theoretical results, some related to vector valued outputs, some related to initialization dependence, some related to convex functions, and some related to Lipschitz assumption. I have some concerns about the theoretical results of the paper, their assumptions and comparison with existing works. \nBelow, I raise some concerns about the assumptions of Theorem 1,3 and 5. The result of Theorem 2 seems peculiar. Theorem 7 is not properly situated with respect to similar norm-based bounds in the literature. Theorem 4 and 6 seems to build heavily on previous results. \n", "questions": "* In line 550 of supplementary materials, it is assumed that $\\frac{B}{\\epsilon}>1$. I guess this is because we have the condition on the rank $r\\leq B^2/\\epsilon^2$. How would the proof work if the condition does not hold, and then $r=0$? The point of working with the norms is that we hope $B$ is small after training.\n* Line 206, “in sharp contrast to the case of vector-valued predictors” $\\to$ maybe “in sharp contrast to the case of *scalar*-valued predictors”?\n* Line 685  in the supplementary materials: the equality should be an inequality. \n", "limitations": "See above.", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "\nCertain story lines of the paper are very interesting, for example the impact of vector valued outputs on the generalization. Also, adapting Peeling lemma in Theorem 7 is very elegant – although it comes with an additional cost. \n", "weaknesses": "* I wonder about the message of  Theorem 1. The authors assumed already that the output dimension is exponentially large $n=\\exp(\\Theta(L^2B^2/\\epsilon^2))$, and then show that the network can shatter $\\exp(cL^2B^2/\\epsilon^2)$ points. This just tells that the fat-shattering dimension would be linearly (or polynomially maybe) dependent on the output dimension and not exponentially on $B$, as it is claimed in the paper. \n* It is surprising that Theorem 2 do not leave any room for reducing to scalar valued case ($n=1$), where the dependence on $B$ is not exponential anymore. Is there an explanation for this? In this sense, the results are not optimal for $n=1$. More generally, it is surprising that the dimension of the output vector $n$ does not impact the sample complexity.\n* The exponential dependence arises mainly from the covering number argument in Lemma 1, where the function space is covered by binning $N_x$ and $N_y$. The exponent is basically $N_x$. It would be important to emphasize this in the main paper, explain why $B$ appears in the exponent, and whether this can be circumvented. \n* I wonder if directly bound the Rademacher complexity for $f(Wx)$ is a good choice. One might be tempted to use variants of vector-valued contraction lemma  (for example Maurer’s result) to remove $f$, although with price of dimension dependence. It seems to me that this approach will not suffer from the exponential dependence. \n* On a similar note, the authors should discuss the existing approaches for bounding the Rademacher complexity of vector valued functions and situate their work with respect to those.\n* Corollary 2 utilizes the Lipschitz constant of the deep network to bound the generalization error. However, this has been tried already in Bartlett et al 2017 and does not have exponential dependence. Besides, considering Lipschitz constant alone without margin has shortcomings already mentioned in  Bartlett et al 2017. The proposed bound suffers from similar shortcomings apart from the exponential dependence. \n* The assumptions of Theorem3 are not clearly discussed. It seems surprising that the input and output dimensions are chosen as a function of $m$ ($d=\\Theta(m)$ and $n=\\Theta(\\exp(m))$. The norm $B$ is fixed to $\\sqrt{2}$ unlike Theorem 1. Overall, it is difficult to parse the message behind Theorem 3. We can raise similar issues for Theorem 5. \n* The authors claim that Theorem 7 provides “the first of this type (to the best of our knowledge) that handles general Lipschitz activations under Frobenius norm constraints”. Bartlett et al 2017 provide a generalization error for Lipschitz activations using spectral and $(p,q)$ matrix norms. Their bound has only logarithmic dependence on the width, and does not have the product of Frobenius norms, which can be much larger than the product of spectral norms. The authors should compare their result with Bartlett et al.  There are other norm based bounds in the literature, and the authors can provide a better comparison with them. \n* A side note is that Theorem 1 and 2 and 7 are for $W_0=0$. If wonder the initialization dependence, which is in the title, is the core idea of the paper. The paper covers many different topics and can probably focus deeper on some of those. For example, I feel that the result about learning convex functions is expected and not very insightful. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading of the paper and the detailed comments, we will be happy to add clarifications and discussions as suggested.\n\nFirst, a general comment relevant to most of the points raised: We would like to emphasize that our focus is on *size-independent* bounds, which do not depend in any manner whatsoever on the dimension or number of parameters. This is in line with a huge previous literature in statistical learning theory, as well as on neural networks in particular. Such results are relevant for understanding the generalization capabilities of large models, and are also crucial for understanding how different norms lead to sample complexity control, independent of additional orthogonal constraints such as model size. Understanding how the bounds are affected by joint norm control and model size control is certainly an interesting avenue for future research, but we believe a necessary prerequisite is understanding the effect of each separately. We believe our results certainly pass the novelty test in that regard. For example, the fact that controlling the Frobenius norm alone leads to any kind of finite sample complexity (Theorem 2) should be surprising considering what we currently know (e.g. Maurer's vector-valued contraction result, which is vacuous without controlling the vector dimension). \n\n- Message of theorem 1: Actually, the sample complexity cannot simply depend on the output dimension. This is because theorem 2 tells us that there is also an upper bound independent of the output dimension, as long as the Frobenius dimension is controlled. In any case, as written above, our focus is on bounds which do not depend on the output dimension. \n- Theorem 2 does not reduce to the scalar-valued case: Indeed it should not, since our focus is on size-independent bounds which do not depend on $n$. This is exactly analogous to the classical $\\frac{B^2}{\\epsilon^2}$ sample complexity bound for linear predictors, which is minimax optimal when the input dimension is unconstrained, but becomes something else if we also constrain the dimension. \n- Existing works on Rademacher complexity of vector-valued functions: We agree these should be further discussed and would be happy to add such a discussion. As far as we know, all results on this topic strongly depend on the vector dimension, and are not applicable to the size-independent setting that we focus on (we certainly tried :) ).\n- Corollary 2 and Bartlett et al. (2017): The Bartlett et al. paper uses a different and much stronger assumption that ours: They control the $(1,2)$ matrix norm, whereas we control the Frobenius norm. Besides the latter norm being arguably more natural (as we discuss in the introduction), the gap between the $(1,2)$-norm and the Frobenius norm can be arbitrarily large, depending on the matrix size (and again, we focus on size-independent bounds). In addition, we already know that the product of the spectral norms is insufficient to bound the Rademacher complexity. The main point of our corollary 2 is that *just* by adding control on the Frobenius norm of the *first* layer, we can already get some finite sample complexity. This should be surprising, as all previous norm-based bounds (that we are aware of) required stronger norm controls on *all* the layers to get a finite bound. \n- Assumptions in Theorem 3 and theorem 5: Again, our focus is on size-independent bounds, so in order to establish a lower bound, it is reasonable to choose $n$ and $d$ to get the tightest lower bound possible (including as a function of the sample size $m$). A similar assumption is used in the classical result that the $\\frac{B^2}{\\epsilon^2}$ bound for linear predictors is tight (i.e. the input dimension should be larger than the sample size). The message of theorem 3 is that even if the Frobenius norm $B$ is controlled (and even a small numerical constant), we cannot obtain a finite sample complexity when $W_0\\neq 0$. Also, the $\\sqrt{2}$ factor in theorems 3+5 is just for convenience, and can easily be replaced by $1$ via rescaling. Anyway, we would be happy to further clarify the presentation of the results if needed. \n- \"The overall message [of theorems 4+5] is that linear predictors combined with convex functions are learnable.\" Actually, the fact that linear+convex functions are learnable is classical and appears in textbooks. The main message is that we present a class that is provably learnable, in a distribution-free learning setting, *without* uniform convergence. Namely, the convergence of the learning algorithm does not depend on the size of the model, but the sample complexity does depend.\n- Theorem 7 and comparison to Bartlett et al.: Thanks, we will add more comparisons to the literature. Again, we would like to emphasize that Barlett et al 2017 considers an incomparable setting where the $(1,2)$ matrix norm is controlled. \n- The result about learning convex functions is expected: Certainly, it is just given for completeness. The more interesting result is theorem 5 which shows that uniform convergence does not hold here. \n\n- Question 1: The main regime of interest is $\\frac{B}{\\epsilon}>1$, i.e. that $B$ is not too small and $\\epsilon$ is not too large. If $\\frac{B}{\\epsilon}<1$, then $B<\\epsilon$. This means that the predictor class (with a norm bound of $B$) cannot attain an output value varying by  more than $\\epsilon$, even on a single fixed data point. \n- Question 2: Thanks, we will fix accordingly.\n- Question 3: Thanks, we will fix accordingly.\n     \nRegarding your summary: \n- We emphasize that Thm. 3 shows that even for very small non-zero initialization, it is impossible to control the sample complexity independent of the size/dimension parameters $d,n$, by showing that the fat shattering is infinite. This is in contrast to Thm. 1 and 2 which showed a tight size-independent bound."}, {"review_id": "yG80EnTkn4", "reviewer": "Reviewer_8WAD", "summary": "The paper generally studies the sample complexity of the functions of the form $f(Wx)$ and it particularly focuses on size-independent bounds. First it shows matching exponential lower and upper bounds for the case that the reference matrix $W_0=0$. Then, it is showed that one cannot obtain an upper bound in the case that $W_0 \\neq 0$. Using these results, they further provide: (1) sample complexity bounds for NNs and (2) an instance where uniform convergence does not hold but learning is possible with SGD. ", "questions": "Main question: \n- Q1. In theorem 1, the valued of $d, n$ are asymptomatically determined by $L^2B^2 /  \\epsilon^2$ which is the exact quantity that gives the shattering. In other words shattering in this case is given by $d$ (or $n$) as well. So I am not sure if this lower bound is independent of the size? (Both the bound and the size depend on $L^2B^2 /  \\epsilon^2$).\n\nOther questions:\n- Q2. (Although this is not super important for the negative result) Do we have a picture about Theorem 3, 5 when $n$ is not exponentially large w.r.t. $d$?\n\nPossible typos:\n- line 232: $W_j$ instead of $w_j$\n- line 234: do not instead of don't\n- line 422: $x_1, \\ldots, x^m$\n- line 633: space between $R$ and (\n", "limitations": "The work is theoretical and does not have any negative societal impact. The limitations have been adequately discussed. ", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper generally studies the sample complexity of $f(Wx)$ quite extensively both in the case that the reference matrix $W_0$ is zero and non-zero. The implications are also interesting:\n    - Neural network results: e.g., depth/width-independent result if the reference matrix is 0\n    - Another example that uniform convergence fails and SGD succeeds. \n- Both the main text and the appendix are well-written. ", "weaknesses": "My main concern is regarding Q1 below. There are some limitation/future directions that have been discussed in the paper itself. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments, we will fix the typos.\n\n- Q1: To prove a lower bound in a size-independent setting, we are free to choose the size parameters $n,d$ as we wish (since the upper bounds should hold for any $n,d$). In particular, we may choose them to depend on $L,B,\\epsilon$. It would be interesting to understand the sample complexity when $n,d$ are also controlled, and we left this as an open question (see section 5).\n- Q2: That's an interesting question for future research. In that case we would attain some dependence on $n$ (but whether it is polynomial, logarithmic or something else remains to be seen). "}, {"review_id": "Y3ZnTRRMxQ", "reviewer": "Reviewer_Zmxy", "summary": "In this paper, the authors give sample complexity bounds for learning function classes of the form $g(x) = f(Wx)$, where $W$ is a matrix, and $f$ is a Lipshitz function. They sample complexity bounds are based on the Frobeneous norm of the matrix $W - W_0$, where $W_0$ is a fixed initialization matrix. The upper bounds are given in terms of the Rademacher complexity, which the lower bounds are given in terms of the fat-shattering dimension. For the case when $W_0 = 0$, the authors give tight, size independent bounds on the sample complexity, where here size refers to the first dimension, $n$, of $W$. They use this to show some novel sample complexity bounds for neural networks. The then show that when $W_0 \\neq 0$, it is impossible to achieve such size-independent bounds, and the resulting sample complexity that grows in $m$. Due to this impossibility result, they are able to show the existence of a certain type of ERM problem for which SGD learns but uniform convergence fails.  Finally they restrict their setting to the case of two-layer neural networks and show some specific results that recover or improve upon results in the literature.", "questions": "Major comments are in weaknesses.\nMinor comments: \n- In line 68, could the authors explain what they mean by the Lipchitz function is a parameter? If possible, this should be explained concisely, but otherwise a pointer to where it is explained later would be helpful.\n- It is standard to have $n$ be the number of samples and $m$ be a width parameter, so it would clearer if these were swapped", "limitations": "Sufficient", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "In general the paper is reasonably clear, and the results are solid. They authors close some open questions in related work, and provide novel results in more general settings. ", "weaknesses": "The results in this paper are somewhat incremental in the sense that they seem to primarily just be useful for the case of a one-layer network with multiple outputs (and practically, in such a setting, the \"size\" parameter $n$ would probably not be so large). Could the authors make the exact dependence on $n$ clear in the resulting sample complexity? (I think it is logarithmic?)\n\n*Lacking Motivation*:\n- The model class $f(Wx)$ studied in this work seems to be different from previous classes studied from a sample complexity perspective, and so the authors should further justify their setting, and why it differs from existing models. Are there settings that generalize this model? And which other settings does this model subsume besides the vector-valued case? The examples given in the paragraph at line 13 could be made even more concrete and obvious to the author.\n- The authors should provide some references in the intro for where such settings are studied in other works or where they are used in practice.\n\n*Comparison with related work could be improved*:\n- Intro: The authors should explain the result of Vardi et al 22 and Daniely and Granot in the introduction, and specifically explain how their work differs, because it is quite similar. It seems like the major difference is that f has a decomposable structure in the other works? The authors should also spell out the exact open questions they answer from Vardi et al.\n- The authors should include a detailed quantitative comparison to the most related works. A table (perhaps in the intro, though if it is too complicated, later on) would be helpful, describing the different settings and comparing results ($W_0 = 0$ or not, shallow or deep nets, element-wise activations, etc.). \n- For the result on deep neural networks on page 6 and in section 4.1, a more detailed quantitative comparison to existing works would be useful. In what regimes are the bounds given in this work better? In what regimes are other works in the literature stronger? \n- More discussion on the limitations of uniform convergence (UC) and works that go beyond UC would be useful. Eg. https://arxiv.org/abs/1902.04742 , https://arxiv.org/abs/2103.04554, https://arxiv.org/abs/2206.07892 and references therein. The authors should discuss other way of bounding the sample complexity of learning neural networks eg. PAC Bayes bounds etc. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments, we will improve the presentation according to your suggestions.\n- Show dependence on $n$: We would like to emphasize that our focus is on size-independent bounds, which do not depend in any manner whatsoever on $n$. This is in line with a huge previous literature in statistical learning theory, as well as on neural networks in particular. Such results are relevant for understanding the generalization capabilities of large models, and are also crucial for understanding how different norms lead to sample complexity control, independent of additional orthogonal constraints such as model size. Understanding how the bounds are affected by joint norm control and model size control is certainly an interesting avenue for future research, but we believe a necessary prerequisite is understanding the effect of each separately. \n- Motivation of model class: We will add further discussion. In a nutshell, it directly models vector-valued linear predictors composed with a Lipschitz loss (e.g., for multi-task and multi-class learning), as well as generalizes large neural networks. The former is of course studied in many papers. As to the latter, an example reference is Daniely and Granot [2022]. In any case, this model helps us to understand the effect of initialization on the sample complexity (which is a challenging task compared to the case of initialization at zero), the sample complexity of neural networks, and the conditions under which we can achieve size-independent bounds. \n- Comparison to previous work: We will add more discussions as suggested, and also include a summary below. The open questions in Vardi et al that we answer are (1)  Understanding the sample complexity with non-zero initialization (e.g., Thm. 6, see lines 336-337, 352-354), and (2) Extending their results to deeper networks (e.g., Thm. 7, see lines 368-370,378-389). As to Daniely and Granot, their bounds are not size-independent, so it is a different setting than ours. \n- Line 68: We meant that the predictor class ranges over all possible $L$-Lipschitz functions, composed with a class of linear functions (as opposed to having a single fixed Lipschitz function). See exact definition in the statement of Theorem 2.\n\n\n\n\nFurther discussion of related works: \n\n- Deep neural networks and Frobenius norm: We refer to lines 333-342.\nIn more detail: A width-independent uniform convergence\nguarantee, depending on the product of Frobenius norm of all layers, has been established in Neyshabur et al. [2015] for\nconstant-depth networks, and in Golowich et al. [2018] for arbitrary-depth networks. However, these bounds are specific to element-wise, homogeneous activation functions, whereas we tackle general Lipschitz activations. Bounds based on other norms include Anthony\nand Bartlett [1999], Bartlett et al. [2017], Liang [2016], but are potentially more restrictive than the\nFrobenius norm, or do not lead to width-independence. As we mention on page 6 (lines 226-230), all previous bounds of this type we are aware of strongly depend on various norms of all layers, which can be arbitrarily larger than the spectral norm in a size-independent setting (such as the Frobenius norm and the $(1,2)-$norm), or made strong assumptions on the activation function.\n\n- Non-zero initialization: Bartlett et al. [2017] upper bound the sample complexity of neural networks with non-zero initialization, but they used a much stronger assumption than ours: They control the $(1,2)$-matrix norm, whereas the gap between this norms can be arbitrarily large, depending on the matrix size. Vardi et al [2022] also studied the initialization case with element-wise activations, but their result is size-dependent and includes a different technique than ours.\n\n- Non-element-wise activations: Daniely and Granot [2022] do provide a fat-shattering lower bound with a general Lipchitz activation (non-element-wise, similar setting as our first part of the paper), which implies that neural networks on $R^d$ with bounded Frobenius norm and width $n$ can shatter $n$ points with constant margin, assuming that the inputs have norm at most $\\sqrt{d}$ and that $n = O(2^d)$.\nHowever, this lower bound is size-dependent, and moreover does not separate between the input norm bound and the width of the hidden layer. Therefore, their result does not contradict our upper bound (i.e. Thm. 2) which says that it's possible to achieve a size-independent upper bound on the sample complexity.\n"}, {"review_id": "Z9dIAwKqC3", "reviewer": "Reviewer_xxjV", "summary": "This paper views a prototype but interesting enough neural network architecture from Rademacher complexity, and uses Rademacher complexity to analyze the sample complexity used for correctly training the neural network. It reveals an approves an interesting result that the Rademacher complexity hence the sample complexity depends on the initialization. The major theorems show the difference of sample complexity bound at zero and non-zero initialization.\n\n=============\n\nRating updated to 7 and Confidence to 3 for the rebuttal. I would be glad to see it published, but the tightness given by shattering, as pointed out by the authors, relies on the \"distribution-free learning setting\", which might not be practical when considering the real world data (whose distribution might make some neural net architectures more learnable), and does not talk about the optimization algorithm that trains the model. The manuscript is still self-consistent so I give 7, but not higher due to the unanswered larger scope. \n\nIf the real world experiment shows the gap and difference between two initializations, I would not hesitate to give 7 or 7+, but now I'm still hesitant between 6 and 7.", "questions": "I did not understand the difference between the results in Section 3.1 and 3.2, they look quite similar. I would like to see more discussion, corollaries or remarks following the theorems, since they are not described as \"sample complexity\", but \"shatter\", etc.\n\nI would be willing to increase the score if the weaknesses can be addressed.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "I think the mathematics is concrete and solid, the contribution is novel, and it shows an interesting and non-intuitive fact that sample complexity depends on the initialization. All the mathematical definition are rigorously and clearly defined, and there is thorough discussion of the impact of the results. The special bound for deep neural networks is also given as a corollary.", "weaknesses": "I would like to see more practical experiments that verify the consistency between sample complexity and the Rademacher complexity. Rademacher complexity, especially for deep neural networks or functions with high nonlinearity, is usually not tight for sample complexity bound. Rademacher complexity is an upper bound, i.e., if you have more samples and can find the globally optimal model in the model family, then it’s guaranteed that the model is the ground truth. But it does not say 1) what if number of samples is lower than sample complexity bound, how does the generalization error grow, which depends on the data distribution; 2) if there are enough samples, is the neural net trained with typical methods like SGD the global optimal solution. Those need to be verified by experiments, no need to be exactly consistent, but it cannot be a too large gap.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your comments. We will see whether we can incorporate experiments (say along the lines of Bartlett et al [2017]). However, it should be emphasized that our paper is theoretical and focuses on understanding the minimax optimal sample complexity of various predictor classes, similar to many previous papers in the statistical learning theory literature. \n- Difference between sections 3.1, 3.2: The main difference is that 3.1 focuses on the case of zero initialization ($W_0=0$) and 3.2 focuses on the case of non-zero initialization ($W_0\\neq 0$). These settings are qualitatively different, as we show that the sample complexity can be finite in the former case, but infinite in the latter case. "}]

Author rebuttal:

Meta-review: This nice paper slightly continues a long line of progress on generalization bounds for deep networks. I urge the authors to use the extra camera ready page for reviewer suggestions. Minor comment: "$k$-1" before Theorem 7 should be "$(k−1)$" or "$k-1$".
Decision: Accept (poster)