Initialization-Dependent Sample Complexity of Linear Predictors and
  Neural Networks
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.
Roey Magen, Ohad Shamir
# Initialization-Dependent Sample Complexity

###### 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.

## 1 Introduction

In this paper, we consider the sample complexity of learning function classes, where each function is a composition of one or more transformations given by

\[\mathbf{x}\ \rightarrow\ f(W\mathbf{x})\,\]

where \(\mathbf{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 to a 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 \(f\) corresponds to some loss function. A special case of the above are scalar-valued linear predictors (composed with some scalar loss or nonlinearity \(f\)), namely \(\mathbf{x}\to f(\mathbf{w}^{\top}\mathbf{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 to 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-valued linear predictors of the form

\[\{\mathbf{x}\rightarrow\mathbf{w}^{\top}\mathbf{x}:\mathbf{w},\mathbf{x}\in \mathbb{R}^{d},\|\mathbf{w}\|\leq B\}\]
and inputs \(||\mathbf{x}||\leq 1\), where \(||\cdot||\) is the Euclidean norm. For this class, it is well-known that the sample complexity required to achieve excess error \(\epsilon\) (w.r.t. Lipschitz losses) scales as \(O(B^{2}/\epsilon^{2})\), independent of the number of parameters \(d\) (e.g., Bartlett and Mendelson (2002), Shalev-Shwartz and Ben-David (2014)). Moreover, the same bound holds when we replace \(\mathbf{w}^{\top}\mathbf{x}\) by \(f(\mathbf{w}^{\top}\mathbf{x})\) for some \(1\)-Lipschitz function \(f\). Therefore, it is natural to ask whether similar size-independent bounds can be obtained when \(W\) is a matrix, as described above. This question is the focus of our paper.

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 \(W_{0}\), 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, 2022)), we will be mainly interested in the case where we bound the _spectral norm_\(||\cdot||\) of \(W_{0}\), and the distance of \(W\) from \(W_{0}\) in the _Frobenius norm_\(||\cdot||_{F}\), resulting in function classes of the form

\[\left\{\mathbf{x}\to f(W\mathbf{x}):W\in\mathbb{R}^{n\times d},||W-W_{0}||_{F} \leq B\right\}. \tag{1}\]

for some Lipschitz, possibly non-linear function \(f\) and a fixed \(W_{0}\) 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 \(W_{0}\), we note that in the case of scalar-valued linear predictors (where \(W,W_{0}\) are vectors), the sample complexity is not affected 1 by \(W_{0}\). This is intuitive, since the function class corresponds to a ball of radius \(B\) in parameter space, and \(W_{0}\) affects the location of the ball but not its size. A similar weak dependence on \(W_{0}\) is also known to occur in other settings that were studied (e.g., Bartlett et al. (2017)).

Footnote 1: More precisely, it is an easy exercise to show that the Rademacher complexity of the function class \(\{\mathbf{x}\to f(\mathbf{w}^{\top}\mathbf{x}):\mathbf{w}\in\mathbb{R}^{d},|| \mathbf{w}-\mathbf{w}_{0}||\leq B\}\), for some fixed Lipschitz function \(f\), can be upper bounded independent of \(\mathbf{w}_{0}\).

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. (1), without further assumptions on \(f\) besides being Lipschitz, and assuming \(\mathbf{x}\) has a bounded Euclidean norm. As mentioned above, this is a very natural class, corresponding (for example) to vector-valued linear predictors with generic Lipschitz losses, or neural networks composed of a single layer and some general Lipschitz activation. In this setting, we make the following contributions:

* In subsection 3.1 we study the case of \(W_{0}=0\), and prove that the size-independent sample complexity (up to some accuracy \(\epsilon\)) is both upper and lower bounded by \(2^{\tilde{\Theta}(B^{2}/\epsilon^{2})}\). This is unusual and perhaps surprising, as it implies that this function class does enjoy a finite, size-independent sample complexity bound, but the dependence on the problem parameters \(B,\epsilon\) are exponential. This is in very sharp contrast to the scalar-valued case, where the sample complexity is just \(O(B^{2}/\epsilon^{2})\) as described earlier. Moreover, and again perhaps unexpectedly, this sample complexity remains the same even if we consider the much larger function class where the Lipschitz function \(f\) itself is a parameter.
* Building on the result above, we prove a size-independent sample complexity upper bound for deep feed-forward 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.
* In subsection 3.2, we turn to consider the case of \(W_{0}\neq 0\), and ask if it is possible to achieve similar size-independent sample complexity guarantees. Perhaps unexpectedly, we show that the answer is no, even for \(W_{0}\) with very small spectral norm. Again, this is in sharp qualitative contrast to the scalar-valued case and other settings in the literature involving a \(W_{0}\) term, where the choice of \(W_{0}\) 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 learnability (e.g., Shalev-Shwartz et al. (2010), Daniely et al. (2011), Feldman (2016)).

In the second part of our paper (Section 4), we turn to a different and more specific choice of the function \(f\), considering one-hidden-layer neural networks with activation applied element-wise:

\[\mathbf{x}\ \longrightarrow\ \mathbf{u}^{\top}\sigma(W\mathbf{x})=\sum_{j}u_{j} \sigma(\mathbf{w}_{j}^{\top}\mathbf{x}),\]

with weight matrix \(W\in R^{n\times d}\), weight vector \(\mathbf{u}\in\mathbb{R}^{n}\), and a fixed (generally non-linear) Lipschitz activation function \(\sigma(\cdot)\). As before, We focus on an Euclidean setting, where \(\mathbf{x}\) and \(\mathbf{u}\) has a bounded Euclidean norm and \(||W-W_{0}||_{F}\) is bounded, for some initialization \(W_{0}\) with bounded spectral norm. In this part, our sample complexity bounds have polynomial dependencies on the norm bounds and on the target accuracy \(\epsilon\). Our contributions here are as follows:

* We prove a fully size-independent Rademacher complexity bound for this function class, under the assumption that the activation \(\sigma(\cdot)\) is smooth. In contrast, earlier results that we are aware of were either not size-independent, or assumed \(W_{0}=0\). Although we do not know whether the smoothness assumption is necessary, we consider this an interesting example of how smoothness can be utilized in the context of sample complexity bounds.
* With \(W_{0}=0\), 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-wise 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 al. (2022). We conclude with a discussion of open problems in Section 5. Formal proofs of our results appear in the appendix.

## 2 Preliminaries

**Notations.** We use bold-face letters to denote vectors, and let \([m]\) be shorthand for \(\{1,2,\ldots,m\}\). Given a vector \(\mathbf{x}\), \(x_{j}\) denotes its \(j\)-th coordinate. Given a matrix \(W\), \(\mathbf{w}_{j}\) is its \(j\)-th row, and \(W_{j,i}\) is its entry in row \(j\) and column \(i\). Let \(0_{n\times d}\) denote the zero matrix in \(\mathbb{R}^{n\times d}\), and let \(I_{d\times d}\) be the \(d\times d\) identity matrix. Given
a function \(\sigma(\cdot)\) on \(\mathbb{R}\), we somewhat abuse notation and let \(\sigma(\mathbf{x})\) (for a vector \(\mathbf{x}\)) or \(\sigma(M)\) (for a matrix M) denote applying \(\sigma(\cdot)\) element-wise. We use standard big-Oh notation, with \(\Theta(\cdot),\Omega(\cdot),O(\cdot)\) hiding constants and \(\tilde{\Theta}(\cdot),\tilde{\Omega}(\cdot),\tilde{O}(\cdot)\) hiding constants and factors that are polylogarithmic in the problem parameters.

\(\left\|\cdot\right\|\) denotes the operator norm: For vectors, it is the Euclidean norm, and for matrices, the spectral norm (i.e., \(\left\|M\right\|=\sup_{x:\left\|\mathbf{x}\right\|=1}\left\|M\mathbf{x}\right\|\)). \(\left\|\cdot\right\|_{F}\) denotes the Frobenius norm (i.e., \(\left\|M\right\|_{F}=\sqrt{\sum_{i,j}M_{i,j}^{2}}\)). It is well-known that the spectral norm of a matrix is equal to its largest singular value, and that the Frobenius norm is equal to \(\sqrt{\sum_{i}\sigma_{i}^{2}}\), where \(\sigma_{1},\sigma_{2},\dots\) 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:\mathbb{R}^{d}\rightarrow\mathbb{R}\) is \(\mu\)-smooth if \(f\) is continuously differentiable and its gradient \(\nabla f\) is \(\mu\)-Lipschitz.

**Sample Complexity Measures.** In our results and proofs, we consider several standard complexity measures of a 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 \(\epsilon\)) lower bounds the number of samples needed to learn in a distribution-free learning setting, up to accuracy \(\epsilon\) (see for example Anthony and Bartlett (2002)). It is formally defined as follows: **Definition 1** (Fat-Shattering).: _A class of functions \(\mathcal{F}\) on an input domain \(\mathcal{X}\)_ shatters \(m\)_points_\(\mathbf{x}_{1},...,\mathbf{x}_{m}\in\mathcal{X}\)_with margin \(\epsilon\), if there exists a number \(s\), such that for all \(y\in\{0,1\}^{m}\) we can find some \(f\in\mathcal{F}\) such that \[\forall i\in[m],\;\;f(\mathbf{x}_{i})\leq s-\epsilon\;\;\text{if}\;\;y_{i}=0 \;\;\text{and}\;\;f(\mathbf{x}_{i})\geq s+\epsilon\;\;\text{if}\;\;y_{i}=1\] _The fat-shattering dimension of \(F\) (at scale \(\epsilon\)) is the cardinality \(m\) of the largest set of points in \(\mathcal{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-shattering dimension, which translate to lower bounds on the sample complexity.
* Rademacher Complexity: This measure can be used to obtain upper bounds on the sample complexity: Indeed, the number of inputs \(m\) required to make the Rademacher complexity of a function class \(\mathcal{F}\) smaller than some \(\epsilon\) is generally an upper bound on the number of samples required to learn \(\mathcal{F}\) up to accuracy \(\epsilon\) (see Shalev-Shwartz and Ben-David (2014)). **Definition 2** (Rademacher complexity).: _Given a class of functions \(\mathcal{F}\)on a domain \(\mathcal{X}\), its Rademacher complexity is defined as \(R_{m}(\mathcal{F})=\sup_{\{\mathbf{x}_{i}\}_{i=1}^{m}\subseteq\mathcal{X}} \mathbb{E}_{\epsilon}\left[\sup_{f\in\mathcal{F}}\frac{1}{m}\sum_{i=1}^{m} \epsilon_{i}f_{i}(\mathbf{x}_{i})\right]\;,\) where \(\epsilon=(\epsilon_{1},...,\epsilon_{m})\) is uniformly distributed on \(\{-1,+1\}^{m}\)._
* Covering Numbers: This is 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 \(\mathcal{F}\) from \(\mathcal{X}\) to \(\mathcal{Y}\), a metric \(d\) over functions from \(\mathcal{X}\) to \(\mathcal{Y}\), and \(\epsilon>0\), we let the covering number \(N(\mathcal{F},d,\epsilon)\) denote the minimal number \(n\) of functions \(f_{1},f_{2},...,f_{n}\) from \(\mathcal{X}\) to \(\mathcal{Y}\), such that for all \(f\in\mathcal{F}\), there exists some \(f_{i}\) with \(d(f_{i},f)\leq\epsilon\). In this case we also say that \(\{f_{1},f_{2},...,f_{n}\}\) is an \(\epsilon\)-cover for \(\mathcal{F}\)._
In particular, we will consider covering numbers with respect to the empirical \(L_{2}\) metric defined as \(d_{m}(f,f^{\prime})=\sqrt{\frac{1}{m}\sum_{i=1}^{m}||f(\mathbf{x}_{i})-f^{\prime} (\mathbf{x}_{i})||^{2}}\) for some fixed set of inputs \(\mathbf{x}_{1},\ldots,\mathbf{x}_{m}\). In addition, if \(\{f_{1},f_{2},...,f_{n}\}\subseteq\mathcal{F}\), 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 \(\epsilon\)-covering number is sandwiched between the improper \(\epsilon\)-covering number and the improper \(\frac{\epsilon}{2}-\)covering number (see the appendix for a formal proof):

**Observation 1**.: _Let \(\mathcal{F}\) be a class of functions. Then the proper \(\epsilon\)-covering number for \(\mathcal{F}\) is at least \(N(\mathcal{F},d,\epsilon)\) and at most \(N(\mathcal{F},d,\frac{\epsilon}{2})\)._

## 3 Linear Predictors and Neural Networks with General Activations

We begin by considering the following simple matrix-parameterized class of functions on \(\mathcal{X}=\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\):

\[\mathcal{F}_{B,n,d}^{f,W_{0}}:=\left\{\mathbf{x}\to f(W\mathbf{x}):W \in\mathbb{R}^{n\times d},||W-W_{0}||_{F}\leq B\right\}\;,\]

where \(f\) is assumed to be some fixed \(L\)-Lipschitz function, and \(W_{0}\) is a fixed matrix in \(\mathbb{R}^{n\times d}\) with a bounded spectral norm. As discussed in the introduction, this can be interpreted as a class of vector-valued linear predictors composed with some Lipschitz loss function, or alternatively as a generic model of one-hidden-layer neural networks with a generic Lipschitz activation function. Moreover, \(W_{0}\) denotes an initialization/reference point which may or may not be \(0\).

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-independent 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 on \(d,n\) necessary for the bounds to hold.

**Remark 1**.: _Enforcing \(f\) to be Lipschitz and the domain \(\mathcal{X}\) to be bounded is known to be necessary for meaningful size-independent bounds, even in the case of scalar-valued linear predictors \(\mathbf{x}\mapsto f(\mathbf{w}^{\top}\mathbf{x})\) (e.g., Shalev-Shwartz and Ben-David (2014)). For simplicity, we mostly focus on the case of \(\mathcal{X}\) being the Euclidean unit ball, but this is without much loss of generality: For example, if we consider the domain \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq b_{x}\}\) in Euclidean space for some \(b_{x}\geq 0\), we can embed \(b_{x}\) into the weight constraints, and analyze instead the class \(\mathcal{F}_{b_{x}B,n,d}^{f,b_{x}W_{0}}\) over the Euclidean unit ball \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\)._

### Size-Independent Sample Complexity Bounds with \(W_{0}=0\)

First, we study the case of initialization at zero (i.e. \(W_{0}=0_{n\times d}\)). Our first lower bound shows that the size-independent fat-shattering dimension of \(\mathcal{F}_{B,n,d}^{f,W_{0}}\) (at scale \(\epsilon\)) is at least exponential in \(B^{2}/\epsilon^{2}\):

**Theorem 1**.: _For any \(B,L\geq 1\) and \(0<\epsilon\leq 1\) s.t. \(\frac{L^{2}B^{2}}{128\epsilon^{2}}\geq 20\), there exists large enough \(d=\Theta(L^{2}B^{2}/\epsilon^{2}),n=\exp(\Theta(L^{2}B^{2}/\epsilon^{2}))\) and an \(L\)-Lipschitz function \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}\) for which \(\mathcal{F}_{B,n,d}^{f,W_{0}=0}\) can shatter_

\[\exp(cL^{2}B^{2}/\epsilon^{2})\]

_points from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\) with margin \(\epsilon\), where \(c>0\) is a 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,\epsilon\) (whereas they considered the dependence on \(n,d\)). The main idea is to use the probabilistic method to show the existence of \(\mathbf{x}_{1},...,\mathbf{x}_{m}\in\mathbb{R}^{d}\) and \(W_{1},...,W_{2^{m}}\in\mathbb{R}^{n\times d}\) for \(m=\Theta(B^{2}/\epsilon^{2})\), with the property that every two different vectors from \(\{W_{y}\mathbf{x}_{i}:i\in m,y\in[2^{m}]\}\) are far enough from each other. We then construct an \(L\)-Lipschitz function \(f\) which assigns arbitrary outputs to all these points, resulting in a shattering as we range over \(W_{1},\ldots W_{2^{m}}\).

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 a similar quantity. In fact, and perhaps surprisingly, a much stronger statement holds: A similar quantity upper bounds the complexity of the much larger class of _all_\(L\)-Lipschitz function \(f\) on \(\mathbb{R}^{n}\), composed with all norm-bounded linear functions from \(\mathbb{R}^{d}\) to \(\mathbb{R}^{n}\):

**Theorem 2**.: _For any \(L,B\geq 1\) and \(0<\epsilon\leq 1\) s.t. \(\frac{LB}{\epsilon}\geq 1\), let \(\Psi_{L,a,n}\) be the class of all \(L\)-Lipschitz functions from \(\{\mathbf{x}\in\mathbb{R}^{n}:||\mathbf{x}||\leq B\}\) to \(\mathbb{R}\), which equal some fixed \(a\in\mathbb{R}\) at \(\mathbf{0}\). Let \(\mathcal{W}_{B,n}\) be the class of linear functions from \(\mathbb{R}^{d}\) to \(\mathbb{R}^{n}\) over the domain \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\) with Frobenius norm at most \(B\), namely_

\[\mathcal{W}_{B,n}:=\{\mathbf{x}\to W\mathbf{x}:W\in\mathbb{R}^{n\times d},||W|| _{F}\leq B\}.\]

_Then the Rademacher complexity of \(\Psi_{a,L,n}\circ\mathcal{W}_{B,n}:=\{\psi\circ g:\psi\in\Psi_{L,a,n},g\in \mathcal{W}_{B,n}\}\) on \(m\) inputs from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\) is at most \(\epsilon\), if \(m\geq\left(\frac{LB}{\epsilon}\right)^{\frac{cL^{2}B^{2}}{\epsilon^{2}}}\) for some universal constant \(c>0\)._

Since \(\mathcal{F}_{B,n,d}^{f,W_{0}=0}\subseteq\Psi_{L,a,n}\circ\mathcal{W}_{B,n}\) 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:\mathbb{R}^{n}\rightarrow\mathbb{R}\) be a fixed \(L\)-Lipschitz function. Then the Rademacher complexity of \(\mathcal{F}_{B,n,d}^{f,W_{0}=0}\) on \(m\) inputs from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\) is at most \(\epsilon\), if \(m\geq\left(\frac{LB}{\epsilon}\right)^{\frac{cL^{2}B^{2}}{\epsilon^{2}}}\) for some universal constant \(c>0\)._

Comparing the corollary and Theorem 1, we see that the sample complexity of Lipschitz functions composed with matrix linear ones is \(\exp\left(\tilde{\Theta}(L^{2}B^{2}/\epsilon^{2})\right)\) (regardless of whether the Lipschitz function 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 \(\epsilon\). On the other hand, it implies that for any fixed \(L,B,\epsilon\), it is finite completely independent of the number of parameters. The exponential dependence on the problem parameters is rather unusual, and in sharp contrast to the case of vector-valued predictors (that is, functions of the form \(\mathbf{x}\mapsto f(\mathbf{w}^{\top}\mathbf{x})\) where \(||\mathbf{w}-\mathbf{w}_{0}||\leq B\) and \(f\) is \(L\)-Lipschitz ), for which the sample complexity is just \(O(L^{2}B^{2}/\epsilon^{2})\).

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 \(\mathbf{x}\mapsto f(W\mathbf{x})\) in our class can be approximated (up to some \(\epsilon\)) by a function of the form \(\mathbf{x}\mapsto f(\tilde{W}_{\epsilon}\mathbf{x})\), where the rank of \(\tilde{W}_{\epsilon}\) is at most \(B^{2}/\epsilon^{2}\). In other words, this approximating function can be written as \(f(UV\mathbf{x})\), where \(V\) maps to \(\mathbb{R}^{B^{2}/\epsilon^{2}}\). Equivalently, this can be written as \(g(V\mathbf{x})\), where \(g(z)=f(Uz)\) over \(\mathbb{R}^{B^{2}/\epsilon^{2}}\). This reduces the problem to bounding the complexity of the function class which is the composition of all linear functions to \(\mathbb{R}^{B^{2}/\epsilon^{2}}\), and all Lipschitz functions over \(\mathbb{R}^{B^{2}/\epsilon^{2}}\), which we perform through covering numbers and the following technical result:

**Lemma 1**.: _Let \(\mathcal{F}\) be a class of functions from Euclidean space to \(\{\mathbf{x}\in\mathbb{R}^{r}:||\mathbf{x}||\leq B\}\). Let \(\Psi_{L,a}\) be the class of all \(L\)-Lipschitz functions from \(\{\mathbf{x}\in\mathbb{R}^{r}:||\mathbf{x}||\leq B\}\) to \(\mathbb{R}\), which equal some fixed \(a\in\mathbb{R}\) at \(\mathbf{0}\). Letting \(\Psi_{L,a}\circ\mathcal{F}:=\{\psi\circ f:\psi\in\Psi_{L,a},f\in\mathcal{F}\}\), its covering number satisfies_

\[\log N(\Psi_{L,a}\circ\mathcal{F},d_{m},\epsilon)\leq\left(1+\frac{8BL}{\epsilon }\right)^{r}\cdot\log\frac{8B}{\epsilon}+\log N(\mathcal{F},d_{m},\frac{ \epsilon}{4L}).\]
The proof for this Lemma is an extension of Theorem 4 from Golowich et al. 2018, which considered the case \(r=1\).

**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 a size/dimension-independent 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 a size-independent setting (such as the Frobenius norm), or made strong assumptions on the activation function (e.g., Neyshabur et al. (2015, 2017), Bartlett et al. (2017), Golowich et al. (2018), Du and Lee (2018), Daniely and Granot (2019), Vardi et al. (2022)).

Formally, we consider scalar-valued depth-\(k\) "neural networks" of the form

\[\mathcal{F}_{k}:=\{x\rightarrow\mathbf{w}_{k}f_{k-1}(W_{k-1}f_{k-2}(...f_{1}( W_{1}\mathbf{x})))\;\;:\;\;||\mathbf{w}_{k}||\leq S_{k}\;,\;\forall j\;||W_{j}|| \leq S_{j}\;,\;||W_{1}||_{F}\leq B\}\]

where each \(\mathbf{w}_{j}\) is a parameter matrix of some arbitrary dimensions, and each \(f_{j}\) is some fixed \(1\)-Lipschitz2 function satisfying \(f_{j}(\mathbf{0})=0\). This is a rather relaxed definition for neural networks, as we don't assume anything about the activation functions \(f_{j}\), except that it is Lipschitz. To analyze this function class, we consider \(\mathcal{F}_{k}\) as a subset of the class

Footnote 2: This is without loss of generality, since if \(f_{j}\) is \(L_{j}\)-Lipschitz, we can rescale it by \(1/L_{j}\) and multiply \(S_{j+1}\) by \(L_{j}\).

\[\left\{x\to f(W\mathbf{x}):\left\|W\right\|_{F}\leq B\;,\;f:\mathbb{R}^{n} \rightarrow\mathbb{R}\text{ is }L\text{-Lipschitz}\right\},\]

where \(L=\prod_{j=2}^{k}S_{j}\) (as this upper bounds the Lipschitz constant of \(z\mapsto W_{k}f_{k-1}(W_{k-1}f_{k-2}(\ldots f_{1}(z)\ldots))\). By applying Theorem 2 (with the same conditions) we have

**Corollary 2**.: _For any \(B,L\geq 1\) and \(0<\epsilon\leq 1\) s.t. \(\frac{B}{\epsilon}\geq 1\), we have that the Rademacher complexity of \(\mathcal{F}_{k}\) on \(m\) inputs from \(\{\mathbf{x}\in\mathbb{R}^{d}:\left\|\mathbf{x}\right\|\leq 1\}\) is at most \(\epsilon\), if_

\[m\geq\left(\frac{LB}{\epsilon}\right)^{\frac{\epsilon L^{2}B^{2}}{\epsilon^{2}}}\]

_where \(L:=\prod_{j=2}^{k}S_{j}\) and \(c>0\) is some universal constant._

Of course, the bound has a bad dependence on the norm of the weights, the Lipschitz parameter and \(\epsilon\). 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 size-independent setting, controlling the product of the spectral norms is both necessary and not 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.

### No Finite Sample Complexity with \(W_{0}\neq 0\)

In subsection 3.1, we showed size-independent sample complexity bounds when the initialization/reference matrix \(W_{0}\) is zero. Therefore, it is natural to ask if it is possible to achieve similar size-independent bounds with non-zero \(W_{0}\). In this subsection we show that perhaps surprisingly, the answer is negative: Even for very small non-zero \(W_{0}\), it is impossible to control the sample complexity of \(\mathcal{F}_{B,n,d}^{f,W_{0}}\) independent of the size/dimension parameters \(d,n\). Formally, we have the following theorem:
**Theorem 3**.: _For any \(m\in\mathbb{N}\) and \(0<\epsilon\leq 0.5\), there exists \(d=\Theta(m),n=\Theta(\exp(m))\), \(W_{0}\in\mathbb{R}^{n\times d}\) with \(\|W_{0}\|=2\sqrt{2}\cdot\epsilon\) and a function \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}\) which is \(1\)-Lipschitz with respect to the infinity norm (and hence also with respect to the Euclidean norm), for which \(\mathcal{F}_{B=\sqrt{2},n,d}^{f,W_{0}}\) can shatter \(m\) points from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq 1\}\) with margin \(\epsilon\)._

The theorem strengthens the lower bound of Daniely and Granot (2022) and the previous subsection, which only considered the \(W_{0}=0\) case. We emphasize that the result holds already when \(||W_{0}||\) is very small (equal to \(2\sqrt{2}\cdot\epsilon\)). Moreover, it holds 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). 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 to obtain sample complexity guarantees (e.g., Daniely and Granot (2019)).

Interestingly, the proof of the theorem is simpler than the \(W_{0}=0\) case, and involves a direct non-probabilistic construction. It can be intuitively described as follows: We choose a fixed set of vectors \(\mathbf{x}_{1},\ldots,\mathbf{x}_{m}\) and a matrix \(W_{0}\) (essentially the identity matrix with some padding) so that \(W_{0}\mathbf{x}_{i}\) encodes the index \(i\). For any choice of target values \(\mathbf{y}\in\{\pm\epsilon\}^{m}\), we define a matrix \(W_{\mathbf{y}}^{\prime}\) (which is all zeros except for a single entry with value \(1\) in a strategic location), so that \(W_{\mathbf{y}}^{\prime}\mathbf{x}_{i}\) encodes the entire vector \(\mathbf{y}\). We note that this is possible if the number of rows of \(W_{\mathbf{y}}^{\prime}\) is exponentially large in \(m\). Letting \(W_{\mathbf{y}}=W_{\mathbf{y}}^{\prime}+W_{0}\), we get a matrix of bounded distance to \(W_{0}\), so that \(W_{\mathbf{y}}\mathbf{x}_{i}\) encodes both \(i\) and \(\mathbf{y}\). Thus, we just need \(f\) to be the fixed function that given an encoding for \(\mathbf{y}\) and \(i\), returns \(y_{i}\), hence \(\mathbf{x}\mapsto f(W_{\mathbf{y}}\mathbf{x})\) shatters the set of points.

### Vector-valued Linear Predictors are Learnable without Uniform Convergence

The class \(\mathcal{F}_{B,n,d}^{f,W_{0}}\), which we considered in the previous subsection, is closely related to the natural class of matrix-valued linear predictors (\(\mathbf{x}\mapsto W\mathbf{x}\)) with bounded Frobenius distance from initialization, composed with some Lipschitz loss function \(\ell\). We can formally define this class as

\[\mathcal{G}_{B,n,d}^{\ell,W_{0}}:=\left\{(\mathbf{x},y)\rightarrow\ell(W \mathbf{x};y)\ :\ W\in\mathbb{R}^{n\times d},\|W-W_{0}\|_{F}\leq B\right\}\.\]

For example, standard multiclass linear predictors fall into this form. Note that when \(y\) is fixed, this is nothing more than the class \(\mathcal{F}_{B,n,d}^{\ell_{y},W_{0}}\) where \(\ell_{y}(z)=\ell(z;y)\). The question of learnability here boils down to the question of whether, given an i.i.d. sample \(\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m}\) from an unknown distribution, we can approximately minimize \(\mathbb{E}_{(\mathbf{x},y)}[\ell(W\mathbf{x},y)]\) arbitrarily well over all \(W:\|W-W_{0}\|\leq B\), provided that \(m\) is large enough.

For multiclass linear predictors, it is natural to consider the case where the loss \(\ell\) is also convex in its first argument. In this case, we can easily establish that the class \(\mathcal{G}_{B,n,d}^{\ell,W_{0}}\) is learnable with respect to inputs of bounded Euclidean norm, regardless of the size/dimension parameters \(n,d\). This is because for each \((\mathbf{x},y)\), the function \(W\mapsto\ell(W\mathbf{x};y)\) is convex and Lipschitz in \(W\), and the domain \(\{W:||W-W_{0}||_{F}\leq B\}\) is bounded. Therefore, we can approximately minimize \(\mathbb{E}_{(\mathbf{x},y)}[\ell(W\mathbf{x},y)]\) by applying stochastic gradient descent (SGD) over the sequence of examples \(\{\mathbf{x}_{i},y_{i}\}_{i=1}^{m}\). This is a consequence of well-known results (see for example Shalev-Shwartz and Ben-David (2014)), and is formalized as follows:

**Theorem 4**.: _Suppose that for any \(y\), the function \(\ell(.,y)\) is convex and \(L\)-Lipschitz. For any \(B>0\) and fixed matrix \(W_{0}\), there exists a randomized algorithm (namely stochastic gradient descent) with the following property: For any distribution over \((\mathbf{x},y)\) such that \(||\mathbf{x}||\leq 1\) with probability \(1\), given an i.i.d. sample \(\{(\mathbf{x}_{i},y_{i})\}_{i=1}^{m}\), the algorithm returns a matrix \(\tilde{W}\) such that \(||\tilde{W}-W_{0}||_{F}\leq B\) and_

\[\mathbb{E}_{\tilde{W}}\left[\mathbb{E}_{(\mathbf{x},y)}[\ell(\tilde{W}\mathbf{x} ;y)]-\min_{W:\|W-W_{0}\|_{F}\leq B}\mathbb{E}_{(\mathbf{x},y)}[\ell(W\mathbf{ x};y)]\right]\ \leq\ \frac{BL}{\sqrt{m}}.\]
_Thus, the number of samples \(m\) required to make the above less than \(\epsilon\) is at most \(\frac{B^{2}L^{2}}{\epsilon^{2}}\)._

Perhaps unexpectedly, we 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 \(\ell(W\mathbf{x};y)\) are close uniformly over all \(W:\|W-W_{0}\|\leq 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 \(\mathcal{G}^{\ell,W_{0}}_{B,n,d}\) can shatter arbitrarily many points of norm \(\leq 1\), and at any scale \(\epsilon\leq 1\), for some small \(W_{0}\) and provided that \(n,d\) are large enough3. In the previous section, we already showed such a result for the class \(\mathcal{F}^{f,W_{0}}_{B,n,d}\), which equals \(\mathcal{G}^{\ell,W_{0}}_{B,n,d}\) when \(y\) is fixed and \(f(W\mathbf{x})=\ell(W\mathbf{x};y)\). Thus, it is enough to prove that the same impossibility result (Theorem 3) holds even if \(f\) is a convex function. This is indeed true using a slightly different construction:

Footnote 3: This precludes uniform convergence, since it implies that for any \(m\), we can find a set of \(2m\) points \(\{\mathbf{x}_{i},y_{i}\}_{i=1}^{2m}\), such that if we sample \(m\) points with replacement from a uniform distribution over this set, then there is always some \(W\) in the class so that the average value of \(\ell(W\mathbf{x};y)\) over the sample and in expectation differs by a constant independent of \(m\). The fact that the fat-shattering dimension is unbounded does not contradict learnability here, since our goal is to minimize the expectation of \(\ell(W\mathbf{x};y)\), rather than view it as predicted values which are then composed with some other loss.

**Theorem 5**.: _For any \(m\in\mathbb{N}\) and \(0<\epsilon\leq 0.5\), there exists large enough \(d=\Theta(m),n=\Theta(\exp(m))\), \(W_{0}\in\mathbb{R}^{n\times d}\) with \(\|W_{0}\|=4\sqrt{2}\cdot\epsilon\) and a **convex** function \(f:\mathbb{R}^{n}\to\mathbb{R}\) which is \(1\)-Lipschitz with respect to the infinity norm (and hence also with respect to the Euclidean norm), for which \(\mathcal{F}^{f,W_{0}}_{B=\sqrt{2},n,d}\) can shatter \(m\) points from \(\{\mathbf{x}\in\mathbb{R}^{d}:\|\mathbf{x}\|\leq 1\}\) with margin \(\epsilon\)._

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 a 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 learnability 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 \(\mathbf{x}\mapsto f(W\mathbf{x})\) (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 is 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 \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq b_{x}\}\), where \(\sigma(\cdot)\) is a Lipschitz function on \(\mathbb{R}\) applied element-wise, and where we only bound the norms as follows:

\[\mathcal{F}^{\sigma,W_{0}}_{b,B,n,d}:=\left\{\mathbf{x}\to\mathbf{u}^{\top} \sigma(W\mathbf{x}):\mathbf{u}\in\mathbb{R}^{n},W\in\mathbb{R}^{n\times d},|| \mathbf{u}||\leq b,||W-W_{0}||_{F}\leq B\right\}\,\]

where \(\mathbf{u}^{\top}\sigma(W\mathbf{x})=\sum_{j}u_{j}\sigma(\mathbf{w}_{j}^{ \top}\mathbf{x})\). We note that we could have also considered a more general version, where \(\mathbf{u}\) is also initialization-dependent: Namely, where the constraint \(||\mathbf{u}||\leq b\) is replaced by \(||\mathbf{u}-\mathbf{u}_{0}||\leq b\) for some fixed \(\mathbf{u}_{0}\). However, this extension is rather trivial, since for vectors \(\mathbf{u}\) there is no distinction between the Frobenius and spectral norms. Thus, to consider \(\mathbf{u}\) in some ball of radius \(b\) around some \(\mathbf{u}_{0}\), we might
as well consider the function class displayed above with the looser constraint \(||\mathbf{u}||\leq b+||\mathbf{u}_{0}||\). This does not lose much tightness, since such a dependence on \(||\mathbf{u}_{0}||\) is also necessary (see remark 2 below).

The sample complexity of \(\mathcal{F}^{\sigma,W_{0}}_{b,B,n,d}\) was first studied in the case of \(W_{0}=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 \(\sigma(\cdot)\) (e.g., homogeneous or quadratic). For general Lipschitz \(\sigma(\cdot)\) and \(W_{0}=0\), Vardi et al. (2022) proved that the Rademacher complexity of \(\mathcal{F}^{\sigma,W_{0}=0}_{b,B,n,d}\) for any \(L\)-Lipschitz \(\sigma(\cdot)\) is at most \(\epsilon\), if the number of samples is \(\tilde{O}\left(\left(\frac{bB_{x}L}{\epsilon}\right)^{2}\right).\)They left the case of \(W_{0}\neq 0\) as an open question. In a recent preprint, Daniely and Granot (2022) used an innovative technique to prove a bound in this case, but not a fully size-independent one (there remains a logarithmic dependence on the network width \(n\) and the input dimension \(d\)). In what follows, we prove a bound which handles the \(W_{0}\neq 0\) case and is fully size-independent, under the assumption that \(\sigma(\cdot)\) is smooth. The proof (which is somewhat involved) involves techniques different from both previous papers, and may be of independent interest.

**Theorem 6**.: _Suppose \(\sigma(\cdot)\) (as function on \(\mathbb{R}\)) is \(L\)-Lipschitz, \(\mu\)-smooth (i.e, \(\sigma^{\prime}(\cdot)\) is \(\mu\)-Lipchitz) and \(\sigma(0)=0\). Then for any \(b,B,n,D,\epsilon>0\) such that \(Bb_{x}\geq 2\), and any \(W_{0}\) such that \(||W_{0}||\leq B_{0}\), the Rademacher complexity of \(\mathcal{F}^{\sigma,W_{0}}_{b,B,n,d}\) on m inputs from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq b_{x}\}\) is at most \(\epsilon\), if_

\[m\geq\frac{1}{\epsilon^{2}}\cdot\tilde{O}\left((1+bb_{x}(LB_{0}+(\mu+L)B(1+B_{ 0}b_{x}))^{2}\right).\]

Thus, we get a sample complexity bounds that depend on the norm parameters \(b,b_{x},B_{0}\), the Lipschitz parameter \(L\), and the smoothness parameter \(\mu\), but is fully independent of the size parameters \(n,d\). Note that for simplicity, the bound as written above hides some factors logarithmic in \(m,B,L,b_{x}\) - see the proof in the appendix for the precise expression.

We note that if \(W_{0}=0\), we can take \(B_{0}=0\) in the bound above, in which case the sample complexity scales as \(\tilde{O}(((\mu+L)bb_{x}B)^{2}/\epsilon^{2})\). This is is the same as in Vardi et al. (2022) (see above) up to the dependence on the smoothness parameter \(\mu\).

**Remark 2**.: _The upper bound on Theorem 6 depends quadratically on the spectral norm of \(W_{0}\) (i.e., \(B_{0}\)). This dependence is necessary in general. Indeed, even by taking the activation function \(\sigma(\cdot)\) to be the identity, \(B=0\) and \(b=1\) we get that our function class contains the class of scalar-valued linear predictors \(\{\mathbf{x}\rightarrow\mathbf{v}^{\top}\mathbf{x}:\mathbf{x},\mathbf{v}\in \mathbb{R}^{d},||\mathbf{v}||\leq B_{0}\}\). For this class, it is well known that the number of samples should be \(\Theta(\frac{B_{0}^{2}}{\epsilon^{2}})\), to ensure that the Rademacher complexity of that class is at most \(\epsilon\)._

### Bounds for Deep Networks with Lipschitz Activations

As a final contribution, we consider the case of possibly deep neural networks, when \(W_{0}=0\) and the activations are Lipschitz and element-wise. Specifically, given the domain \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq b_{x}\}\) in Euclidean space, we consider the class of scalar-valued neural networks of the form

\[\mathbf{x}\rightarrow\mathbf{w}_{k}^{\top}\sigma_{k-1}(W_{k-1}\sigma_{k-2}(...\sigma_{1}((W_{1}\mathbf{x})))\]

where \(\mathbf{w}_{k}\) is a vector (i.e. the output of the function is in \(\mathbb{R}\)) with \(||\mathbf{w}_{k}||\leq b\), each \(W_{j}\) is a parameter matrix s.t. \(||W_{j}||_{F}\leq B_{j}\), \(||W_{j}||\leq S_{j}\) and each \(\sigma_{j}(\cdot)\) (as a function on \(\mathbb{R}\)) is an \(L\)-Lipschitz function applied element-wise, satisfying \(\sigma_{j}(0)=0\). Let \(\mathcal{F}^{\{\sigma_{j}\}}_{k,\{S_{j}\},\{B_{j}\}}\) be the class of neural networks as above. Vardi et 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 depth-\(k\) neural networks to depth-\(k-1\) neural networks. The resulting bound is fully independent of the network width (although strongly depends on the network depth), and is the first of this type (to the best of our knowledge) that handles general Lipschitz activations under Frobenius norm constraints.

**Theorem 7**.: _For any \(\epsilon,b>0,\{B_{j}\}_{j=1}^{k-1},\{S_{j}\}_{j=1}^{k-1},L\) with \(S_{1},...,S_{k-1},L\geq 1\), the Rademacher complexity of \(\mathcal{F}_{k,\{S_{j}\},\{B_{j}\}}^{\{\sigma_{j}\}}\) on \(m\) inputs from \(\{\mathbf{x}\in\mathbb{R}^{d}:||\mathbf{x}||\leq b_{x}\}\) is at most \(\epsilon\), if_

\[m\geq\frac{c\left(kL^{k-1}bR_{k-2}\log^{\frac{3(k-1)}{2}}(m)\cdot\prod_{i=1}^ {k-1}B_{i}\,\right)^{2}}{\epsilon^{2}}\,\]

_where \(R_{k-2}=b_{x}L^{k-2}\prod_{i=1}^{k-2}S_{i}\), \(R_{0}=b_{x}\) and \(c>0\) is a 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 a few avenues for future research. For example, in Section 3, we studied the sample complexity of \(\mathcal{F}_{B,n,d}^{f,W_{0}}\) when \(n,d\) are unrestricted. Can we get a full picture of the sample complexity when \(n,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 in Section 4, is our Rademacher complexity bound for \(\mathcal{F}_{b,B,n,d}^{\sigma,W_{0}}\) (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,d\) are also controlled? In a different direction, it would be very interesting to extend the results of this section to deeper networks and non-zero \(W_{0}\).

### Acknowledgements

This research is supported in part by European Research Council (ERC) grant 754705.
