On the Power and Limitations of Random Features for Understanding Neural Networks

Introduction

Deep learning, in the form of artificial neural networks, has seen a dramatic resurgence in popularity in recent years. This is mainly due to impressive performance gains on various difficult learning problems, in fields such as computer vision, natural language processing and many others. Despite the practical success of neural networks, our theoretical understanding of them is still very incomplete.

A key aspect of modern networks is that they tend to be very large, usually with many more parameters than the size of the training data: In fact, so many that in principle, they can simply memorize all the training examples (as shown in the influential work of Zhang et al. ). The fact that such huge, over-parameterized networks are still able to learn and generalize is one of the big mysteries concerning deep learning. A current leading hypothesis is that over-parameterization makes the optimization landscape more benign, and encourages standard gradient-based training methods to find weight configurations that fit the training data as well as generalize (even though there might be many other configurations which fit the training data without any generalization). However, pinpointing the exact mechanism by which over-parameterization helps is still an open problem.

Recently, a spate of papers (such as ) provided positive results for training and learning with over-parameterized neural networks. Although they differ in details, they are all based on the following striking observation: When the networks are sufficiently large, standard gradient-based methods change certain components of the network (such as the weights of a certain layer) very slowly, so that if we run these methods for a bounded number of iterations, they might as well be fixed. To give a concrete example, consider one-hidden-layer neural networks, which can be written as a linear combination of $r$ neurons

using weights $\{u_{i},w_{i},b_{i}\}_{i=1}^{r}$ and an activation function $\sigma$. When $r$ is sufficiently large, and with standard random initializations, it can be shown that gradient descent will leave the weights $w_{i},b_{i}$ in the first layer nearly unchanged (at least initially). As a result, the dynamics of gradient descent will resemble those where $\{w_{i},b_{i}\}$ are fixed at random initial values – namely, where we learn a linear predictor (parameterized by $u_{1},\ldots,u_{r}$) over a set of $r$ random features of the form $x\mapsto\sigma(\langle w_{i},x\rangle+b_{i})$ (for some random choice of $w_{i},b_{i}$). For such linear predictors, it is not difficult to show that they will converge quickly to an optimal predictor (over the span of the random features). This leads to learning guarantees with respect to hypothesis classes which can be captured well by such random features: For example, most papers focus (explicitly or implicitly) on multivariate polynomials with certain constraints on their degree or the magnitude of their coefficients. We discuss these results in more detail (and demonstrate their close connection to random features) in Section 2.

Taken together, these results are a significant and insightful advance in our understanding of neural networks: They rigorously establish that sufficient over-parameterization allows us to learn complicated functions, while solving a non-convex optimization problem. However, it is important to realize that this approach can only explain learnability of hypothesis classes which can already be learned using random features. Considering the one-hidden-layer example above, this corresponds to learning linear predictors over a fixed representation (chosen obliviously and randomly at initialization). Thus, it does not capture any element of representation learning, which appears to lend much of the power of modern neural networks.

(where $[z]_{+}=\max\{0,z\}$ is the ReLU function and $x$ has a standard Gaussian distribution) then

In other words, either the number of features $r$ or the magnitude of the weights (or both) must be exponential in the dimension $d$. Moreover, if the random features can be written as $x\mapsto f_{i}(Wx)$ for a random matrix $W$ (which includes for instance vanilla neural networks of any size), then the same result holds for any choice of $w^{*}$. These results imply that the random features approach cannot fully explain polynomial-time learnability of neural networks, even with respect to data generated by an extremely simple neural network, composed of a single neuron. This is despite the fact that single ReLU neurons with Gaussian inputs are easily learnable with gradient-based methods (e.g., , To be precise, existing theoretical results usually ignore the bias term for simplicity, but we believe this is not a real impediment for the analysis.). The point we want to make here is that the random feature approach, as a theory for explaining the success of neural networks, cannot explain even the fact that single neurons are learnable.

For completeness we also provide a simple, self-contained analysis, showing how over-parameterized, one-hidden-layer networks can provably learn polynomials with bounded degrees and coefficients, using standard stochastic gradient descent with standard initialization.

We emphasize that there is no contradiction between our positive and negative results: In the positive result on learning polynomials, the required size of the network is exponential in the degree of the polynomial, and low-degree polynomials cannot express even a single ReLU neuron if its weights are large enough.

Overall, we argue that although the random feature approach captures important aspects of training neural networks, it is by no means the whole story, and we are still quite far from a satisfying general explanation for the empirical success of neural networks.

The recent literature on the theory of deep learning is too large to be thoroughly described here. Instead, we survey here some of the works most directly relevant to the themes of our paper. In Section 2, we provide a more technical explanation on the connection of recent results to random features.

The Power of Over-Parameterization. The fact that over-parameterized networks are easier to train was empirically observed, for example, in , and was used in several contexts to show positive results for learning and training neural networks. For example, it is known that adding more neurons makes the optimization landscape more benign (e.g., ), or allows them to learn in various settings (e.g., besides the papers mentioned in the introduction, ).

Random Features. The technique of random features was proposed and formally analyzed in , originally as a computationally-efficient alternative to kernel methods (although as a heuristic, it can be traced back to the “random connections” feature of Rosenblatt’s Perceptron machine in the 1950’s). These involve learning predictors of the form $x\mapsto\sum_{i=1}^{r}u_{i}\psi_{i}(x)$, where $\psi_{i}$ are random non-linear functions. The training involves only tuning of the $u_{i}$ weights. Thus, the learning problem is as computationally easy as training linear predictors, but with the advantage that the resulting predictor is non-linear, and in fact, if $r$ is large enough, can capture arbitrarily complex functions. The power of random features to express certain classes of functions has been studied in past years (for example ). However, in our paper we also consider negative rather than positive results for such features. also discusses the limitation of approximating functions with a bounded number of such features, but in a different setting than ours (worst-case approximation of a large function class using a fixed set of features, rather than inapproximability of a fixed target function, and not in the context of single neurons). Less directly related, studied learning neural networks using kernel methods, which can be seen as learning a linear predictor over a fixed non-linear mapping. However, the algorithm is not based on training neural networks with standard gradient-based methods. In a very recent work (and following the initial dissemination of our paper), Ghorbani et al. studied the representation capabilities of random features, and showed that in high dimensions random features are not good at fitting high degree polynomials.

Notation

Analysis of Neural Networks as Random Features

In many previous works, a key element is to analyze neural networks as if they are random features, either explicitly or implicitly. Here we survey some of these works and how they can actually be viewed as random features.

For example, a one-hidden-layer neural network where the activation $\sigma$ is the ReLU function can be written as

Using the coupling method, after doing gradient descent, the amount of neurons that change sign, i.e. the sign of $\langle w_{i}^{(t)},x\rangle$ changes, is small. As a result, using the homogeneity of the ReLU function, the following network can actually be analyzed:

2 Optimization on all the Layers

A second approach in the literature (e.g. Andoni et al. , Daniely et al. , Du et al. ) is to perform optimization on all the layers of the network, choose a ”good” learning rate and bound the number of iterations such that the inner layers stay close to their initialization. For example, in the setting of a one-hidden-layer network, for every $\epsilon>0$, a learning rate $\eta$ and number of iterations $T$ are chosen, such that after running gradient descent with these parameters, there is an iteration $1\leq t\leq T$ such that:

Hence, it is enough to analyze a linear predictor over a set of random features:

where $\sigma$ is not necessarily the ReLU function. Again, the difficulty here is finding the functions that can be approximated in this form, where $r$ (the amount of neurons) is only polynomial in the relevant parameters.

Over-Parameterized Neural Networks Learn Polynomials

For completeness we provide a simple, self-contained analysis, showing how over-parameterized, one-hidden-layer networks can provably learn polynomials with bounded degrees and coefficients, using standard stochastic gradient descent with standard initialization.

We consider one-hidden-layer feed-forward neural networks which are defined as:

For simplicity we will use the hinge loss, which is defined by: $l(\hat{y},y)=\max\{0,1-\hat{y}y\}$, thus the optimization will be done on the function $l(N(x),y)=l(N(W,U,x),y)$. We will also use the notation:

We will use the standard form of SGD to optimize $L_{D}$, where at each iteration a random sample $(x,y)$ is drawn from $D$ and we update:

The initialization of $W_{0}$ is a standard Xavier initialization , that is $w_{i}\sim U\left(\left[\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]^{d}\right)$. $U_{0}$ can be initialized in any manner, as long as its norm is smaller than $\frac{1}{\sqrt{r}}$, e.g. we can initialize $U_{0}$ = 0. This kind of initialization for the outer layer has been used also in other works (see , ).

The main result of this section is the following:

$r$ neurons with $r\geq\frac{64\beta^{6}L^{2}}{\epsilon^{4}}log\left(\frac{1}{\delta}\right)$

$W_{0}$ is initialized with $w_{i}\sim U\left(\left[\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]^{d}\right)$ for $i=1,\dots,r$ and $U_{0}$ is initialized s.t $\|U_{0}\|\leq\frac{1}{\sqrt{r}}$

$T$ steps with $T=\frac{4\beta^{2}}{\epsilon^{2}}$ ,

Here the expectation is over the random choice of $(x_{i},y_{i})$ in each iteration of SGD.

We note that for simplicity, we focused on analytic activation functions, although it is possible to derive related results for non-analytic activations such as a ReLU (see Appendix F for a discussion). The assumptions on the Taylor coefficients of the activation function includes for example the $\exp$ and $\rm{erf}$ activations. We note that similar assumptions were used also in other works on learning polynomials (e.g. ). Also, note that we did not use a bias term in the architecture of the network in the theorem (namely, we have $\sigma(\langle w_{i},x\rangle)$ and not $\sigma(\langle w_{i},x\rangle+b_{i})$). This is because if the polynomial we are trying to compete with has a constant factor, then we require that the Taylor expansion of the activation also has a constant factor, thus the bias term is already included in the Taylor expansion of the activation function.

Suppose we are given a sample set $S=\{(x_{i},y_{i})\}_{i=1}^{m}$. By choosing $D$ uniform on the sample set $S$, Theorem 3.1 shows that SGD over the sample set will lead to an average loss not much worse than the best possible polynomial predictor with bounded degree and coefficients.

At high level, the proof idea of Theorem 3.1 is divided into three steps. In the first step we show that with an appropriate learning rate and limited amount of iterations, neural networks generalize better than random features. This step allows us to focus our analysis on the behaviour of a linear combination of random features instead of the more complicated architecture of neural networks. In the second step using McDiarmid’s theorem we show that by taking enough random features, they concentrate around their expectation. In the third step we use Legendre’s polynomials to show that any polynomial can be approximated by an expectation of random features.

We break the proof to three steps, where each step contains a theorem which is independent of the other steps. Finally we combine the three steps to prove the main theorem.

where $W_{0},\ U_{0}$ are initialized as described in the theorem We show that for any target matrix $U^{*}$ with a small enough norm and every $\epsilon>0$, if we run SGD on $l(N(W_{0},U_{0},x),y)$ with appropriate learning rate $\eta$ and number of iterations $T$, there is some $t\in[T]$ with:

where the expectation is over the random choices of examples in each round of SGD. The bound in Eq. (4) means that SGD on randomly initialized weights competes with random features. By random features here we mean any linear combination of neurons of the form $\sigma(\langle w_{i},x\rangle)$ where the $w_{i}$ are randomly chosen, and the norm of the weights of the linear combination are bounded. In more details:

Assume we initialize $U_{0},W_{0}$ such that $\|U_{0}\|\leq\frac{1}{\sqrt{r}}$ and $\|W_{0}\|\leq\sqrt{r}$. Also assume that $\sigma$ is $L$-Lipschitz with $\sigma(0)\leq L$, and let $C\geq 1$ be a constant. Letting $\epsilon>0$, we run SGD with step size $\eta=\frac{\epsilon}{8r}$ and $T$ steps with $T=\frac{4C^{2}}{\epsilon^{2}}$ and let $W_{1},\dots,W_{T}$ be the weights produced at each step. If we pick $r$ such that $r\geq\frac{64C^{6}L^{2}}{\epsilon^{4}}$ then for every target matrix $U^{*}$ with $\|U^{*}\|\leq\frac{C}{\sqrt{r}}$ there is a $t\in[T]$ s.t:

Here the expectation is over the random choice of the training examples in each round of SGD.

In the proof of Theorem 3.2 we first show that for the chosen learning rate $\eta$ and limited number of iterations $T$, the matrix $W$ does not change much from its initialization. After that we use results from online convex optimization for linear prediction with respect to $U^{*}$ with a sufficiently small norm to prove the required bound. For a full proof see Appendix E. Note that in the theorem we did not need to specify the initialization scheme, only to bound the norm of the initialized weights. The optimization analysis is similar to the one done in Daniely .

Step 2: Random Features Concentrate Around their Expectation

where $|u_{i}|\leq\frac{C}{r}$ for every $1\leq i\leq r$, such that:

Theorem 3.3 basically states that random features concentrate around their expectation, and the rate of convergence is $O\left(\frac{1}{\sqrt{r}}\right)$ where $r$ is the amount of random features that were sampled. The proof is based on concentration of measure and Rademacher complexity arguments, and appears in Appendix D.

Step 3: Approximating Polynomials Using Expectation of Random Features

In the previous step we showed that random features can approximate functions with the integral form:

In this step we show how a a polynomial $P(x)$ with bounded degree and coefficients can be approximated by this form. This means that we need to find a function $g(w)$ for which $f(x)=P(x)$. To do so we use the fact that $\sigma(x)$ is analytic, thus it can be represented as an infinite sum of monomials using a Taylor expansion, and take $g(w)$ to be a finite weighted sum of Legendre polynomials, which are orthogonal with respect to the appropriate inner product. The main difficulty here is to find a bound on $\max_{w\in\left[\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]^{d}}|g(w)|$, which in turn also bounds the distance between the sum of the random features and its expectation. The main theorem of this step is:

$\max_{\|x\|\leq 1}\left|c_{d}\int_{w\in\left[-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]}\sigma(\langle w,x\rangle)g(w)dw-P(x)\right|<\epsilon$

where $c_{d}=\left(\frac{\sqrt{d}}{2}\right)^{d}$ is a normalization term.

For a full proof of Theorem 3.4 and an overview of Legendre polynomials see Appendix C.

Step 4: Putting it all Together

We are now ready to prove the main theorem of this section. The proof is done for convenience in reverse order of the three steps presented above.

Let $a_{0},a_{1},\dots,a_{k}$ be the coefficients of the Taylor expansion of $\sigma$ up to degree $k$, and let $P(x)$ be a a polynomial with $\deg(P)\leq k$ and $|P|\leq\alpha$, such that if $a_{j}=0$ then the monomials in $P(x)$ of degree $j$ also have a zero coefficient.

First, we use Theorem 3.4 to find a function $g(w)$ such that:

Then we consider drawing random features $w_{1},\dots,w_{r}\sim U\left(\left[\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]^{d}\right)$ i.i.d. Using Theorem 3.3, the choice of $r$ and Eq. (5), w.p $>1-\delta$ there is $U^{*}=(u_{1},\dots,u_{r})$ such that:

and also $|u_{i}|\leq\max_{\|w\|\leq 1}\frac{|g(w)|}{r}\leq\alpha^{k}\left(\frac{A}{a}\right)^{k}(12d)^{2k^{2}}$, thus $\|U^{*}\|\leq\frac{\alpha^{k}\left(\frac{A}{a}\right)^{k}(12d)^{2k^{2}}}{\sqrt{r}}$.

Finally, we use Theorem 3.2 with the defined learning rate $\eta$ and iterations $T$ to find $t\in[T]$ such that:

Combining Eq. (5), Eq. (6) with Eq. (7) gives:

Re-scaling $\epsilon$ finishes the proof. ∎

Limitations of Random Features

Having discussed and shown positive results for learning using (essentially) random features, we turn to discuss the limitations of this approach.

where $f_{i}$ are the random features. Importantly, when $r=1$, $\sigma$ is the ReLU function, and $f_{1}(x)=\sigma(\langle w,x\rangle+b)$ (that is, we train a single neuron with Gaussian inputs to learn a single target neuron), this problem is quite tractable with standard gradient-based methods (see, e.g., , ). In this section, we ask whether this positive result – that single target neurons can be learned – can be explained by the random features approach. Specifically, we consider the case where the function $f_{i}$ are arbitrary functions chosen obliviously of the target neuron (e.g. multilayered neural networks at a standard random initialization), and ask what conditions on $r$ and $u_{i}$ are required to minimize Eq. (8). Our main results (Theorem 4.1 and Theorem 4.2) show that either one of them has to be exponential in the dimension $d$, as long as the sizes of $w^{*},b^{*}$ are allowed to be polynomial in $d$. Since networks with exponentially-many neurons or exponentially-sized weights are generally not efficiently trainable, we conclude that an approach based on random-features cannot explain why learning single neurons is tractable in practice. In Theorem 4.1, we show the result for any choice of $w^{*}$ with some fixed norm, but require the feature functions to have a certain structure (which is satisfied by neural networks). In Theorem 4.2, we drop this requirement, but then the result only holds for a particular $w^{*}$.

To simplify the notation in this section, we consider functions on $x$ as elements of the $L^{2}$ space weighted by a standard Gaussian measure, that is

where $c_{d}=\left(\frac{1}{\sqrt{2\pi}}\right)^{d}$ is a normalization term. For example, Eq. (8) can also be written as $\|\sum_{i=1}^{r}u_{i}f_{i}(x)-\sigma(\langle w^{*},x\rangle+b^{*})\|^{2}$.

Before stating our main results, let us consider a particularly simple case, where $\sigma$ is the identity, and our goal is to learn a linear predictor $\mathbf{x}\mapsto\langle w^{*},x\rangle$ with $\|w^{*}\|=1$. We will show that already in this case, there is a significant cost to pay for using random features. The main result in the next subsection can be seen as an elaboration of this idea.

The following proposition shows that with high probability, Eq. (9) cannot hold unless $r=\Omega(d)$. This shows that even for linear predictors, there is a price to pay for using a combination of random features, instead of learning the linear predictor directly.

2 Features Based on Random Linear Transformations

Having discussed the linear case, let us return to the case of a non-linear neuron. Specifically, we will show that even a single ReLU neuron cannot be approximated by a very large class of random feature predictors, unless the amount of neurons in the network is exponential in the dimension, or the coefficients of the linear combination are exponential in the dimension. In more details:

Note that the theorem allows any “random” feature which can be written as a composition of some function $f$ (chosen randomly or not), and a random linear transformation. This includes as special cases one-hidden layer networks ($f_{i}(Wx)=\sigma(\langle W_{i},x\rangle)$, with each $W_{i}$ chosen randomly), or multi-layer neurons of any depth (as long as the first layer performs a random linear transformation).

As opposed to the linear case, here we also have a restriction on $\max_{i}|u_{i}|$. We conjecture that it is possible to remove this dependence and leave it to future work.

To prove the theorem, we will use the following proposition, which implies that functions of the form $x\mapsto\psi(\langle w,x\rangle)$ for a certain sine-like $\psi$ and ”random” $w$ are nearly uncorrelated with any fixed function.

It is a periodic odd function on the interval $[-a,a]$

For every $w^{*}$ with $\|w^{*}\|=d$, $\left\|\psi(\langle w^{*},x\rangle)\right\|^{2}\geq\frac{1}{6}$.

Items 1 and 2 follow by a straightforward calculation, where in item 2 we also used the fact that $x$ has a symmetric distribution. Item 3 relies on a claim from , which shows that periodic functions of the form $x\mapsto\psi(\langle w,x\rangle)$ for a random $w$ with sufficiently large norm have low correlation with any fixed function. The full proof can be found in Appendix B.

At a high level, the proof of Theorem 4.1 proceeds as follows: If we choose and fix $\{f_{i}\}_{i=1}^{r}$ and $W$, then any linear combination of random features $f_{i}(Wx)$ with small weights will be nearly uncorrelated with $\psi(\langle w^{*},x\rangle)$, in expectation over $w^{*}$ . But, we know that $\psi(\langle w^{*},x\rangle)$ can be written as a linear combination of ReLU neurons, so there must be some ReLU neuron which will be nearly uncorrelated with any linear combination of the random features (and as a result, cannot be well-approximated by them). Finally, by a symmetry argument, we can actually fix $w^{*}$ arbitrarily and the result still holds. We now turn to provide the formal proof:

where $c_{3}$ is a universal constant that depends only on the constant $c$ from Proposition 4.2 and on $c_{2}$. Hence also:

Therefore, there is $w^{*}$ with $\|w^{*}\|=d$ such that:

Using Markov’s inequality and dividing $c_{3}$ by a factor of $2$, we get w.p $>1-\exp\left(-c_{3}d\right)$ over sampling of $W$, $|\langle f_{W},\psi_{w^{*}}\rangle|\leq\exp(-c_{3}d)$ for the $w^{*}$ we found above. Finally, if we pick $f_{1},\dots,f_{r}\in\mathcal{F}$, using the union bound we get that w.p $>1-r\exp\left(-c_{3}d\right)$ over sampling of $W$:

where $\widetilde{u}_{i}=\left(\sum_{j=1}^{a}u_{i}^{j}a_{j}\right)$. On the other hand using Eq. (10) and item 2 from Proposition 4.2 we get w.p $>1-r\exp\left(-c_{3}d\right)$ over the distribution of $W$ that:

then r\max_{i}|u_{i}|\geq\big{(}1-576d^{4}\epsilon^{2})\frac{1}{144d^{2}}\exp\left(c_{3}d\right).

then r\max_{i}|u_{i}|\geq\big{(}1-576d^{4}\epsilon^{2})\frac{1}{144d^{2}}\exp\left(c_{3}d\right).

then $r\max_{i}|\hat{u}_{i}|\geq\frac{1}{200d^{4}}\exp\left(c_{3}d\right)$. ∎

3 General Features and Kernel Methods

In the previous subsection, we assumed that our features have a structure of the form $x\mapsto f(Wx)$ for a random matrix $W$. We now turn to a more general case, where we are given features $x\mapsto f(x)$ of any kind without any assumptions on their internal structure, as long as they are sampled from some fixed distribution. Besides generalizing the setting of the previous subsection, it also captures the setting of Subsection 2.1, where the coupling method is used in order to show that

The proof is similar to the proof of Theorem 4.1. The main difference is that we do not have any assumptions on the distribution of the random features (as the assumption on the distribution on $W$ in Theorem 4.1), hence we can only show that there exists some ReLU neuron that cannot be well-approximated. On the other hand, we have almost no restrictions on the random features, e.g. they can be multi-layered neural network of any architecture and with any random initialization, kernel-based features on sampled training sets, etc.

This research is supported in part by European Research Council (ERC) grant 754705. We thank Yuanzhi Li for some helpful comments on a previous version of this paper, and for Pritish Kamath and Alex Damian for spotting a bug in a previous version of the paper.

References

Appendices

Appendix A Comparison to Previous Works

The method from Subsection 2.1 is used in several works, for example:

Li and Liang show a generalization bound for ReLU neural networks where there is a strong separability assumption on the distribution of the data, which is critical in the analysis.

In Du et al. , it is shown that under some assumptions on the data, neural network with ReLU activation would reach a global minimum of the empirical risk in polynomial time.

Allen-Zhu et al. also show an empirical risk bound on a multi-layer feed-forward neural network with ReLU activation and relies on separability assumption on the data.

Allen-Zhu et al. show with almost no assumptions on the distribution of the data that the generalization of neural networks with two or three layers is better then the generalization of a ”ground truth” function for a large family of functions, which includes polynomials.

In Allen-Zhu and Li similar techniques are used to show a generalization bound on recurrent neural networks.

Cao and Gu show a generalization result for multi-layered networks, where the generalization is compared to a family of functions that take an integral form, similar to the one developed in Theorem 3.3. This integral form is also studied in , in the context of studying neural networks as random features.

All the above fix the weights of the output layer and consider only the ReLU activation function. Note that while using ReLU as an activation function, it is possible to show that fixing the output layer does not change the expressive power of the network. With that said, in practice all layers of neural networks are being optimized, and the optimization process may not work as well if some of the layers are fixed.

A.2 Optimization on all the Layers

The methods from Subsection 2.2 are also used in several works, for example:

In Andoni et al. this approach is also used to prove that neural networks can approximate polynomials. There the weights are drawn from a complex distribution, thus optimization is done on a complex domain which is non standard. Moreover, that paper uses the exponent activation function and assumes that the distribution on the data is uniform on the complex unit circle.

In Daniely et al. and Daniely this approach is used to get a generalization bound with respect to a large family of functions, where the network may have more than two layers and a different architecture than simple feed-forward. The methods used there are through the ”conjugate kernel”, which is a function corresponding to the activation and architecture of the network. The proof of our result is relatively more direct, and gives a bound which correspond directly to the activation function, without going through the conjugate kernel. Moreover, those papers do not quantitatively characterize the class of polynomials learned by the network, with an explicit proof.

Du and Lee rely on the same methods and assumptions as Du et al. to show an empirical risk bound on multi-layer neural network where a large family of activations is considered and with several architectures, including ResNets and convolutional ResNets. However, this does not imply a bound on the population risk.

Appendix B Proofs from section 4

In the proof of Proposition 4.2 we rely on the following claim from [32, Lemma 5] In order to deduce it we only need to note that since $\psi$ is odd, its first Fourier coefficient is $a_{0}=0$, and we can take $g=\widehat{f\phi}$ and use the fact that Fourier transform preserves inner products and norms.:

For every $x_{0}\in[-a,a-4]$ we have that:

where we used the fact that $a$ is odd. This proves that $\psi(x)$ is periodic in $[-a,a]$ with a period of $4$. To prove that $\psi(x)$ is an odd function, note that:

In the above, we used the fact that for every interval of the form $[n,n+2]$ for $n\in[-a,a-2]$, the integral

where we used the fact that since $x\sim N(0,I_{d})$ then $\langle\frac{w}{\|w\|},x\rangle$ has a standard Gaussian distribution, hence its fourth moment is $3$. Also $\langle w,x\rangle\sim N(0,d)$, Hence

Using Cauchy-Schwartz and Eq. (21) we can bound the second term:

and finally using Claim 1 on $\widetilde{\psi}(x)$, and taking $r=d$ we can bound the first term of Eq. (22), by changing the constant from the claim by a factor of at most $4$. Thus, there exists a universal constant $c$ such that:

where $c_{3}$ is a universal constant that depends only on the constant $c$ from Proposition 4.2 and on $c_{2}$. Thus, there exists $w^{*}$ such that:

Using Markov’s inequality on Eq. (23), with the fixed $w^{*}$ that was found and dividing $c_{3}$ by a factor of $2$, we get w.p $>1-r\exp\left(-c_{3}d\right)$ over sampling of $(f_{1},\dots,f_{r})\sim D$ that:

The rest of the proof is the same as the proof of Theorem 4.1, except for fixing the $w^{*}$ we found above. ∎

Appendix C Approximating Polynomials Using Expectation of Random Features

We will use the Legendre polynomials in the one variable and multi-variable case. Let $p_{1}(w),\dots,p_{k}(w)$ be the one variable Legendre polynomials, these polynomials are an orthogonal basis for one variable polynomials with respect to the inner product:

They are normalized by $p_{0}(w)=1$, and their inner product is:

Using tensor product of polynomial spaces, the polynomials $p_{J}$ for all multi-indices $J$ form an orthogonal base for $d$-dimensional polynomials (see ), with respect to the inner product:

which satisfies the requirements of the theorem, where the coefficients $c_{J}$ will be determined later. We will first show how to choose the coefficients $c_{J}$ so that $g(w)$ can indeed approximate polynomials, and then we will prove items (1) and (2) by bounding $\max_{w\in\left[-\frac{1}{\sqrt{d}},\frac{1}{\sqrt{d}}\right]}|g(w)|$. Since $\sigma$ is analytic we can use its Taylor expansion to get:

Plugging $g(w)$ and $c_{d}$ into Eq. (25) and using the change of variables $\sqrt{d}w\mapsto w$ gives:

Using Eq. (24) to expand $w^{J}$ in the Legendre basis, the above is equal to:

We now turn to bound $|c_{J}|$. For this, we will first need to bound $f_{J,J^{\prime}}$ and $\frac{1}{\|p_{J}\|^{2}}$. Using Rodrigues’ formula we can derive the following explicit representation of the $i$-th Legendre polynomial:

Next, we bound $\frac{1}{\|p_{J}\|^{2}}$. The norm of a single variable Legendre polynomial is given by:

Given a multi-index $J=(j_{1},\dots,j_{d})$ with $|J|=i$ and using this, we can write:

If $d\geq i$, then it is clear that the term in the nominator above is largest for $J$ with $i$ indices equals to 1, and the rest 0 (e.g $J=(\underbrace{1,\dots,1}_{\text{i}},\underbrace{0,\dots,0}_{\text{d-i}})$). For this case we bound:

If $d<i$, then the nominator of Eq. (32) is largest when the indices of J are equal, i.e. $J=\left(\left\lceil\frac{i}{d}\right\rceil,\dots,\left\lceil\frac{i}{d}\right\rceil\right)$. In this case, we can bound:

Note that for any value of $d\in\{1,\dots,i\}$ we have that $\left(\frac{i}{d}\right)^{d}\leq 2^{i}$, hence, we can bound the above as:

and by the arguments above, this gives us an upper bound also for the case of $d\geq i$ .

Using Eq. (C) and Eq. (33) we are now ready to bound $|c_{J}|$. By Eq. (29), for a multi-index $J$ with $|J|\leq i$ we have that:

where we used the bound $\sum_{j=0}^{k}\binom{d}{j}\leq(d+1)^{k}$.

which prove item (1). Plugging in $n$ into Eq. (C) gives us:

Appendix D Random Features Concentrate Around their Expectation

We will use McDiarmid’s inequality to bound $h$. For every $1\leq i\leq r$ and every $\widetilde{w_{i}}$ with $\|\widetilde{w_{i}}\|\leq 1$ we have that:

Where $\xi_{1},\dots,\xi_{r}$ are independent Rademacher random variables (where we write them as $\xi$ for short). Define $\sigma^{\prime}(x)=\sigma(x)-\alpha$, where $\sigma(0)=\alpha$, then we have that $\sigma^{\prime}(0)=0$. We use the fact that for i.i.d Rademacher random variables $\xi_{1},\dots,\xi_{r}$ :

combined with [6, Theorem 12(4)], Cauchy-Schwartz theorem and our assumptions that $\|x\|,\|w\|\leq 1$ to get:

We can now use McDiarmid’s inequality on $h(x)$ to get that:

Replacing the right hand side with $\delta$ we get that w.p $>$ $1-\delta$:

Appendix E SGD on Over-Parameterized Networks Competes with Random Features

Let $\|W_{0}\|,\ \|U_{0}\|\leq B$ with $B\geq 2$, then for every $\epsilon>0$ if we run SGD with learning rate of $\eta=\frac{\epsilon}{LB^{2}}$ we have that for all $t\leq\frac{B}{2\epsilon}$:

$\left\|\sigma(W_{t}x)-\sigma(W_{0}x)\right\|\leq 2Lt\epsilon$

We prove the first part by induction on $t$. First trivially it is true for $t=0$. Assume it is true for all $t\leq\frac{B}{2\epsilon}$. The gradients of $L_{D}(U,W)$ are:

We bound the gradients of $L_{D}(U,W)$ using Eq. (38) and Eq. (37), the assumptions on $\sigma$ and that $\|x\|\leq 1$:

Using the bounds on the gradient, at each step of SGD the norm of $W_{t+1}$ changed from the norm of $W_{t}$ by at most $\eta L\|U_{t}\|$. Thus, after $t$ iterations we get that

For the second part, using the previous part we get that:

Now we use the fact that $\sigma$ is $L$-Lipschitz, $\|x\|\leq 1$ and $|B|\geq 1$ to get that:

We will also use the following theorem about convex online learning (see [31, Theorem 21.15]):

Now we are ready to prove the generalization bound:

For every $1\leq t\leq T$ we have by Lemma E.1 that:

Where the last inequality is by the choice of $r$. We define the function $g_{t}(U):=l(N(W_{t},U,x_{t}),y_{t})$ where $(x_{t},y_{t})$ is the example sampled at round $t$ of SGD. Observe that:

where we used the fact that the loss is 1-Lipschitz. Also note that $g_{t}(U)$ are convex for every $t$. Using Lemma E.1 again:

thus $g_{t}(U)$ is also $2L\sqrt{r}$-Lipschitz for all $t$. We use Theorem E.1 on the functions $g_{t}$ to get:

Using the lower bound of $T$ we get that:

Combining Eq. (41) with Eq. (42) and plugging in $\eta$ gives us:

Thus there is $1\leq t\leq T$ that satisfies:

Rescaling $\epsilon$ appropriately finishes the proof. ∎

Appendix F Approximating polynomials with ReLU networks

Theorem 3.1 can be modified to also include the ReLU activation which is not analytic. This modification requires to add a bias term and also use a non-standard architecture for the network. For terseness we explain here how it can be done without writing the full proof: We begin with the following network architecture:

where $c=\frac{1}{e-1}$ is a normalization term which is added for simplicity. This architecture is similar to a standard feed-forward neural network, but includes duplicated ReLU neurons with a negative sign, and linear and constant factors. The initialization of $w_{i}$ and $u_{i}$ is the same as in Theorem 3.1, and the bias terms $b_{i}$ are initialized from a uniform distribution on $$. Steps 1 and 2 are similar to those used in the original theorem, with adjustments for the added terms, and also in step 2 the function$g(w)$should depend additionally on the bias term$g(w,b)$. Thus, we can approximate an integral of the form:

Plugging in $g(w,b)$ into Eq. (45), and using the integral from Eq. (46) with $z=\langle w_{i},x\rangle$ (note that $|\langle w_{i},x\rangle|^{2}\leq\|w\|^{2}\|x\|^{2}\leq 1)$ we can approximate an integral of the form:

Now we can use step 3 to finish the proof. The requirement for the extra linear and constant terms are also needed in . There it is shown that functions that admits certain Fourier transform representations can be approximated using a combination of ReLUs, with an extra linear and constant factors.