A Comparative Analysis of the Optimization and Generalization Property of Two-layer Neural Network and Random Feature Models Under Gradient Descent Dynamics

Introduction

Optimization and generalization are two central issues in the theoretical analysis of machine learning models. These issues are of special interest for modern neural network models, not only because of their practical success , but also because of the fact that these neural network models are often heavily over-parametrized and traditional machine learning theory does not seem to work directly . For this reason, there has been a lot of recent theoretical work centered on these issues . One issue of particular interest is whether the gradient descent (GD) algorithm can produce models that optimize the empirical risk and at the same time generalize well for the population risk. In the case of over-parametrized two-layer neural network models, which will be the focus of this paper, it is generally understood that as a result of the non-degeneracy of the associated Gram matrix , optimization can be accomplished using the gradient descent algorithm regardless of the quality of the labels, in spite of the fact that the empirical risk function is non-convex. In this regard, one can say that over-parametrization facilitates optimization.

The situation with generalization is a different story. There has been a lot of interest on the so-called “implicit regularization” effect , i.e. by tuning the parameters in the optimization algorithms, one might be able to guide the algorithm to move towards network models that generalize well, without the need to add any explicit regularization terms (see below for a review of the existing literature). But despite these efforts, it is fair to say that the general picture has yet to emerge.

In this paper, we perform a rather thorough analysis of the gradient descent algorithm for training two-layer neural network models. We study the case in which the parameters in both the input and output layers are updated – the case found in practice. In the heavily over-parametrized regime, for general initializations, we prove that the results of still hold, namely, the gradient descent dynamics still converges to a global minimum exponentially fast, regardless of the quality of the labels. However, we also prove that the functions obtained are uniformly close to the ones found in an associated kernel method, with the kernel defined by the initialization.

In the second part of the paper, we study the more general situation when the assumption of over-parametrization is relaxed. We provide sharp estimates for both the empirical and population risks. In particular, we prove that for target functions in the appropriate reproducing kernel Hilbert space (RKHS) , the generalization error can be made small if certain early stopping strategy is adopted for the gradient descent algorithm.

Our results imply that under this setting over-parametrized two-layer neural networks are a lot like the kernel methods: They can always fit any set of random labels, but in order to generalize, the target functions have to be in the right RKHS. This should be compared with the optimal generalization error bounds proved in for regularized models.

The seminal work of presented both numerical and theoretical evidence that over-parametrized neural networks can fit random labels. Building upon earlier work on the non-degeneracy of some Gram matrices , Du et al. went a step further by proving that the GD algorithm can find global minima of the empirical risk for sufficiently over-parametrized two-layer neural networks . This result was extended to multi-layer networks in or a general setting . The related result for infinitely wide neural networks was obtained in . In this paper, we prove a new optimization result (Theorem 3.2) that removes the non-degeneracy assumption of the input data by utilizing the smoothness of the target function. Also the requirement of the network width is significantly relaxed.

The issue of generalization is less clear. established generalization error bounds for solutions produced by the online stochastic gradient descent (SGD) algorithm with early stopping when the target function is in a certain RKHS. Similar results were proved in for the classification problem, in for offline SGD algorithms, and in for GD algorithm. These results are similar to ours, but we do not require the network to be over-parametrized. Moreover, in Theorem 3.3 we show that in this setting neural networks are uniformly close to the random feature models if the network is highly over-parametrized.

More recently in , a generalization bound was derived for GD solutions using a data-dependent norm. This norm is bounded if the target function belongs to the appropriate RKHS. However, their error bounds are not strong enough to rule out the possibility of curse of dimensionality. Indeed the results of the present paper do suggest that curse of dimensionality does occur in their setting (see Theorem 3.4).

provided by a heuristic argument that the GD solutions of a infinitely-wide neural network are captured by the so-called neural tangent kernel. In this paper, we provide a rigorous proof of the non-asymptotic version of the result for the two-layer neural network under weaker conditions.

Preliminaries

We focus on the regression problem with a training data set given by $\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$, i.i.d. samples drawn from a distribution $\rho$, which is assumed fixed but only known through the samples. In this paper, we assume $\|\bm{x}\|_{2}=1$ and $|y|\leq 1$. We are interested in fitting the data by a two-layer neural network:

The ultimate goal is to minimize the population risk defined by

But in practice, we can only work with the following empirical risk

We are interested in analyzing the property of the following gradient descent algorithm: $\Theta_{t+1}=\Theta_{t}-\eta\nabla\hat{\mathcal{R}}_{n}(\Theta_{t}),$ where $\eta$ is the learning rate. For simplicity, we will focus on its continuous version, the gradient descent (GD) dynamics:

2 Assumption on the input data

Throughout this paper, we make the following assumption on the training set.

For the given training set $\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}$, we assume that the smallest eigenvalues of the two kernel matrices defined above are both positive, i.e.

Let $\lambda_{n}=\min\{\lambda_{n}^{a},\lambda_{n}^{b}\}$.

Let $\Lambda_{n}(T_{s})$ denote its $n$-th largest eigenvalue. If $\{\bm{x}_{i}\}_{i=1}^{n}$ are independently drawn from $\pi_{0}$, it was proved in that with high probability $\lambda^{(a)}_{n}\geq\Lambda_{n}(T_{k^{(a)}})/2$ and $\lambda^{(b)}_{n}\geq\Lambda_{n}(T_{k^{(b)}})/2$. Using the similar idea, provided lower bounds for $\lambda^{(b)}_{n}$ based on some geometric discrepancy, which quantifies the uniformity degree of $\{\bm{x}_{i}\}_{i=1}^{n}$. In this paper, we leave $\lambda^{(a)}_{n}>0,\lambda^{(b)}_{n}>0$ as our basic assumption.

3 The random feature model

We introduce the following random feature model as a reference for the two-layer neural network model

This dynamics is relatively simple since it is linear.

Analysis of the over-parameterized case

Since $\hat{\mathcal{R}}_{n}=\frac{1}{2n}\bm{e}^{T}\bm{e}$, we have

For any fixed $\delta>0$, with probability at least $1-\delta$ over the random initialization, we have

where $c(\delta)=2+\sqrt{\ln(1/\delta)}$.

The proof of this lemma can be found in Appendix C.

In addition, at the initialization, the Gram matrices satisfy

For $\delta>0$, if $m\geq\frac{8}{\lambda_{n}^{2}}\ln(2n^{2}/\delta)$, we have, with probability at least $1-\delta$ over the random choice of $\Theta_{0}$

The proof of this lemma is deferred to Appendix D.

2 Gradient descent near the initialization

We define a neighborhood of the initialization by

Using the lemma above, we conclude that for any fixed $\delta>0$, with probability at least $1-\delta$ over the random choices of $\Theta_{0}$, we must have

for all $\Theta\in\mathcal{I}(\Theta_{0})$.

For the GD dynamics, we define the exit time of $\mathcal{I}(\Theta_{0})$ by

For any fixed $\delta\in(0,1)$, assume that $m\geq\frac{8}{\lambda_{n}^{2}}\ln(2n^{2}/\delta)$. Then with probability at least $1-\delta$ over the random choices of $\Theta_{0}$, we have the following holds for any $t\in[0,t_{0}]$,

where the last inequality is due to the fact that $\Theta_{t}\in\mathcal{I}(\Theta_{0})$. This completes the proof. ∎

The following is the most crucial characterization of the GD dynamics.

For any $\delta>0$, assume $m\geq 1024\lambda_{n}^{-2}\ln(n^{2}/\delta)$. Then, with probability at least $1-\delta$, we have the following holds for any $t\in[0,t_{0}]$,

To facilitate the analysis, we define the following two quantities,

Combining the two inequalities above, we get

Using Lemma 1 and the fact that $m\geq\max\{\frac{16}{\lambda^{(a)}_{n}},\frac{64c^{2}(\delta)}{\lambda^{(b)}_{n}\lambda^{(a)}_{n}}\}$, we have

Inserting the above estimates back to (10), we obtain

Since $m\geq\max\{\frac{16}{\sqrt{\lambda^{(a)}_{n}\lambda^{(b)}_{n}}},\frac{1024c^{2}(\delta)}{(\lambda^{(b)}_{n})^{2}}\}$, we have

Therefore we have $\omega_{k}(t)\leq 1+\|\bm{b}_{k}(t)-\bm{b}_{k}(0)\|\leq 2$, which leads to

The following lemma provides that how $p_{n}$ and $q_{n}$ depend on $\beta$ and $m$.

For any $\delta>0$, assume $m\geq 1024\lambda_{n}^{-2}\ln(n^{2}/\delta)$. Let $C(\delta)=10c^{2}(\delta)$. If $\beta\leq 1$, we have

3 Global convergence for arbitrary labels

Proposition 3.1 and Lemma 4 tell us that no matter how large $\beta$ is, we have

This actually implies that the GD dynamics always stays in $\mathcal{I}(\Theta_{0})$, i.e. $t_{0}=\infty$.

For any $\delta\in(0,1)$, assume $m\gtrsim\lambda_{n}^{-4}n^{2}\delta^{-1}\ln(n^{2}/\delta)$. Then with probability at least $1-\delta$ over the random initialization, we have

According to Lemma 3, we only need to prove that $t_{0}=\infty$. Assume $t_{0}<\infty$.

Let us first consider the Gram matrix $G^{(a)}$. Since $\sigma(\cdot)$ is $1-$Lipschitz and $\max_{k}\|\bm{b}_{k}(t_{0})-\bm{b}_{k}(0)\|\leq q_{n}\leq 1$, we have

Next we turn to the Gram matrix $G^{(b)}$. Define the event

Hence using $q_{n}=p_{n}^{2}+\beta p_{n}\leq 1$, we obtain

By the Markov inequality, with probability $1-\delta/n$ we have

Consequently, with probability $1-\delta$ we have

where the last inequality comes from Lemma (4). Taking $m\gtrsim\lambda_{n}^{-4}n^{2}\delta^{-1}\ln(n^{2}/\delta)$, we get

The above result contradicts the definition of $t_{0}$. Therefore $t_{0}=\infty$. ∎

Compared with Proposition 3.1, the above theorem imposes a stronger assumption on the network width: $m\geq\text{poly}(\delta^{-1})$. This is due to the lack of continuity of $\sigma^{\prime}(\cdot)$ when handling $\|G^{(b)}(\Theta_{t_{0}})-G^{(b)}(\Theta_{0})\|_{F}$. If $\sigma^{\prime}(\cdot)$ is continuous, we can get rid of the dependence on $\text{poly}(\delta^{-1})$. In addition, it is also possible to remove this assumption for the case when $\beta=o(1)$, since in this case the Gram matrix $G=G^{(a)}+\beta^{2}G^{(b)}$ is dominated by $G^{(a)}$.

Theorem 3.2 is closely related to the result of Du et al. where exponential convergence to global minima was first proved for over-parametrized two-layer neural networks. But it improves the result of in two aspects. First, as is done in practice, we allow the parameters in both layers to be updated, while chooses to freeze the parameters in the first layer. Secondly, our analysis does not impose any specific requirement on the scale of the initialization whereas the proof of relies on the specific scaling: $\beta\sim 1/\sqrt{m}$.

4 Characterization of the whole GD trajectory

In the last subsection, we showed that very wide networks can fit arbitrary labels. In this subsection, we study the functions represented by such networks. We show that for highly over-parametrized two-layer neural networks, the solution of the GD dynamics is uniformly close to the solution for the random feature model starting from the same initial function.

Assume $\beta\leq 1$. Denote the solution of GD dynamics for the random feature model by

where $c(\delta)=1+\sqrt{\ln(1/\delta)}$.

Again the factor $\delta^{-1}$ in the condition for $m$ can be removed if $\sigma$ is assumed to be smooth or $\beta$ is assumed to be small (see the remark at the end of Theorem 3.2).

If $\beta=o(m^{-1/6})$, the right-hand-side of (18) goes to as $m\rightarrow\infty$. For example, if we take $\beta=1/\sqrt{m}$, we have

Hence this theorem says that the GD trajectory of a very wide network is uniformly close to the GD trajectory of the related kernel method (5).

We are now going to bound $J_{1}(\bm{x},t)$ and $J_{2}(\bm{x},t)$.

We first consider $J_{1}$. By Theorem (3.1), with probability at least $1-\delta$ we have

Hence, by the estimates of $\hat{\mathcal{R}}_{n}(\Theta_{0})$ in Lemma 1, we have

Inserting the estimate of $q_{n}$ in Lemma 4, we get

Consider the initializations for which $\lambda_{\min}(G^{(a)}(\Theta_{0}))\geq\frac{3\lambda^{(a)}_{n}}{4}$. The probability of this event is no less than $1-\delta$. For such initializations, we have

Using Proposition (3.1), we conclude that with probability no less than $1-2\delta$, the following holds:

Together with the fact that $\|\bm{e}(s)\|\leq\sqrt{2n\hat{\mathcal{R}}_{n}(\Theta_{0})}e^{-\frac{m\lambda^{(a)}_{n}}{2}s}$, we obtain

In addition, for any $\bm{x}\in\SS^{d-1}$, we have $\|\bm{g}^{(a)}(\bm{x})\|\leq\frac{1}{m\sqrt{n}}$. Hence, plugging (3.4) into $J_{2}$ leads to

Substituting in the estimates for $q_{n}$ and $\hat{\mathcal{R}}_{n}(\Theta_{0})$, and assuming that $\beta^{2}\leq 1$, we obtain, for any $\delta>0$, with probability no less than $1-3\delta$,

Finally, combining the estimates of $J_{1}$ and $J_{2}$, we conclude that

holds for any $\delta>0$ with probability at least $1-6\delta$. This completes the proof of Theorem 3.3.

5 Curse of dimensionality of the implicit regularization

For any probability distribution $\pi$ over $\SS^{d-1}$, we define

The Barron space is defined as the union of $\mathcal{H}_{\pi}$, i.e.

The Barron norm for any $h\in\mathcal{B}$ is defined by

To signify the dependence on the target function and data set, we introduce the notation:

where the right hand side is the GD solution of the random feature model obtained by using the training data $\{\bm{x}_{i},y_{i}\}_{i=1}^{n}$ with $y_{i}=f(\bm{x}_{i})$ and $\Theta_{0}$ as the initial parameters. Let $\mathcal{B}_{Q}=\{f\in\mathcal{B}\,:\,\|f\|_{\mathcal{B}}\leq Q\}$. We then have the following theorem.

There exists an absolute constant $\kappa>0$, such that for any $t\in[0,+\infty)$

Combined Theorem 3.4 with Theorem 3.3, we conclude that for any $\delta\in(0,1)$, if $m$ is sufficiently large, then with probability at least $1-\delta$ we have

denotes the solution at time $t$ of the GD dynamics for the two-layer neural network model. If $\beta$ is sufficiently small (e.g. $\beta=o(m^{-1/6})$), then we see that the curse of dimensionality also holds for the solutions generated by the GD dynamics for the two-layer neural network model. Since this statement holds for all time $t$, no early-stopping strategy is able to fix this curse of dimensionality problem.

In contrast, it has been proved in that an appropriate regularization can avoid this curse of dimensionality problem, i.e. if we denote by $\mathcal{M}(f,\{\bm{x}_{i}\}_{i=1}^{n})$ the estimator for the regularized model in (see (86) below), then it was shown that for any $\delta>0$, with probability at least $1-\delta$ over the sampling of $\{\bm{x}_{i}\}_{i=1}^{n}$, the following holds

The comparison between (40) and (41) provides a quantitative understanding of the insufficiency of using the random feature model to explain the generalization behavior of neural network models.

To prove Theorem 3.4, we need the following lemma, which is proved in .

As is shown in , any function $f\in\Gamma_{Q}$ can be represented as

for some $\pi$ and $\|f\|_{\mathcal{H}_{\pi}}\leq Q$, which means $f\in\mathcal{B}_{Q}$. Hence, $\Gamma_{Q}\subset\mathcal{B}_{Q}$. Next, since the training data $\{\bm{x}_{i}\}_{i=1}^{n}$ and the initialization are fixed, we have

Analysis of the general case

In this section, we will relax the requirement of the network width. We will make the following assumption on the target function.

We assume that the target function $f^{*}$ admits the following integral representation

with $\gamma(f^{*})\stackrel{{\scriptstyle\text{def}}}{{=}}\max\{1,\sup_{\bm{b}\in\SS^{d-1}}|a^{*}(\bm{b})|\}<\infty$.

The following approximation result is essentially the same as the ones in . Since we are interested in the explicit control for the norm of the solution, we provide a complete proof in Appendix A.

where $\mathcal{R}(\bm{a}^{*},B_{0})=\|f_{m}(\cdot;\bm{a}^{*},B_{0})-f^{*}(\cdot)\|^{2}_{\rho}$ is the population risk.

The following generalization bound for the random feature model will be used later.

For fixed $B_{0}$, and any $\delta>0$, with probability no less than $1-3\delta$ over the choice of the training data, we have

We first show that the gradient descent algorithm can reduce the empirical risk to $\mathcal{O}(\frac{1}{m}+\frac{1}{\sqrt{n}})$. Here we will assume $m\geq n$. This assumption is not used in the next subsection, except for Corollary 4.3.

Take $\beta=\frac{c}{m}$ for some absolute constant $c$. Assume that the target function $f^{*}$ satisfies Assumption 2, and $\|f^{*}\|_{\infty}\leq 1$. Then, for any $\delta\in(0,1)$, with probability no less than $1-4\delta$ we have

for any $t>0$, where $C$ is a constant depending on $\delta$, $\gamma(f^{*})$ and $c$.

The next three lemmas give bounds on the changes of the parameters.

Let $\beta=\frac{c}{m}$, and $T$ be a fixed constant. Then there exists constant $C_{T}$ depending on $T$, such that for any $0\leq t\leq T$,

By the gradient descent dynamics, we have

Since $\|a_{k}(0)\|=\frac{c}{m}$ and $\|\bm{b}_{k}(0)\|=1$, we have

If $t\leq T$, since $\cosh((c+1)t)\leq\frac{e^{(c+1)T}+1}{2}$ and $\sinh((c+1)t)\leq\frac{e^{(c+1)T}+1}{2}t$, we have

with $C_{T}=\frac{e^{(c+1)T}+1}{2}$. Hence, we have

For $\|B_{t}-B_{0}\|$, consider a more refined estimate

Plugging in the above estimate for $a_{k}$, we obtain

Let $\gamma=\gamma(f^{*})$, $\beta=\frac{c}{m}$, and assume $\sqrt{m}\geq\gamma$. Then, for any $\delta>0$, with probability no less than $1-4\delta$, we have for any $0\leq t\leq T$,

By Lemma 6 and Lemma 7, when $\sqrt{m}\geq\gamma$, with probability no less than $1-4\delta$, we have

Under the assumptions of Lemmas 8 and 9, for any $0\leq t\leq T$, we have

Using the estimates in Lemmas 8 and 9, we obtain

Let $\hat{\rho}=\frac{1}{n}\sum_{i=1}^{n}\delta_{\bm{x}_{i}}$, then we have

By Lemma 7, we can bound $I_{2}$ as follows,

For $I_{1}$, consider the Lyapunov function

Combining all the estimates above, we conclude that for any $\delta>0$, with probability larger than $1-4\delta$, we have

For the estimate on $\bm{a}^{*}$, by Lemma 6, we have $\|\bm{a}^{*}\|\leq\frac{\gamma}{\sqrt{m}}$. To bound $\|\bm{a}_{0}-\bm{a}^{*}\|$, we have

Together with the estimates in Lemmas 8, 9 and 10, and without loss of generality assuming that $\gamma\geq 1$, we obtain

If we assume $m\geq n$ and take $t\in[0,\frac{\sqrt{n}}{m}]$, then we can take $T=1$ and obtain

for some constant $C$. Moreover, since $\hat{\mathcal{R}}_{n}(\bm{a}_{t},B_{t})$ is non-increasing, $\hat{\mathcal{R}}_{n}(\bm{a}_{t},B_{t})\leq\hat{\mathcal{R}}_{n}(\bm{a}_{\sqrt{n}/m},B_{\sqrt{n}/m})$. Hence for any $t>\frac{\sqrt{n}}{m}$, we have

for some constant $C$. Combining (73) and (74), we complete the proof for all $t$.

2 Generalization results

The following theorem provides an upper bound for the population error of GD solutions at any time $t\in[0,\infty)$. It tells that one can use early stopping to reach the optimal error in the absence of over-parametrization.

Take $\beta=\frac{c}{m}$ for some constant $c$. Assume that the target function $f^{*}$ satisfies Assumption 2, and $\|f^{*}\|_{\infty}\leq 1$. Fix any positive constant $T$. Then for $\delta>0$, with probability no less than $1-4\delta$ we have, for $t\leq T$

where $C$ is a constant depending only on $T$, $\delta$, $\gamma(f^{*})$ and $c$.

As a consequence, we have the following early-stopping results.

Assume that $m>n$. Let $t=\frac{\sqrt{n}}{m}$. Under the condition of Theorem 4.2, we have

From these results we conclude that for target functions in a certain RKHS, with high probability the gradient descent dynamics can find a solution with good generalization properties in a short time. Compared to the long-term analysis in the last section, this theorem does not require $m$ to be very large. It works in the “mildly over-parameterized” regime.

The following Corollary provides a more detailed study of the balance between $m$, $n$ and $t$ to achieve best rates for $\mathcal{R}(\bm{a}_{t},B_{t})$.

Assume $m=n^{p}$ for some $p\geq 0$. Then, if $p\leq\frac{7}{8}$, take $t=n^{-\frac{3p}{7}}$, we have

If $p>\frac{7}{8}$, take $t=n^{-p+\frac{1}{2}}$, we have

Let $m=n^{p}$ and $t=n^{r}$. We assume $r\leq 0$, then

Expand the right hand side of (75), we obtain

For each $p\geq 0$, we are going to find the corresponding $r$ for which the maximum value among all the terms at the right hand side of (80) is minimized. When $r=-p$, we have $-r-p=0$. Thus the second term is larger than any other terms. Hence, we only have to consider the case when $-p\leq r\leq 0$. In this interval, we only need to compare the terms with powers $-r-p$, $r+p-1$, $6r+2p$ and $7r+3p-\frac{1}{2}$ and neglect all other terms. The desired results are then obtained by comparing the second term with the other three terms. ∎

The right hand side of (82) has one more term than (66), and additional term can be bounded as

Hence, for any $\delta>0$, with probability larger than $1-4\delta$, we have

Numerical experiments

In this section, we present some numerical results to illustrate our theoretical analysis.

The first experiment studies the convergence of GD dynamics for over-parametrized two-layer neural networks with different initializations. We uniformly sample $\{\bm{x}_{i}\}_{i=1}^{n}$ from $\SS^{d-1}$, and for each $\bm{x}_{i}$ we specify a label $y_{i}$, which is uniformly drawn from $$. In the experiments, we choose$n=50,d=50$, and network width$m=10,000\gg n$. Six initializations of different magnitudes are tested. Figure 1 shows the training curves.

We see that the GD algorithm for the neural network models converges exponentially fast for all initializations considered, even for the case when $\beta=m$. This is consistent with the results of Theorem 3.2.

2 Learning the one-neuron function

We first choose $n=50,d=10$ to build the training set, and then use the gradient descent algorithm with learning rate $\eta=0.01$ to train two-layer neural network and random feature models. We initialize the models using $\beta=0$. In addition, $10^{4}$ new samples are drawn to evaluate the test error. Figure 2 shows the training and test error curves of the two models of three widths: $m=4,50,1000$. We see that, when the width is very small, the GD algorithm for the random feature model does not converge, while it does converge for the neural network model and the resulting model does generalize. This is likely due to the special target function we have chosen here. For the intermediate width ($m=50$), the GD algorithm for both models converges, and it converges faster for the neural network model than for the random feature model. The test accuracy is slightly better for the resulting neural network model (but not as good as for the case when $m=4$). When $m=1000$, the behavior of the GD algorithm for two models is almost the same.

Finally, we study the generalization properties of neural network models of different width. We train two-layer neural networks of different width until the training error is below $10^{-5}$. Then we measure the test error. We compare the test error with that of the regularized model proposed in :

The results are showed in Figure 3. One sees that when the width is small, the test error is small for both methods. However, when the width becomes very large, the un-regularized neural network model does not generalized well. In other words, implicit regularization fails.

The above results are consistent with the theoretical lower bound (40), which states that learning with GD suffers from the curse of dimensionality for functions in Barron space. Here the one-neuron function serves as a specific example. Intuitively, the one-neuron target function $f^{*}(x)=\sigma((\bm{w}^{*})^{T}\bm{x})$ only relies on the specific direction $\bm{w}^{*}$. However the basis $\{\sigma(\bm{w}^{T}\bm{x})\}_{j=1}^{m}$ are uniformly drawn from $\SS^{d-1}$. In high dimension, we know $\langle\bm{w}_{j},\bm{w}^{*}\rangle\approx 0$ for any $\bm{w}_{j}$ uniformly drawn from $\SS^{d-1}$. Therefore, it is not surprising to see that learning with uniform features suffers from the curse of dimensionality.

Conclusion

To put things into perspective, let us first recall some results from .

One can define a space of functions called the Barron space. The Barron space is the union of all RKHS with kernels defined by

with respect to all probability distributions $\pi$.

For regularized models with a suitably crafted regularization term, optimal generalization error estimates (i.e. rates that are comparable to the Monte Carlo rates) can be established for all target functions in the Barron space.

In the present paper, we have shown that for over-parametrized two-layer neural networks without explicit regularization, the gradient descent algorithm is sufficient for the purpose of optimization. But to obtain dimension-independent error rates for generalization, one has to require that the target function be in the RKHS with a kernel defined by the initialization. In other words, given a target function in the Barron space, in order for implicit regularization to work, one has to know beforehand the kernel function for that target function and use that kernel function to initialize the GD algorithm. This requirement is certainly impractical. In the absence of such a knowledge, one should expect to encounter the curse of dimensionality for general target functions in Barron space, as is proved in this paper.

We have also studied the case with general network width. Our results point to the same direction as for the over-parametrized regime although in the general case, one has to rely on early stopping to obtain good generalization error bounds. Our analysis does not rule out completely the possibility that in some scaling regimes of $n,m,t$, the GD algorithm for two-layer neural network models may have better generalization properties than that of the related kernel method.

From a technical viewpoint, our analysis was facilitated greatly by the fact that the dynamics of the $\bm{b}$’s is much slower than that of the $\bm{a}$’s, as a consequence of the smallness of $\beta$. As a result, the $\bm{b}$’s are effectively frozen in the GD dynamics. While this is the same setup as the ones used in practice, one can also imagine putting out an explicit scaling factor to account for the smallness of $\beta$, e.g.

as in . In this case, the separation of time scales is no longer valid and one can potentially obtain a very different picture. While this is certainly an interesting avenue to pursue, so far there are no results concerning the effect of implicit regularization in such a setting.

Acknowledgement: The work presented here is supported in part by a gift to Princeton University from iFlytek and the ONR grant N00014-13-1-0338.

References

Appendix A Proof of Lemma 6

For any $B_{0}$, let $\bm{a}^{*}(B_{0})=\{a^{*}(\bm{b}_{k}^{0})/m\}_{k=1}^{m}$, where $a^{*}$ is the function defined in Assumption 2. Let

Hence, by McDiarmid’s inequality, for any $\delta>0$, with probability no less than $1-\delta$, we have

Finally, by Assumption 2, $\|\bm{a}^{*}\|\leq\frac{\gamma}{\sqrt{m}}$. ∎

Appendix B Proof of Lemma 7

For any $Q>0$, let $\mathcal{F}_{Q}=\{f(\cdot;\bm{a},B_{0}):\ \|\bm{a}\|\leq Q\}$. We can bound the Rademacher complexity of $\mathcal{F}_{Q}$ as follows.

Next, let $\mathcal{H}_{Q}=\{(f(\cdot;\bm{a},B_{0})-f^{*})^{2}:\ \|\bm{a}\|\leq Q\}$. Since $|f^{*}(\bm{x})|\leq 1$ for any $\bm{x}$, by the Cauchy-Schwartz inequality, $|f(\bm{x};\bm{a},B_{0})|\leq\sqrt{m}Q$. Hence we can bound the Rademacher complexity of $\mathcal{H}_{Q}$ by

using that $(f(\cdot;\bm{a},B_{0})-f^{*})^{2}$ is Lipschitz continuous with Lipschitz constant bounded by $2\sqrt{m}Q+1$. Therefore, for any $\delta>0$, with probability larger than $1-\delta$, we have

for any $\bm{a}$ with $\|\bm{a}\|\leq Q$.

Finally, for any integer $k$, let $Q_{k}=2^{k}$ and $\delta_{k}=2^{-|k|}\delta$. Then, with probability larger than

Appendix C Proof of Lemma 1

Define $\mathcal{F}=\{h(a,\bm{b})=a\sigma(\bm{b}^{T}\bm{x})\,:\,\|\bm{x}\|\leq 1\}$. By the standard Rademacher complexity bound (see Theorem 26.5 of ), we have, with probability at least $1-\delta$,

Moreover, since $\phi_{k}(\cdot)\stackrel{{\scriptstyle\text{def}}}{{=}}a_{k}\sigma(\cdot)$ is $\beta-$Lipschitz continuous, by applying the contraction property of Rademacher complexity (see Lemma 26.9 of ) we have

where the last inequality follows from the Lemma 26.10 of . Thus with probability $1-\delta$, we have that for any $\|\bm{x}\|=1$,

Thus $\hat{\mathcal{R}}_{n}(\Theta_{0})\leq\frac{1}{2n}\sum_{i=1}^{n}(1+|f(\bm{x}_{i};\Theta_{0})|)^{2}\leq\frac{1}{2}(1+\sqrt{m}\beta(2+\sqrt{\ln(1/\delta)}))^{2}$. ∎

Appendix D Proof of Lemma 2

For a given $\varepsilon\geq 0$, define events

Thus with probability at least $(1-e^{-2m\varepsilon^{2}})^{2n^{2}}\geq 1-2n^{2}e^{-2m\varepsilon^{2}}$, we have

Taking $\varepsilon=\lambda_{n}/4$, we complete the proof. ∎