A Priori Estimates of the Population Risk for Two-layer Neural Networks

Introduction

One of the main challenges in theoretical machine learning is to understand the errors in neural network models . To this end, it is useful to draw an analogy with classical approximation theory and finite element analysis . There are two kinds of error bounds in finite element analysis depending on whether the target solution (the ground truth) or the numerical solution enters into the bounds. Let $f^{*}$ and $\hat{f}_{n}$ be the true solution and the “numerical solution”, respectively. “A priori” error estimates usually take the form

where only norms of the true solution enter into the bounds. In “a posteriori” error estimates, the norms of the numerical solution enter into the bounds:

Here $\|\cdot\|_{1},\|\cdot\|_{2},\|\cdot\|_{3}$ denote various norms. In this language, most recent theoretical results on estimating the generalization error of neural networks should be viewed as “a posteriori” analysis, since the bounds depend on various norms of the neural network model obtained after the training process. As was observed in , the numerical values of these norms are very large, yielding vacuous bounds. For example, calculated the values of various a posteriori bounds for some real two-layer neural networks and it is found that the best bounds are still on the order of $O(10^{5})$.

In this paper, we pursue a different line of attack by providing “a priori” analysis. Specifically, we focus on two-layer networks, and we consider models with explicit regularization. We establish estimates for the population risk which are asymptotically sharp with constants depending only on the properties of the target function. Our numerical results suggest that such regularization terms are necessary in order for the model to be “well-posed” (see Section 7 for the precise meaning).

Specifically, our main contributions are:

We establish a priori estimates of the population risk for learning two-layer neural networks with an explicit regularization. These a priori estimates depend on the Barron norm of the target function. The rates with respect to the number of parameters and number of samples are comparable to the Monte Carlo rate. In addition, our estimates hold for high dimensional and over-parametrized regime.

We make a comparison between the neural network and kernel methods using these a priori estimates. We show that two-layer neural networks can be understood as kernel methods with the kernel adaptively selected from the data. This understanding partially explains why neural networks perform better than kernel methods in practice.

The present paper is the first in a series of papers in which we analyze neural network models using a classical numerical analysis perspective. Subsequent papers will consider deep neural network models , the optimization and implicit regularization problem using gradient descent dynamics and the general function spaces and approximation theory in high dimensions .

Related work

There are two key problems in learning two-layer neural networks: optimization and generalization. Recent progresses on optimization suggest that over-parametrization is the key factor leading to a nice empirical landscape $\hat{L}_{n}$ , thus facilitating convergence towards global minima of $\hat{L}_{n}$ for gradient-based optimizers . This leaves the generalization property of learning two-layer neural networks more puzzling, since naive arguments would suggest that more parameters implies worse generalization ability. This contradicts what is observed in practice. In what follows, we survey previous attempts in analyzing the generalization properties of two-layer neural network models.

This line of works studies the generalization property of two-layer neural networks with explicit regularization and our work lies in this category. Let $n,m$ denote the number of samples and number of parameters, respectively. For two-layer sigmoidal networks, established a risk bound $O(1/m+md\ln(n)/n)$. By considering smoother activation functions, proved another bound $O((\ln d/n)^{1/3})$ for the case when $m\approx\sqrt{n}$. Both of these results are proved for a regularized estimator. In comparison, the error rate established in this paper, $O(1/m+\ln n\sqrt{\ln d/n})$ is sharper and in fact nearly optimal, and it is also applicable for the over-parametrized regime. For a better comparison, please refer to Table 1.

More recently, considered explicit regularization for classification problems. They proved that for the specific cross-entropy loss, the regularization path converges to the maximum margin solutions. They also proved an a priori bound on how the network size affects the margin. However, their analysis is restricted to the case where the data is well-separated. Our result does not have this restriction.

2 Implicit regularization

Another line of works study how gradient descent (GD) and stochastic gradient descent (SGD) finds the generalizable solutions. proved that SGD learns over-parametrized networks that provably generalize for binary classification problem. However, it is not clear how the population risk depends on the number of samples for their compression-based generalization bound. Moreover, their proof highly relies on the strong assumption that the data is linearly separable. The experiments in suggest that increasing the network width can improve the test accuracy of solutions found by SGD. They tried to explain this phenomena by an initialization-dependent (a posterior) generalization bound. However, in their experiments, the largest width $m\approx n$, rather than $m\gg n$. Furthermore their generalization bounds are arbitrarily loose in practice. So their result cannot tell us whether GD can find generalizable solutions for arbitrarily wide networks.

Recent work in has shown clearly that for the kind of initialization schemes considered in these previous works or in the over-parametrized regime, the neural network models do not perform better than the corresponding kernel method with a kernel defined by the initialization. These results do not rule out the possibility that neural network models can still outperform kernel methods in some regimes, but they do show that finding these regimes is quite non-trivial.

Preliminaries

We begin by recalling the basics of two-layer neural networks and their approximation properties.

The two-layer neural network is defined by

The ultimate goal is to minimize the population risk

In practice, we have to work with the empirical risk

We will consider the regularized model defined as follows:

For a two-layer neural network $f(\cdot;\theta)$ of width $m$, we define the regularized risk as

The $+1$ term at the right hand side is included only to simplify the proof. Our result also holds if we do not include this term in the regularized risk. The corresponding regularized estimator is defined as

Here $\lambda>0$ is a tuning parameter that controls the balance between the fitting error and the model complexity. It is worth noting that the minimizer is not necessarily unique, and $\hat{\theta}_{n,\lambda}$ should be understood as any of the minimizers.

In the following, we will call Lipschitz continuous functions with Lipschitz constant $C$ $C$-Lipschitz continuous. We will use $X\lesssim Y$ to indicate that $X\leq cY$ for some universal constant $c>0$.

We begin by defining the natural function space associated with two-layer neural networks, which we will refer to as the Barron space to honor the pioneering work that Barron has done on this subject . A more complete discussion can be found in .

Let $\SS^{d}:=\{w\,|\,\|w\|_{1}=1\}$, and let $\mathcal{F}$ be the Borel $\sigma$-algebra on $\SS^{d}$ and $P(\SS^{d})$ be the collection of all probability measures on $(\SS^{d},\mathcal{F})$. Let $\mathcal{B}(X)$ be the collection of functions that admit the following integral representation:

where $\pi\in P(\SS^{d})$, and $a(\cdot)$ is a measurable function with respect to $(\SS^{d},\mathcal{F})$. For any $f\in\mathcal{B}(X)$ and $p\geq 1$, we define the following norm

Since $\pi(\cdot)$ is a probability distribution, by Hölder’s inequality, for any $q\geq p>0$ we have $\gamma_{p}(f)\leq\gamma_{q}(f).$ Thus, we have $\mathcal{B}_{\infty}(X)\subset\cdots\subset\mathcal{B}_{2}(X)\subset\mathcal{B}_{1}(X)$.

Obviously $\mathcal{B}_{p}(X)$ is dense in $C(X)$ since all the finite two-layer neural networks belong to Barron space with $\pi(w)=\frac{1}{m}\sum_{k=1}^{m}\delta(w-\hat{w}_{k})$ and the universal approximation theorem tells us that continuous functions can be approximated by two-layer neural networks. Moreover, it is interesting to note that the $\gamma_{1}(\cdot)$ norm of a two-layer neural network is bounded by the path norm of the parameters.

Thus it lies in $\mathcal{B}_{\infty}(X)$.

The Barron space has a natural connection with reproducing kernel Hilbert space (RKHS) , and as we will show later, this connection will lead to a precise comparison between two-layer neural networks and kernel methods. For a fixed $\pi$, we define

Thus Barron space can be viewed as the union of a family of RKHS with kernels defined by $\pi$ through Equation (3.5), i.e.

Note that the family of kernels is only determined by the activation function $\sigma(\cdot)$.

2 Approximation property

This kind of approximation results have been established in many papers, see for example . The difference is that we provide the explicit control of the norm of the constructed solution in (3.8), and the bound is independent of the network size. This observation will be useful for what follows.

The proof of Proposition 3.3 can be found in Appendix A. The basic intuition is that the integral representation of $f$ allows us to approximate $f$ by the Monte-Carlo method: $f(x)\approx\frac{1}{m}\sum_{k=1}^{m}a(w_{k})\sigma(\langle w_{k},x\rangle)$ where $\{w_{k}\}_{k=1}^{m}$ are sampled from the distribution $\pi$.

Main results

For simplicity we first discuss the case without noise, i.e. $\xi=0$. In the next section, we deal with the noise. We also assume $\ln(2d)\geq 1$, and let $\hat{\gamma}_{p}(f)=\max\{1,\gamma_{p}(f)\},\lambda_{n}=4\sqrt{2\ln(2d)/n}$. Here $d$ is the dimension of input and the definition of $\gamma_{p}(\cdot)$ is given in Equation (3.4).

Assume that the target function $f^{*}\in\mathcal{B}_{2}(X)$ and $\lambda\geq\lambda_{n}$. Then for any $\delta>0$, with probability at least $1-\delta$ over the choice of the training set $S$, we have

The above theorem provides an a priori estimate for the population risk. The a priori nature is reflected by dependence of the $\gamma_{2}(\cdot)$ norm of the target function. The first term at the right hand side controls the approximation error. The second term bounds the estimation error. Surprisingly, the bound for the estimation error is independent of the network width $m$. Hence the bound also makes sense in the over-parametrization regime.

In particular, if we take $\lambda\asymp\lambda_{n}$ and $m\geq\sqrt{n}$, the bound becomes $O(1/\sqrt{n})$ up to some logarithmic terms. This bound is nearly optimal in a minimax sense .

Let $\hat{h}_{n,\lambda}$ be the solution of the kernel ridge regression (KRR) problem defined by:

If $\|f^{*}\|_{\mathcal{H}_{\pi_{0}}}<\infty$, then we have $f^{*}\in\mathcal{H}_{\pi_{0}}$ and $\inf_{h\in\mathcal{H}_{\pi_{0}}}L(h)=0$. In this case, it was proved in that the optimal learning rate is

Compared to Theorem 4.1, we can see that both rates have the same scaling with respect to $n$, the number of samples. The only difference appears in the two norms: $\gamma_{2}(f^{*})$ and $\|f^{*}\|_{\mathcal{H}_{\pi_{0}}}$. From the definition (3.4), we always have $\gamma_{2}(f^{*})\leq\|f^{*}\|_{\mathcal{H}_{\pi_{0}}}$, since $(a^{*}\frac{d\pi^{*}}{d\pi_{0}},\pi_{0})\in\Theta_{f^{*}}$. If $\pi^{*}$ is nearly singular with respect to $\pi_{0}$, then $\|f^{*}\|_{\mathcal{H}_{\pi_{0}}}\gg\gamma_{2}(f^{*})$. In this case, the population risk for the kernel methods should be much larger than the population risk for the neural network model.

Take $\pi_{0}$ to be the uniform distribution over $\SS^{d}$ and $f^{*}(x)=\sigma(\langle w^{*},x\rangle)$, for which $\pi^{*}(w)=\delta(w-w^{*})$ and $a^{*}(w)=1$. In this case $\gamma_{2}(f^{*})=1$, but $\|f^{*}\|_{\mathcal{H}_{\pi_{0}}}=+\infty$. Thus the rate (4.13) becomes trivial. Assume that the population risk scales as $O(n^{-\beta})$, and it is interesting to see how $\beta$ depends on the dimension $d$. We numerically estimate $\beta$’s for two methods, and report the results in Table 2. It does show that the higher the dimensionality, the slower the rate of the kernel method. In contrast, the rates for the two-layer neural networks are independent of the dimensionality, which confirms the the prediction of Theorem 4.1. For this particular target function, the value of $\beta\geq 1$ is bigger than the lower bound ($1/2$) proved in Theorem 4.1. This is not a contradiction since the latter holds for any $f\in\mathcal{B}_{2}(X)$.

The two-layer neural network model as of an adaptive kernel method

Recall that $\mathcal{B}_{2}(X)=\cup_{\pi}\mathcal{H}_{\pi}(X)$. The norm $\gamma_{2}(\cdot)$ characterizes the complexity of the target function by selecting the best kernel among a family of kernels $\{k_{\pi}(\cdot,\cdot)\}_{\pi\in P(\SS^{d})}$. The kernel method works with a specific RKHS with a particular choice of the kernel or the probability distribution $\pi$. In contrast, the neural network models work with the union of all these RKHS and select the kernel or the probability distribution adapted to the data. From this perspective, we can view the two-layer neural network model as an adaptive kernel method.

2 Tackling the noise

We first make the following sub-Gaussian assumption on the noise. {assumption} We assume that the noise satisfies

Here $c_{0},\tau_{0}$ and $\sigma$ are constants.

In the presence of noise, the population risk can be decomposed into

Let $B_{n}=1+\max\{\tau_{0},\sigma^{2}\ln n\}$. For the noisy case, we consider the following regularized risk:

The corresponding regularized estimator is given by $\hat{\theta}_{n,\lambda}=\operatorname{argmin}J_{\lambda}(\theta).$ Here for simplicity we slightly abused the notation.

Assume that the target function $f^{*}\in\mathcal{B}_{2}(X)$ and $\lambda\geq\lambda_{n}$. Then for any $\delta>0$, with probability at least $1-\delta$ over the choice of the training set $S$, we have

Compared to Theorem 4.1, the noise introduces at most several logarithmic terms. The case with no noise corresponds to the situation with $B_{n}=1$.

3 Extension to classification problems

Under the same assumption as in Theorem 4.2 and taking $\lambda=\lambda_{n}$, for any $\delta\in(0,1)$, with probability at least $1-\delta$, we have

According to the Theorem 2.2. of , we have

In this case, $\varepsilon_{i}=y_{i}-f^{*}(x_{i})$ is bounded by $1$, thus $\tau_{0}=1,c=\sigma=0$. Applying Theorem 4.2 yields the result.

Proofs

The generalization gap can be estimated via the Rademacher complexity by the following theorem .

Fix a hypothesis space $\mathcal{F}$. Assume that for any $f\in\mathcal{F}$ and $z$, $|f(z)|\leq B$. Then for any $\delta>0$, with probability at least $1-\delta$ over the choice of $S=(z_{1},z_{2},\dots,z_{n})$, we have,

Let $\mathcal{F}_{Q}=\{f(x;\theta)\,|\,\|\theta\|_{\mathcal{P}}\leq Q\}$ denote all the two-layer networks with path norm bounded by $Q$. It was proved in that

By combining the above result withTheorem 5.2, we obtain the following a posterior bound of the generalization gap for two-layer neural networks. The proof is deferred to Appendix B.

We see that the generalization gap is bounded roughly by $\|\theta\|_{\mathcal{P}}/\sqrt{n}$ up to some logarithmic terms.

2 Proof for the noiseless case

The last term can be simplified by using $\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$ and $\ln(1+a)\leq a$ for $a\geq 0,b\geq 0$. So we have

Plugging it into Equation (5.5) completes the proof.

The regularized estimator $\hat{\theta}_{n,\lambda}$ satisfies:

The first claim follows from the definition of $\hat{\theta}_{n}$. For the second claim, note that

Applying Proposition 5.4 completes the proof.

(Proof of Theorem 4.1) Now we are ready to prove the main result. Following the a posteriori generalization bound given in Theorem 5.3, we have with probability at least $1-\delta$,

Thus after some simplification, we obtain

By combining Equation (5.21) and (5.23), we obtain

3 Proof for the noisy case

We need the following lemma. The proof is deferred to Appendix D.

This suggests that as long as we can bound the truncated population risk, the original risk will be bounded accordingly.

Following the proof of Theorem 4.1, we have

Plugging (5.24) and (5.25) into (5.26), we get

Using Lemma 5.10 and the decomposition (4.15), we complete the proof.

Numerical Experiments

In this section, we evaluate the regularized model using numerical experiments. We consider two datasets, MNISThttp://yann.lecun.com/exdb/mnist/ and CIFAR-10https://www.cs.toronto.edu/~kriz/cifar.html. Each example in MNIST is a $28\times 28$ grayscale image, while each example in CIFAR-10 is a $32\times 32\times 3$ color image. For MNIST, we map numbers $\{0,1,2,3,4\}$ to label and $\{5,6,7,8,9\}$ to $1$. For CIFAR-10, we select the examples with labels and $1$ to construct our new training and validation sets. Thus, our new MNIST has $60,000$ training examples, and CIFAR-10 has $10,000$ training examples.

The two-layer ReLU network is initialized using $a_{i}\sim\mathcal{N}(0,\frac{2\kappa}{m}),\,w_{i,j}\sim\mathcal{N}(0,2\kappa/d)$. We use $\kappa=1$ and train the regularized models using the Adam optimizer for $T=10,000$ steps, unless it is specified otherwise. The initial learning rate is set to be $0.001$, and it is then multiplied by a decay factor of $0.1$ at $0.7T$ and again at $0.9T$. We set the trade-off parameter $\lambda=0.1\lambda_{n}$Our proof of theoretical results require $\lambda\geq\lambda_{n}$. However, this condition is not necessarily optimal. .

Theorem 5.3 shows that the generalization gap is bounded by $\frac{\|\theta\|_{\mathcal{P}}}{\sqrt{n}}$ up to some logarithmic terms. Previous works showed that (stochastic) gradient descent tends to find solutions with huge norms, causing the a posterior bound to be vacuous. In contrast, our theory suggests there exist good solutions (i.e. solutions with small generalization error) with small norms, and these solutions can be found by the explicit regularization.

To see how this works in practice, we trained both the regularized models and un-regularized models ($\lambda=0$) for fixed network width $m=$10,000. To cover the over-parametrized regime, we also consider the case $n=100$ where $m/n=100\gg 1$. The results are summarized in Table 3.

As we can see, the test accuracies of the regularized and un-regularized solutions are generally comparable, but the values of $\frac{\|\theta\|_{\mathcal{P}}}{\sqrt{n}}$, which serve as an upper bound for the generalization gap, are drastically different. The bounds for the un-regularized models are always vacuous, as was observed in . In contrast, the bounds for the regularized models are always several orders of magnitude smaller than that for the un-regularized models. This is consistent with the theoretical prediction in Proposition 5.6.

To further explore the impact of over-parametrization, we trained various models with different widths. For both datasets, all the training examples are used. In Figure 1, we display how the value of $\frac{\|\theta\|_{\mathcal{P}}}{\sqrt{n}}$ of the learned solution varies with the network width. We find that for the un-regularized model this quantity increases with network width, whereas for the regularized model it is almost constant. This is consistent with our theoretical result.

2 Dependence on the Initialization

Since the neural network model is non-convex, it is interesting to see how initialization affects the performance of the different models, regularized and un-regularized, especially in the over-parametrized regime. To this end, we fix $m=10000,n=100$ and vary the variance of random initialization $\kappa$. The results are reported in Figure 2. In general, we find that regularized models are much more stable than the un-regularized models. For large initialization, the regularized model always performs significantly better.

Conclusion

In this paper, we proved nearly optimal a priori estimates of the population risk for learning two-layer neural networks. Our results also give some insight regarding the advantage of neural network models over the kernel method. We should also mention that the main result of this paper has also been extended to deep residual network models in .

The most unsatisfactory aspect of our result is that it is proved for the regularized model since practitioners rely on the so-called implicit regularization. At the moment it is unclear where the “implicit regularization” comes from and how it actually works. Existing works consider special initialization schemes and require strong assumptions on the target function . In particular, the work in demonstrates clearly that in the regimes considered the neural network models are no better than the kernel method in terms of implicit regularization. This is quite unsatisfactory.

There are overwhelming evidence that by tuning the optimization procedure, including the algorithm, the initialization, the hyper-parameters, etc., one can find solutions with superior performance on the test data. The problem is that excessive tuning and serious experience is required to find good solutions. Until we have a good understanding about the mysteries surrounding implicit regularization, the business of parameter tuning for un-regularized models will remain an art. In contrast, the regularized model proposed here is rather robust and much more fool-proof. Borrowing the terminology from mathematical physics, one is tempted to say that the regularized model considered here is “well-posed” whereas the un-regularized model is “ill-posed” .

Appendix A Proof of Theorem 3.3

Define the event $E_{1}=\{L_{U}<\frac{3\gamma_{2}^{2}(f)}{m}\}$, and $E_{2}=\{A_{U}<2\gamma_{1}(f)\}$. By Markov’s inequality, we have

Therefore, we have the probability of two events happens together,

Appendix B Proof of Theorem 5.3

Before we provide the upper bound for the Rademacher complexity of two-layer networks, we first need the following two lemmas.

We are now ready to estimate the Rademacher complexity of two-layer networks.

Let $\mathcal{F}_{Q}=\{f_{m}(x;\theta)\,|\,\|\theta\|_{\mathcal{P}}\leq Q\}$ be the set of two-layer networks with path norm bounded by $Q$, then we have

To simplify the proof, we let $c_{k}=0$, otherwise we can define $w_{k}=(w_{k}^{T},c_{k})^{T}$ and $\mathbf{x}=(\mathbf{x}^{T},1)^{T}$.

Since $\sigma$ is Lipschitz continuous with Lipschitz constant $1$, by applying Lemma B.2 and Lemma B.1, we obtain

(Proof of Theorem 5.3) Consider the decomposition $\mathcal{F}=\cup_{l=1}^{\infty}\mathcal{F}_{l}$, where $\mathcal{F}_{l}=\{f_{m}(\mathbf{x};\theta)\,|\,\|\theta\|_{\mathcal{P}}\leq l\}$. Let $\delta_{l}=\frac{\delta}{c\,l^{2}}$ where $c=\sum_{l=1}^{\infty}\frac{1}{l^{2}}$. According to Theorem B.5, if we fix $l$ in advance, then with probability at least $1-\delta_{l}$ over the choice of $S$, we have

So the probability that there exists at least one $l$ such that (2.28) fails is at most $\sum_{l=1}^{\infty}\delta_{l}=\delta$. In other words, with probability at least $1-\delta$, the inequality (2.28) holds for all $l$.

Given an arbitrary set of parameters $\theta$, denote $l_{0}=\min\{l\,|\,\|\theta\|_{\mathcal{P}}\leq l\}$, then $l_{0}\leq\|\theta\|_{\mathcal{P}}+1$. Equation (2.28) implies that

Appendix C Proof of Lemma 5.10

Let $Z=f(x;\theta)-f^{*}(x)-\varepsilon$, then for any $B\geq 2+\tau_{0}$, we have

Since $B_{n}\geq\sigma^{2}\ln n$, we have $2c_{0}\sigma^{2}e^{-\frac{B^{2}_{n}}{2\sigma^{2}}}\leq 2c_{0}\sigma^{2}n^{-1/2}$. We thus complete the proof.

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