The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training

Introduction

Tractability and generalization are two key problems in statistical learning. Classically, tractability is achieved by crafting suitable convex objectives, and generalization by regularizing (or restricting) the function class of interest to guarantee uniform convergence. In modern neural networks, a different mechanism appears to be often at work [NTS15, ZBH+16, BHMM19]. Empirical risk minimization becomes tractable despite non-convexity because the model is overparametrized. In fact, so overparametrized that a model interpolating perfectly the training set is found in the neighborhood of most initializations. Despite this, the resulting model generalizes well to unseen data: the inductive bias produced by gradient-based algorithms is sufficient to select models that generalize well.

Elements of this picture have been rigorously established in special regimes. In particular, it is known that for neural networks with a sufficiently large number of neurons, gradient descent converges quickly to a model with vanishing training error [DZPS18, AZLS19, OS20]. In a parallel research direction, the generalization properties of several examples of interpolating models have been studied in detail [BLLT20, LR20, HMRT19, BHX19, MM21, MRSY19]. The present paper continues along the last direction, by studying the generalization properties of linear interpolating models that arise from the analysis of neural networks.

In this context, many fundamental questions remain challenging. (We refer to Section 4 for pointers to recent progress on these questions.)

When is a neural network sufficiently complex to interpolate $n$ data points? Counting degrees of freedom would suggest that this happens as soon as the number of parameters in the network is larger than $n$. Does this lower bound predict the correct threshold? What are the architectures that achieve this lower bound?

Assume that the answer to the previous question is positive, namely a network with the order of $n$ parameters can interpolate $n$ data points. Can such a network be found efficiently, using standard gradient descent (GD) or stochastic gradient descent (SGD)?

Can we characterize the generalization error above this interpolation threshold? Does it decrease with the number of parameters? What is the nature of the implicit regularization and of the resulting model \widehat{f}(\text{\boldmathx})?

Here we address these questions by studying a class of linear models known as ‘neural tangent’ models. Our focus will be on characterizing test error and generalization, i.e., on the last question Q3, but our results are also relevant to Q1 and Q2.

A substantial literature [DZPS18, AZLS19, ZCZG20, OS20, LZB20] shows that, under certain training schemes, multi-layer neural networks can be well approximated by linear models with a nonlinear (randomized) featurization map that depends on the network architecture and its initialization. In this paper, we will focus on the simplest such models. Given a set of weights \text{\boldmathW}=(\text{\boldmathw}_{1},\dots,\text{\boldmathw}_{N}), we define the following function class with $Nd$ parameters \text{\boldmatha}:=(\text{\boldmatha}_{1},\dots,\text{\boldmatha}_{N}):

While our focus is not on establishing or expanding the connection between neural networks and neural tangent models, Section 5 discusses the relation between model (1) and two-layer networks, mainly based on [COB19, BMR21]. We also emphasize that the model (1) is the neural tangent model corresponding to a two-layer network in which only first-layer weights are trained. If second-layer weights were trained as well, this model would have to be slightly modified (see Section 5). However, our proofs and results would remain essentially unchanged at the cost of substantial notational burden. The reason is intuitively clear: in large dimensions, the number of second layer weights $N$ is negligible compared to the number of first-layer weights $Nd$.

Finding such an interpolator amounts to solving the $n$ linear equations f(\text{\boldmathx}_{i};\text{\boldmatha})=y_{i}, $i\leq n$ in the $Nd$ unknowns \text{\boldmatha}_{1},\dots,\text{\boldmatha}_{N}, which parametrize \mathcal{F}^{N}_{{\sf NT}}(\text{\boldmathW}), cf. Eq. (1). Hence the function $f$ can be found efficiently, e.g. via gradient descent with respect to the square loss.

In order to prove the previous upper bound on the interpolation threshold, we show that the linear system f(\text{\boldmathx}_{i};\text{\boldmatha})=y_{i}, $i\leq n$ has full row rank provided $Nd/(\log Nd)^{C}\geq n$. In fact, our proof provides quantitative control on the eigenstructure of the associated empirical kernel matrix.

The rest of the paper is organized as follows. In the next section, we illustrate our results through some simple numerical simulations. We formally present our main results in Section 3. We state our characterization of the NT kernel, and of the generalization error of NT regression. In Section 4, we briefly overview related work on interpolation and generalization of neural networks. We discuss the connection between GD-trained neural networks and neural tangent models in Section 5. Section 6 provides some technical background on orthogonal polynomials, which is useful for the proofs. The proofs of the main theorems are outlined in Sections 7 and 8, with most technical work deferred to the appendices.

Two numerical illustrations

From Figure 1, we observe that $(1)$ the minimum eigenvalue of the kernel becomes strictly positive very sharply as soon as $Nd/n\gtrsim 1$, $(2)$ as a consequence, the train error vanishes sharply as $Nd/n$ crosses $1$. Both phenomena are captured by our theorems in the next section, although we require the condition $Nd/(\log Nd)^{C}\geq n$ which is suboptimal by a polylogarithmic factor.

From Figure 2, we make the following observations and remarks.

The number of samples $n$ and the number of parameters $Nd$ play a strikingly symmetric role. The test error is large when $Nd\approx n$ (the interpolation threshold) and decreases rapidly when either $Nd$ or $n$ increases (i.e. moving either along horizontal or vertical lines). In the context of random features model, a form of this symmetry property was established rigorously in [MMM21]. For the present work, we only focus on the overparametrized regime $Nd\gg n$.

2 Comparing NT regression and polynomial regression

We also trained a two-layer neural network to fit this linear model. Under specific initialization of weights, the test error is well aligned with the one from NT KRR and polynomial ridge regression. Details can be found in the appendix.

Main results

Throughout, we will use $C,C_{0},C_{1},C_{2},C_{3}$ to refer to constants that do not depend on $d$. In particular, for notational convenience, the value of $C$ may change from line to line.

Most of our statement apply to settings in which $N,n,d$ all grow to $\infty$, while satisfying certain conditions. Without loss of generality, one can thing that such sequences are indexed by $d$, with $N,n$ functions of $d$.

2 Definitions and assumptions

The entries of the kernel matrix take the form

The infinite-width kernel matrix is given by

In terms of the featurization map $\Phi$, an NT function f\in\mathcal{F}_{{\sf NT}}^{N}(\text{\boldmathW}) reads

3 Structure of the kernel matrix

Note that any NT model (1) can be approximated arbitrarily well by a two-layer neural network with $2N$ neurons. This can be seen by taking $\varepsilon\to 0$ in f_{\varepsilon}(\text{\boldmathx})=\sum_{k=1}^{N}\frac{1}{\varepsilon}\big{\{}\sigma(\langle\text{\boldmathw}_{k},\text{\boldmathx}\rangle+\varepsilon\langle\text{\boldmatha}_{k},\text{\boldmathx}\rangle)-\sigma(\langle\text{\boldmathw}_{k},\text{\boldmathx}\rangle-\varepsilon\langle\text{\boldmatha}_{k},\text{\boldmathx}\rangle)\big{\}}. As a consequence, in the above setting, a $2N$-neurons neural network can interpolate $n$ data points with arbitrarily small approximation error with high probability provided $Nd/(\log(Nd))^{C}\geq n$.

To the best of our knowledge, this is the first result of this type for regression. The concurrent paper [Dan20] proves a similar memorization result for classification but exploits in a crucial way the fact that in classification it is sufficient to ensure y_{i}f(\text{\boldmathx}_{i})>0. Regression is considered in [BELM20] but the number of required neurons depends on the interpolation accuracy.

The proof of Theorem 3.1 is presented in Section 7. The key is to show that the NT kernel concentrates to the infinite-width kernel for large enough $N$.

For any constant $\gamma>0$, we define an event $\mathcal{A}_{\gamma}$ as follows.

If we further have $n\leq Nd/(\log(Nd))^{C}$, $n\geq c_{0}d$ for $c_{0}>0$ and a sufficiently large constant $C$, then we can take $\eta^{\prime}=(n(\log(Nd))^{C^{\prime}}/Nd)^{1/2}$ here.

4 Test error

where f(\,\cdot\,;\text{\boldmatha}) is defined as per Eq. (1). Explicitly, we have

We occasionally call this ‘generalization error’, with a slight abuse of terminology (sometimes this term is referred to the difference between test error and the train error n^{-1}\sum_{i\leq n}(y_{i}-\langle\widehat{\boldsymbol{a}},\text{\boldmath\Phi}(\text{\boldmathx}_{i})\rangle)^{2}.)

Kernel ridge regression and polynomial ridge regression are well understood. Our next result establishes a relation between these risks: the neural tangent model behaves as the polynomial model, albeit with a different value of the regularization parameter.

where $\tau^{2}:=\|f_{*}\|^{2}_{L^{2}}+\sigma^{2}_{\varepsilon}$.

Consider ridge regression with respect to the linear features, with regularization $\gamma\geq 0$:

Note that $R_{\mbox{\tiny\rm lin}}(f_{*};\gamma)$ is essentially the same as $R_{{\sf PRR}}(f_{*};\lambda+v(\sigma))$, with the minor difference that we are not fitting an intercept. The scaling factor $d^{-1}$ is specially chosen for comparison with NT KRR. Theorem 3.3 implies the following correspondence.

Here we emphasized the dependence on $\kappa$. Also, as $\kappa\to\infty$, $\mathscrsfs{B}_{\mbox{\tiny\rm lin}}(\kappa,\gamma)=\gamma^{2}\kappa^{-2}+O(\kappa^{-3})$ and $\mathscrsfs{V}_{\mbox{\tiny\rm lin}}(\kappa,\gamma)=\kappa^{-1}+O(\kappa^{-2})$.

5 An upper bound on the memorization capacity

In the regression setting, naively counting degrees of freedom would imply that the memorization capacity of a two-layer network with $N$ neurons is at most given by the number of parameters, namely $N(d+1)$. More careful consideration reveals that, as long as the data \{(\text{\boldmathx}_{i},y_{i})\}_{i\leq n} are in generic positions $N=O(1)$ neurons are sufficient to achieve memorization within any fixed accuracy, using a ‘sawlike’ activation function.

These constructions are of course fragile and a non-trivial upper bound on the memorization capacity can be obtained if we constrain the weights. In this section, we prove such an upper bound. We state it for binary classification, but it is immediate to see that it implies an upper bound on regression which is of the same order.

The value y_{i}f(\text{\boldmathx}_{i}) is referred to the margin for input \text{\boldmathx}_{i}. In regression we require y_{i}f(\text{\boldmathx}_{i})=y_{i}^{2}=1 (the latter equality holds for $\{+1,-1\}$ labels), while in classification we ask for yf(\text{\boldmathx}_{i})>0. The next result states that $Nd$ must be roughly of order $n$ in order for a neural network to fit a nontrivial fraction of data with $\delta$ margin.

Assume that, with probability larger than $\eta_{1}$, there exists a function $f\in\mathcal{F}_{{\sf NN}}^{N,L}$ such that

(In words, $f$ achieves margin $\delta$ in at least a fraction $(1+\eta_{2})/2$ of the samples.)

Then we must have $n\leq C^{-1}Nd\log(Ld/\delta)$.

If $L$ and $1/\delta$ are upper bounded by a polynomial of $d$, then this result implies an upper bound on the network capacity of order $Nd\log d$. This matches the interpolation and invertibility thresholds in Corollary 3.1, and Theorem 3.1 up to a logarithmic factor. The proof follows a discretization–approximation argument, which can be found in the appendix.

Notice that the memorization capacity upper bound $C^{-1}Nd\log(Ld/\delta)$ tends to infinity when the margin vanishes $\delta\to 0$. This is not an artifact of the proof. As mentioned above, if we allow for an arbitrarily small margin, it is possible to construct a ‘sawlike’ activation function $\sigma$ such that the corresponding network correctly classifies $n$ points with binary labels $y_{i}\in\{+1,-1\}$ despite $n\gg Nd$. Note that our result is different from [YSJ19, BHLM19] in which the activation function is piecewise linear/polynomial.

While we stated Proposition 3.1 for classification, it has obvious consequences for regression interpolation. Indeed, considering $y_{i}\in\{+1,-1\}$, the interpolation constraint f(\text{\boldmathx}_{i})=y_{i} implies y_{i}f(\text{\boldmathx}_{i})\geq\delta_{0}=1.

Related work

As discussed in the introduction, we addressed three questions: Q1: What is the maximum number of training samples $n$ that a network of given width $N$ can interpolate (or memorize)? Q2: Can such an interpolator be found efficiently? Q3: What are the generalization properties of the interpolator? While questions Q1 and Q2 have some history (which we briefly review next), much less is known about Q3, which is our main goal in this paper.

In the context of binary classification, question Q1 was first studied by Tom Cover [Cov65], who considered the case of a simple perceptron network ($N=1$) when the feature vectors (\text{\boldmathx}_{i})_{i\leq n} are in a generic position, and the labels $y_{i}\in\{+1,-1\}$ are independent and uniformly random. He proved that this model can memorize $n$ training samples with high probability if $n\leq 2d(1-\varepsilon)$, and cannot memorize them with high probability if $n\geq 2d(1+\varepsilon)$. Following Cover, this maximum number of samples is sometimes referred to as the network capacity but, for greater clarity, we also use the expression network memorization capacity.

The case of two-layers network was studied by Baum [Bau88] who proved that, again for any set of points in general positions, the memorization capacity is at least $Nd$. Upper bound of the same order were proved, among others, in [Sak92, Kow94]. Generalizations to multilayer networks were proven recently in [YSJ19, Ver20]. Can these networks be found efficiently? In the context of classification, the recent work of [Dan19] provides an efficient algorithm that can memorize all but a fraction $\varepsilon$ of the training samples in polynomial time, provided the $Nd\geq Cn/\varepsilon^{2}$. For the case of Gaussian feature vectors, [Dan20] proves that exact memorization can be achieved efficiently provided $Nd\geq Cn(\log d)^{4}$.

In concurrent work, [BELM20] studied the interpolation properties of two-layers networks. Generalizing the construction of Baum [Bau88], they show that, for $N\geq 4\lceil n/d\rceil$ there exists a two-layers ReLU network interpolating $n$ points in generic positions. This is however unlikely to be the network produced by gradient-based training. They also construct a model that interpolates the data with error $\varepsilon$, provided $Nd\geq n\log(1/\varepsilon)$. In contrast, we obtain exact interpolation provided $Nd\geq n(\log Nd)^{C}$ From a more fundamental point of view, our work does not only construct a network that memorizes the data, but also characterizes the eigenstructure of the kernel matrix. While our paper is under review, more papers on memorization are posted, including [VYS21, PLYS21] that study the effect of depth.

As discussed in the introduction, we focus here on the lazy or neural tangent regime in which weights change only slightly with respect to a random initialization [JGH18]. This regime attracted considerable attention over the last two years, although the focus has been so far on its implications for optimization, rather than on its statistical properties.

As mentioned several times, our main contribution is a characterization of the test error of minimum norm regression in the NT model (1). We are not aware of any comparable results.

Upper bounds on the generalization error of neural networks based on NT theory were proved, among others, in [ADH+19, AZLL19, CG19, JT19, CCZG19, NCS19]. These works assume a more general data distribution than ours. However their objectives are of very different nature from ours. We characterize the test error of interpolators, while most of these works do not consider interpolators. Our main result is a sharp characterization of the difference between test error of NT regression (with a finite number of neurons $N$) and kernel ridge regression (corresponding to $N=\infty$), and between this and polynomial regression. None of the earlier work is sharp enough to provide to control these quantities. More in detail:

The upper bounds of [AZLL19, CG19] do not apply to interpolators since SGD is run in a one-pass fashion. Further they require large overparametrization, namely $N\gtrsim n^{7}$ in [CG19] and $N$ depending on the generalization error in [AZLL19]. Finally, they bound generalization error rather than test error, and do not bound the difference between NT regression and kernel ridge regression.

The upper bounds of [JT19, CCZG19, NCS19] apply to classification and require a large margin condition. As before, these papers do not bound the difference between NT regression and kernel ridge regression.

Results similar to ours were recently obtained in the context of simpler random features models in [HMRT19, GMMM21, MM21, MRSY19, GMMM20, MMM21]. The models studied in these works corresponds to a two-layer network in which the first layer is random and the second is trained. Their analysis is simpler because the featurization map has independent coordinates.

Connections with gradient descent training of neural networks

In this section we discuss in greater detail the relation between the NT model (1) studied in the rest of the paper, and fully nonlinear two-layer neural networks. For clarity, we will adopt the following notation for the NT model:

We changed the normalization purely for aesthetic reasons: since the model is linear, this has no impact on the min-norm interpolant. We will compare it to the following neural network

Note that the network has $2N$ hidden units and the second layer weights $b_{k}$ are fixed. We train the first-layer weights using gradient flow with respect to the empirical risk

The next theorem is a slight modification of [BMR21, Theorem 5.4] which in turn is a refined version of the analysis of [COB19, OS20].

then, with probability at least $1-2\exp\{-n/C_{0}\}$, the following holds.

In particular the rate is lower bounded as $\lambda_{*}\geq C_{1}\alpha^{2}d/n$ by Theorem 3.1.

The difference in test errors between the neural network (32) trained via gradient flow and the min-norm NT interpolant studied in this paper can be bounded using Eq. (37) by triangular inequality. Also, while we focus for simplicity on gradient flow, similar results hold for gradient descent with small enough step size.

Even among two-layer fully connected neural networks, model (32) presents some simplifications:

Second-layer weights are not trained and fixed to $b_{j}\in\{+1,-1\}$. If second-layer weights are trained, the NT model (31) needs to be modified as follows

The new model has $N(d+1)$ parameters \text{\boldmatha}=(\text{\boldmatha}_{1},\dots,\text{\boldmatha}_{N};\widetilde{a}_{1},\dots,\widetilde{a}_{N}). Notice that, for large dimension, the additional number of parameters is negligible. Indeed, going through the proofs reveals that our analysis can be extended to this case at the price of additional notational burden, but without changing the results.

We also point out that the model in which only second layer weights are trained, i.e. we set \text{\boldmatha}_{i}=0 in Eq. (38), has been studied in detail in [GMMM21, MMM21]. These papers support the above parameter-counting heuristics.

The specific initialization (34) is chosen so that f_{{\sf NN}}(\text{\boldmathx};\widetilde{\text{\boldmathW}}^{0})=0 identically. If this initialization was modified (for instance by taking independent (\widetilde{\text{\boldmathw}}_{k})_{k\leq 2N} ) two main elements would change in the analysis. First, the target model f_{*}(\text{\boldmathx}) should be replaced by the difference between target and initialization f_{*}(\text{\boldmathx})-f_{{\sf NN}}(\text{\boldmathx};\widetilde{\text{\boldmathW}}^{0}). Second, and more importantly, the approximation results in Theorem 5.1 become weaker: we refer to [BMR21] for a comparison.

Within the setting of Theorem 5.1 (in particular $y_{i}$ being $C$-subgaussian), the null risk $\|f_{*}\|^{2}_{L^{2}}$ is of order one, and therefore we should compare the right-hand side of Eq. (37) with $\|f_{*}\|_{L^{2}}=\Theta(1)$. We can point at two specific regimes in which this upper bound guarantees that \|f_{{\sf NN}}(\widetilde{\text{\boldmathW}}^{\infty})-f_{{\sf NT}}(\widehat{\text{\boldmatha}},\text{\boldmathW})\|_{L^{2}}\ll\|f_{*}\|_{L^{2}}:

First letting $\alpha$ grow, the this upper bound vanishes. More precisely, it becomes much smaller than one provided $\alpha\gg(n^{2}/Nd)^{1/2}\vee(n^{5}/Nd^{4})^{1/4}$. By training the two-layer neural network with a large scaling parameter $\alpha$, we obtain a model that is well approximated by the NT model as soon as the overparametrization condition $n\leq Nd/(\log Nd)^{C}$ is satisfied.

This role of scaling in the network parameters, and its generality were first pointed out in [COB19]. It implies that the theory developed in this always applied to nonlinear neural networks under a certain specific initialization and training scheme.

A standard initialization rule suggests to take $\alpha=\Theta(1)$. In this case, the right-hand side of Eq. (37) becomes small for wide enough networks, namely $Nd\gg n^{2}\vee(n^{5}/d^{4})$. This condition is stronger than the overparametrization condition under which we carried our analysis of the NT model.

This means that, for $\alpha=\Theta(1)$ and $n(\log n)^{C}\ll Nd\lesssim n^{2}\vee(n^{5}/d^{4})$, we can apply our analysis to neural tangent models but not to actual neural networks. On the other hand, the condition $Nd\gg n^{2}\vee(n^{5}/d^{4})$ in Theorem 5.1 is likely to be a proof artifact, and we expect that it will be improved in the future. In fact we believe that the refined characterization of the NT model in the present paper is a foundational step towards such improvements.

Technical background

where $B(d,k)$ is a dimension parameter that is monotonically increasing in $k$ and satisfies $B(d,k)=(1+o_{d}(1))d^{k}/k!$. This normalization guarantees $Q_{k}^{(d)}(d)=1$. The following are some properties of Gegenbauer polynomials we will use.

where $Y_{k,1}^{(d)},\ldots,Y_{k,B(d,k)}^{(d)}$ are normalized spherical harmonics of degree $k$; more precisely, each $Y_{k,i}^{(d)}$ is a polynomial of degree $k$ and they satisfy

Note that point $(b)$ and the Cauchy-Schwarz inequality implies $\max_{|t|\leq d}|Q_{k}^{(d)}(t)|\leq 1$. If the function $\sigma^{\prime}$ satisfies $\sigma^{\prime}\in L^{2}([-\sqrt{d},\sqrt{d}],\tau_{d-1}^{1})$, then we can decompose $\sigma^{\prime}$ using Gegenbauer polynomials:

Kernel invertibility and concentration: Proof of Theorems 3.1 and 3.2

To ease notations, we will henceforth write the target function $f_{*}$ simply as $f$.

Finally, $\gamma_{0}=o_{d}(1)$ and for $k\geq 1$ we have $\gamma_{k}=\mu_{k-1}^{2}+o_{d}(1)$, where we recall that $\mu_{k}$ is the $k$-th coefficient in the Hermite expansion of $\sigma^{\prime}$.

The use of spherical harmonics and Gegenbauer polynomials to study inner product kernels on the sphere (the $N=\infty$ case) is standard since the classical work of Schoenberg [Sch42]. Several recent papers in machine learning use these tools [Bac17, BM19, GMMM21]. On the other hand, quantitative properties when both the sample size $n$ and the dimension $d$ are large are much less studied [GMMM21]. The finite width $N$ case is even more challenging since the kernel is no longer of inner-product type.

We thus obtain, for fixed $x$, \text{\boldmathx}^{\prime}:

Here, $(i)$ is due to the the orthogonality of Q_{k}^{(d)}(\sqrt{d}\,\langle\text{\boldmathx},\,\cdot\,\rangle) and Q_{k^{\prime}}^{(d)}(\sqrt{d}\,\langle\text{\boldmathx}^{\prime},\,\cdot\,\rangle) for $k\neq k^{\prime}$ as well as Lemma 24 (exchanging summation with expectation), and $(ii)$ is due to the property (40).

We use the recurrence formula to simplify the above expression.

The asymptotic formulas for $\gamma_{k}$ follow by the convergence of Gegenbauer expansion to Hermite expansion discussed in Section 6. ∎

Here, $\gamma_{k}\geq 0$ and $\gamma_{k}=\mu_{k-1}^{2}+o_{d}(1)$ (we denote $\mu_{-1}=0$).

Using Lemma 1, and using property (41) to express

and \text{\boldmathQ}_{k}:=(Q_{k}^{(d)}(\langle\text{\boldmathx}_{i},\text{\boldmathx}_{j}\rangle))_{i,j\leq n}. Note that

By first taking $d\to\infty$ and then $M\to\infty$, we obtain

Here in the last line we recall that $\rho$ is the standard Gaussian measure, and we used dominated convergence to show that $\|\sigma^{\prime}\|_{L^{2}(\widetilde{\tau}^{1}_{d-1})}^{2}\to\|\sigma^{\prime}\|_{L^{2}(\rho)}^{2}$. By Proposition E.1, we have with very high probability,

By [Ver18][Theorem 5.6.1 and Exercise 5.6.4], we obtain

2 Concentration of neural tangent kernel: Proof of Theorem 3.2

Let $C_{0}>0$ be a sufficiently large constant (which is determined later). Define the truncated function

Note that by definition and the assumption on the activation function, namely Assumption 3.2, we have $|\varphi(x)|\leq B(1+(C_{0}\log(nNd))^{B})$.

Note that $\mathcal{A}_{\gamma}$ is a very high probability event as a consequence of Lemma 2. We shall treat \text{\boldmathx}_{1},\ldots,\text{\boldmathx}_{n} as deterministic vectors such that the conditions in the event $\mathcal{A}_{\gamma}$ holds.

Step 1: The effect of truncation is small. First, we realize that

By the fact that uniform spherical random vector is subgaussian [Ver10][Sect. 5.2.5], we pick $C_{0}$ sufficiently large such that

where A_{i}:=\{|\langle\text{\boldmathx}_{i},\text{\boldmathw}\rangle|\leq C_{0}\log(nNd)\}. For the first term, we derive

where (i) is due to |\langle\text{\boldmathx}_{i},\text{\boldmathx}_{j}\rangle|\leq\|\text{\boldmathx}_{i}\|\cdot\|\text{\boldmathx}_{j}\|=d, (ii) is due to Hölder’s inequality, and (iii) follows from the polynomial growth assumption on $\sigma^{\prime}$. By (57), we can choose $C_{0}$ large enough such that $|I_{1}|\leq C(nNd)^{-2}$. Similarly, we can prove that $|I_{2}|\leq C(nNd)^{-2}$. Thus,

We choose a sufficient large constant $C^{\prime}$ and set

so that the right-hand side of (60) is no larger than $2n\cdot\exp(-(\log(nNd)^{2}))$. This proves that with very high probability,

Since $1/(\gamma nNd)\leq O(1)\cdot C^{\prime}\sqrt{(n+d)(\log(nNd))^{C^{\prime}}/(Nd)}$, we can enlarge the constant $C^{\prime}$ appropriately to obtain that with very high probability,

3 Smallest eigenvalue of neural tangent kernel: Proof of Theorem 3.1

By Lemma 2, we have, with high probability,

and we can strengthen the inequalities $\geq$ to equalities $=$ in (i), (ii) if $n>d+1$. By Theorem 3.2 and Eq. (14) in its following remark,

Generalization error: Proof outline of Theorem 3.3

In this section outline the proof our main result Theorem 3.3, which characterize the test error of NT regression. We describe the main scheme of proof, and how we treat the bias term. We refer to the appendix where the remaining steps (and most of the technical work) are carried out.

In NT regression the coefficients vector is given by Eq. (16) and, more explicitly, Eq. (17). The prediction function \widehat{f}_{{\sf NT}}(\text{\boldmathx})=\langle\text{\boldmath\Phi}(\text{\boldmathx}),\widehat{\text{\boldmatha}}\rangle can be written as

In the kernel ridge regression, the prediction function is

Similarly, we can decompose the associated generalization error $R_{{\sf KRR}}(\lambda)$ into three errors.

The first part of Theorem 3.3, establishing that NT regression is well approximated by kernel ridge regression for overparametrized models, is an immediate consequence of the next statement.

There exists a constant $C^{\prime}>0$ such that the following holds. If $n\leq(\log(Nd))^{C^{\prime}}Nd$, then for any $\lambda>0$, with high probability,

Its associated generalization error $R_{{\sf PRR}}(\lambda)$ into also decomposed into three errors.

The second part of Theorem 3.3 follows immediately from the following result.

There exists a constant $C^{\prime}>0$ such that the following holds. For any $\lambda>0$, with high probability,

In this section we prove the first inequality in Eq. (62). Since both sides are homogeneous in $f$, we will assume without loss of generality that $\|f\|_{L^{2}}=1$.

Our goal is to show that $I_{1}^{N}$ and $I_{1}$ are close, and that $I_{2}^{N}$ and $I_{2}$ are close. Let us pause here to explain the challenges and our proof strategy:

Here, we denote $\eta=\sqrt{n(\log(nNd))^{C^{\prime}}/(Nd)}$. As a consequence, we have, with high probability,

We handle the other two terms \delta I_{12}^{g,\text{\boldmathh}} and \delta I_{23}^{\text{\boldmathh}} in a different way. Denote

The function $\widetilde{h}$ satisfies \|\widetilde{h}\|_{L^{2}}\leq C\|\text{\boldmathh}\|^{2}/n with high probability by the following lemma, which we will prove in Section B.3.

We can rewrite \delta I_{12}^{g,\text{\boldmathh}} and \delta I_{23}^{\text{\boldmathh}} as

Let \text{\boldmathz}_{1},\text{\boldmathz}_{2},\text{\boldmathz} be independent copies of $x$. Then we have

Moreover, it holds that with high probability,

As a consequence, with high probability, we have

In Lemma 3 and 5, we set \text{\boldmathh}=\text{\boldmathf} and $g=f$. By the conclusions of these two lemmas, we will obtain the bound on the bias term in Theorem 8.1. We defer the proofs of the two lemmas to the appendix.

Conclusions

We studied the neural tangent model associated to two-layer neural networks, focusing on its generalization properties in a regime in which the sample size $n$, the dimension $d$, and the number of neurons $N$ are all large and polynomially related ($c_{0}d\leq n\leq d^{1/c_{0}}$ for some small constant $c_{0}>0$), while in the overparametrized regime $Nd\gg n$. We assumed an isotropic model for the data (\text{\boldmathx}_{i})_{i\leq n}, and noisy label $(y_{i})_{i\leq n}$ with a general target y_{i}=f_{*}(\text{\boldmathx}_{i})+\varepsilon_{i} (with $\varepsilon_{i}$ independent noise).

An immediate corollary is that, as soon as $Nd\geq n(\log d)^{C}$, the neural network can exactly interpolate arbitrary labels.

Our analysis offers several insight to statistical practice:

NT models provide an effective randomized approximation to kernel methods. Indeed their statistical properties are analogous to the one of more standard random features methods [RR08], when we compare them at fixed number of parameters [MMM21]. However, the computational complexity at prediction time of NT models is smaller than the one of random feature models if we keep the same number of parameters.

The additional error due to the finite number of hidden units is roughly bounded by $\sqrt{n/(Nd)}$.

In high dimensions, the nonlinearity in the activation function produces an effective ‘self-induced’ regularization (diagonal term in the kernel) and as a consequence interpolation can be optimal.

Finally, our characterization of generalization error applies to two-layer neural networks (under specific initializations) as long as the neural tangent theory provides a good approximation for their behavior. In Section 5 we discussed sufficient conditions for this to be the case, but we do not expect these conditions to be sharp.

Acknowledgements

We thank Behrooz Ghorbani and Song Mei for helpful discussion. This work was supported by NSF through award DMS-2031883 and from the Simons Foundation through Award 814639 for the Collaboration on the Theoretical Foundations of Deep Learning. We also acknowledge NSF grants CCF-1714305, IIS-1741162, and the ONR grant N00014-18-1-2729.

Appendix A Additional numerical experiment

Appendix B Generalization error: Proof of Theorem 3.3

This section finishes the proof of our main result, Theorem 3.3, which was initiated in Section 8. We use definitions and notations introduced in that section.

By homogeneity we can and will assume, without loss of generality, $\|f\|_{L^{2}}=\sigma_{\varepsilon}=1$.

This implies that $|\delta J_{1}|\leq C\eta$ and $|\delta J_{2}|\leq C\eta$ w.h.p. Moreover, denoting

Applying Lemma 5 in which we set \text{\boldmathh}=\text{\boldmath\varepsilon}, we obtain w.h.p.,

This implies that $|\delta J_{3}|\leq C\eta$ w.h.p. as well. This proves the bound on the variance term in Theorem 8.1.

For the first term $\widetilde{\delta J}_{1}$, we further decompose:

From Eqs. (67) and (71) in Lemma 3 (setting $g=f$ and \text{\boldmathh}=\text{\boldmath\varepsilon}), we have $|\widetilde{\delta J}_{11}|\leq C\eta$ w.h.p. By Lemma 5 Eq. (76) (setting $h$ to $\varepsilon$), w.h.p.,

so with high probability $|\widetilde{\delta J}_{12}|\leq C\eta$. Thus we proved $|\widetilde{\delta J}_{1}|\leq C\eta$.

Finally, we further decompose $\widetilde{\delta J}_{2}$ as follows.

By Lemma 3 (in which we set $h$ to $f$) and Eqs. (79)–(81), we have $|\widetilde{\delta J}_{21}|\leq C\eta$ and $|\widetilde{\delta J}_{22}|\leq C\eta$ w.h.p. Moreover, denoting

we express $\widetilde{\delta J}_{23}$ as

B.2 Proof of Lemma 3

for a sufficiently large $C>0$ such that we can use the following inequalities by Lemma 2 and Theorem 3.2:

We start with the easiest bounds in Lemma 3.

The first two bounds follow from the observation

We conclude that Eq. (69) and (70) hold with high probability.

Recall the notations in the proof of Theorem 3.2, cf. Eqs. (55), (56).

Finally, we recall that $B(d,k)=(1+o_{d}(1))\cdot d^{k}/k!$. This then leads to the claim (92).

Suppose that $\min\{\lambda_{k}/\lambda_{k^{\prime}},\lambda_{k^{\prime}}/\lambda_{k}\}\leq 1/4$. Then,

This proves the claim (95). By the kernel eigenvalue structure (Lemma 6),

By the assumptions on $\lambda_{k}$ and $\lambda_{k^{\prime}}$, with very high probability,

By the kernel invertibility, Theorem 3.2, we have

Combining (97) and (100), we have shown that with very high probability,

Suppose that $c^{\prime}n\leq m\leq C^{\prime}n$, where $c^{\prime},C^{\prime}\in(0,1)$ are constants. Then there exists $c>0$ such that with very high probability,

By the variational characterization of singular values and the triangle inequality,

where (i) follows from Jensen’s inequality, and (ii) is due to

There exist constant $C_{1},C_{2}>0$ such that the following holds. With very high probability,

Consequently, we obtain (67) and (68) in Lemma 3.

(where $C>0$ is a constant). Taking the square, we have

It is clear that the second term on the last line is bounded by C\|\widetilde{\text{\boldmathf}}_{2}\| with very high probability, by Eq. (110). For the first term, with very high probability,

(Note that the left-hand side is a random variable depending on \text{\boldmathx}_{1},\ldots,\text{\boldmathx}_{n} and \text{\boldmathw}_{1},\ldots,\text{\boldmathw}_{N}.) Indeed, for any $\beta^{\prime}>0$, By Markov’s inequality,

with very high probability. This proves the claim. ∎

B.3 Proof of Lemma 4

By homogeneity, we will assume, without loss of generality $\|f\|_{L^{2}}=1$.

Recall that, by Lemma 1, we have K(\text{\boldmathx}_{i},\text{\boldmathx})=\sum_{k=0}^{\infty}\gamma_{k}Q_{k}^{(d)}(\langle\text{\boldmathx}_{i},\text{\boldmathx}\rangle) (where we replaced \text{\boldmathx}_{j} by an independent copy $x$ for notational convenience). We derive

where in (i) we used \lim_{M\to\infty}\|\sum_{k>M}\gamma_{k}Q_{k}^{(d)}(\langle\text{\boldmathx}_{i},\cdot\rangle)\|_{L^{2}}=0 and convergence in $L^{2}$-spaces (Lemma 24), and in (ii) we used the identity (40). Note that

where (i) follows from the identity (156) and (ii) follows form (82). This completes the proof of (74).

In order to prove (75), we will prove that the following holds w.h.p.

We use the Cauchy-Schwarz inequality on the left-hand side. Since we assumed, without loss of generality, $\|f\|_{L^{2}}=1$, we only need to show

for any unit vector $u$. This is immediate from (74) since

B.4 Proof of Lemma 5

Step 1: Proving (76)–(78). Define, for $k\leq N$,

Since $\|g\|_{L^{2}}$ is independent of $w$, it follows that

Let \text{\boldmath\alpha}=(\alpha_{1},\ldots,\alpha_{n})^{\top} be any vector, then

By definition, \text{\boldmathQ}(\text{\boldmathw}) is p.s.d. for all $w$. For any $w$ and unit vector $u$,

where we used the Cauchy-Schwarz inequality and (123)–(124). This implies

For any vector \text{\boldmath\alpha}=(\alpha_{1},\ldots,\alpha_{n})^{\top}, we derive

Step 3: Proving the “as a consequence” part. Now we derive bounds on \delta I_{12}^{g,\text{\boldmathh}} and \delta I_{23}^{\text{\boldmathh}}. By assumption, $\|g\|_{L^{2}}$ is bounded by a constant.

Also, by assumption \|\text{\boldmathh}\|^{2}/n\leq C with high probability. Therefore

Combining the last two bounds then leads to the bound on |\delta I_{23}^{\text{\boldmathh}}|. ∎

B.5 Proof of Theorem 8.2

We first show that Theorem 8.2 follows from this lemma. After that, we will prove Lemma 11.

We apply Lemma 11 with \text{\boldmathh}_{1}=\text{\boldmath\varepsilon} and \text{\boldmathh}_{2}=\text{\boldmathf}. This leads to $|E_{\text{\rm Cross}}-E_{\text{\rm Cross}}^{p}|\leq\eta^{\prime}$, which completes the proof. ∎

where we used Lemma 4 Eq. (74). Combining the upper bounds on $|\delta I_{1}^{\prime}|$ and $|\delta I_{2}^{\prime}|$, we arrive at the first inequality in the lemma.

Next, we bound $|\delta I_{3}^{\prime}|$. With high probability,

The proof of the generalization error under this relaxed condition follows mostly the proof in Section B.2, with modifications we show in this subsection.

For any constant $\delta\in(0,0.1)$, there exists certain $C_{\delta}>1$ such that the following holds. If $n\geq C_{\delta}d$, then with very high probability,

Fix the constant $\delta=0.01$. Let $C_{\delta}>1$ be the constant in Lemma 12. First, we establish some useful results under the condition

the eigenvalues have the following structure:

In the proof of Lemma 6, instead of claiming (93), we will show that the following modified claim holds.

We omit the rest of proof, as it follows closely the proof of Lemma 6. ∎

Suppose that $\min\{\lambda_{k}/\lambda_{k^{\prime}},\lambda_{k^{\prime}}/\lambda_{k}\}\leq 1/4$. Then,

By the assumptions on $\lambda_{k}$ and $\lambda_{k^{\prime}}$, with very high probability,

which results in the same conclusion as in Lemma 7 (a). To show the modified inequality in (b), we only need to notice that

Suppose that $c^{\prime}n\leq m\leq C^{\prime}n$, where $c^{\prime},C^{\prime}\in(0,1)$ are constants. Also suppose that the condition (135) is satisfied. Then there exist $C_{3},c>0$ such that if $m>(C_{3}+1)d$, then with very high probability,

where \widetilde{\text{\boldmathf}} is defined in (104).

There exist constant $C,C_{2}>0$ such that the following holds. If $c_{0}d\leq n\leq d^{2}/(C(\log d)^{C})$, then with high probability,

Consequently, we obtain (67) and (68) in Lemma 3 under the relaxed condition $c_{0}d\leq n\leq d^{2}/(C(\log d)^{C})$.

Following the proof of Lemma 16, we have with very high probability,

As in the proof of Lemma 16, it suffices to show

for certain constant $c>0$. In the case $n>(C_{3}+1)d$, the assumptions in Lemma 13, 14, 15 are satisfied. Following the proof of Lemma 16, we have

In order to resolve this issue, we first notice that if $\gamma_{0}n_{0}\leq 2\gamma_{1}n_{0}/d$, then (143) holds with very high probability. In fact,

First, we make a claim about \text{\boldmathv}_{s}^{(1)}. There exists a constant $C_{3}>0$ such that if $\gamma_{0}n_{0}\geq C_{3}$, then for certain constant $c_{0}^{\prime}>0$, with very high probability,

To prove this claim, we express \widetilde{\text{\boldmathv}}_{s}^{(1)} as

where $C_{4},C_{4}^{\prime}>0$ are some constants. Thus, we obtain

In order to bound the smallest eigenvalue in (143), we consider two cases.

where we used the claim (145) in (i). The second lower bound is

where $c_{1}>0$ is certain small constant, and in the last inequality we used our assumption $n\leq(C_{3}+1)d$. If \|\text{\boldmathz}_{-1}\|\leq\min\{1/2,c_{0}^{\prime}/12\}, then by the first lower bound (146), we have

If \|\text{\boldmathz}_{-1}\|\geq\min\{1/2,c_{0}^{\prime}/12\} instead, then the second lower bound (147) implies that the left-hand side above is lower bounded by a constant. Combining the two cases, we obtain

This proves the desired inequality (143). The remaining proof is similar proof of Lemma 16. ∎

Appendix D Generalization error for linear model: proof of Corollary 3.2

Throughout this subsection, let the assumptions of Corollary 3.2 hold. Denote $\overline{\lambda}:=\lambda+v(\sigma)$. First, we state and prove a lemma. We will use the simple identity

There exist constants $c,C>0$ such that the following holds. With high probability,

where in the last inequality we used $\overline{\lambda}\geq c$ for a constant $c>0$ so $\overline{\lambda}+C\lambda_{1}\leq C^{\prime}\overline{\lambda}$. If $n>16d$, we observe that

In either case, the first inequality of the lemma holds with high probability. Next, we notice that

Building on this lemma, we prove some useful bounds. For convenience, we define

In this proof, we will use the bounds on the singular values of $X$ from Lemma 21. To prove the two bounds in (149a), we observe that

where in (i) we used Lemma 17. So by the triangle inequality, we have

The diagonal entries are all no larger than $d$, so this proves the first bound in (149c). Moreover,

To study the risk $R_{{\sf PRR}}(\overline{\lambda})$ in the linear case, we first notice that K^{p}(\text{\boldmathx}_{i},\text{\boldmathx}_{j})=\gamma_{0}+\frac{\gamma_{1}}{d}\text{\boldmathx}_{i}^{\top}\text{\boldmathx}_{j}. Thus, we have

The expressions for the bias/variance/cross terms are given below.

To further simplify the terms, we will show the following lemma.

Once these bounded are proved, then by Lemma 23 we have

Similar to the decomposition of the risk $R_{{\sf PRR}}(\overline{\lambda})$ and Lemma 20, we can show that $R_{\mbox{\tiny\rm lin}}(\gamma)$ has a similar variance-bias decomposition and that the components concentrate to their respective trace, which yield Eqs. (25)–(27). Combining these with Theorem 3.3 and (154), we arrive at the claims in Corollary 3.2.

To complete the proof, below we first prove Lemma 20 and then Lemma 19.

To show the claim (152a), first we notice that

where we used Lemma 17 and 18 in the last inequality. Similarly, we can also prove

Step 2. Finally, to prove the desired results, we connect $\widetilde{I}_{\varepsilon}^{(1)},\widetilde{I}_{1}^{(1)},\widetilde{I}_{\varepsilon,\varepsilon}^{(2)},\widetilde{I}_{1,1}^{(2)},\widetilde{I}_{\varepsilon,1}^{(2)}$ back to $I_{\varepsilon}^{(1)},I_{1}^{(1)},I_{\varepsilon,\varepsilon}^{(2)},I_{1,1}^{(2)},I_{\varepsilon,1}^{(2)}$. By definition, \text{\boldmath\beta}_{*} and \|\text{\boldmath\beta}_{*}\|\text{\boldmathg}/\|\text{\boldmathg}\| have the same distribution, so there is no loss of generality by writing

Appendix E Supporting lemmas and proofs

where we used concentration of Gaussian vector norms [Ver10, vH14] in the last inequality. This finishes the proof. ∎

Let $\mathcal{H}$ be an $L^{2}$ space and $\langle\cdot,\cdot\rangle_{\mathcal{H}}$ be the associated inner product. If $f,f_{m},g,g_{m}\in\mathcal{H}$ for $m\geq 1$, and $f_{m}\xrightarrow{L^{2}}f$, $g_{m}\xrightarrow{L^{2}}g$, then $\langle f_{m},g_{m}\rangle_{\mathcal{H}}\xrightarrow{m\to\infty}\langle f,g\rangle_{\mathcal{H}}$.

This is a simple convergence result of $L^{2}$ spaces.

E.2 An operator norm bound

Denote \text{\boldmathQ}_{k}=(Q_{k}^{(d)}(\langle\text{\boldmathx}_{i},\text{\boldmathx}_{j}\rangle))_{i,j\leq n}. Then, there exists a constant $C>0$ such that with very high probability,

This lemma is a quantitative refinement of [GMMM21][Prop. 3]. Difference from the moment method employed in [GMMM21][Prop. 3], the proof of this lemma uses a specific matrix concentration inequality, namely the matrix version of Freedman’s inequality for martingales, first established by [T+11] (see also [Oli09]).

Consider a matrix-valued martingale \{\text{\boldmathY}_{i}:i=0,1,\ldots\} with respect to the filtration $(\mathcal{F}_{i})_{i=0}^{\infty}$. The values of \text{\boldmathY}_{i} are symmetric matrices with dimension $n$. Let \text{\boldmathZ}_{i}=\text{\boldmathY}_{i}-\text{\boldmathY}_{i-1} for all $i\geq 1$. Assume that \lambda_{\max}(\text{\boldmathZ}_{i})\leq\overline{L} almost surely for all $i\geq 1$. Then, for all $t\geq 0$ and $v\geq 0$,

By a simple concentration result (Lemma 22), we have, with very high probability,

In this proof, we will use the identities

Let $j,m\in[n]$ be indices. Since \text{\boldmathZ}_{i} is symmetric, there is no loss of generality in only considering that $j<m$ (note (\text{\boldmathZ}_{i})_{jj}=0 if $j=m$). If $m<i$, then $\overline{Q}_{jm}\in\mathcal{F}_{i-1}$ so [\text{\boldmathZ}_{i}]_{jm}=0. Next we consider $m>i$. Observe that

where in (i) we used (160), in (ii) we used the Cauchy-Schwarz inequality, and in (iii) we used (160) and Lemma 22. This implies

Together, these bounds imply |[\text{\boldmathZ}_{i}]_{jm}|=O_{d}(d^{-2k}). Finally, consider $m=i$. A similar argument gives

Combining the three cases, we derive the expression (159). The residual satisfies

where the last inequality is due to $d^{k}\geq n$. Note that (161) also implies

By the property (44) of the Gegenbauer polynomials, we know that the coefficients of $B(d,k)^{1/2}Q(\cdot)$ are of constant order, so we have the deterministic bound

Since $B(d,k)=(1+o_{d}(1))\cdot d^{k}/k!$, this gives $\max_{ij}|\overline{Q}_{ij}|\leq C\sqrt{(\log d)^{k}/d^{k}}$ and thus

Before applying the matrix concentration inequality to the sum \sum_{i=1}^{n}\text{\boldmathZ}_{i}, let us define

Using Lemma 25, we obtain deterministic bounds on $L$ and $V$, as stated below.

The first inequality follows directly from Lemma 25:

To prove the second inequality, we use the decomposition (159).

due to the assumption $d^{k}\geq n$. To further simplify (164), we note that

Now we consider the case where $m<i$ and $j<i$.

where we used the identity (40) in the last equality. We write $1-\xi_{ij}\xi_{im}=(1-\xi_{ij})\xi_{im}+1-\xi_{im}$ and use the Cauchy-Schwarz inequality to derive

where in (i) we used the inequality $|Q_{ij}|\leq 1$, and in (ii) we used Lemma 22. Therefore,

Let the constant $C\geq 1$ be no smaller than those in Lemma 25 and 26. Suppose that

Then, by setting $\overline{L}=C\sqrt{\frac{n(\log d)^{2k}}{d^{k}}}$ and $v=\frac{t^{2}}{32(\log d)^{2}}$, we have

This proves the inequality (167). We note that there is a naive deterministic bound

We apply (167) in which $t$ is set to one of $\{2t,4t,\ldots,2^{s}t$} where $s\geq k\log d/\log 2$. Summing these inequalities and using the naive deterministic bound, we obtain

Let $s\geq 1$ be a constant integer. Our goal is to prove

for certain sufficiently large constant $C^{\prime}$.

where we used the inequality $\sum_{k>k_{0}}\frac{1}{B(d,k)}\leq Cd^{-k_{0}}$. So taking the union bound, we get

Combining (169) with (170) yields the desired goal (168). ∎

Appendix F Proof for network capacity upper bound

Let $M=M_{d}>1$ be a positive integer to be specified later. We define the discretization set $\mathcal{D}_{M}=\{0,\pm\frac{1}{M},\pm\frac{2}{M},\pm\frac{3}{M},\ldots\}$ and

Each $f\in\mathcal{F}_{{\sf NN}}^{N,L}$ is associated with an \text{\boldmath\theta}\in\Theta_{L}.

(1) Lower bound on discretized parameter space. We make the following claim. If with probability at least $\eta_{1}/2$, there exists certain \overline{\text{\boldmath\theta}}\in\Theta_{L,M} such that at least $(1/2+\eta_{2}/2)n$ examples are correctly classified, i.e.,

then we have Nd=\Omega_{d}\big{(}\frac{n}{\log(LM)}\big{)}.

To prove this claim, we treat the input \text{\boldmathx}_{i} as deterministic. We derive

which is proved via the covering number argument (see Lemma 28). By Hoeffding’s inequality, we have

Since we assume that the probability of the event in (174) is at least $\eta_{1}$, we take the logarithm and deduce

It then follows that Nd=O_{d}\big{(}\frac{n}{\log(LM+1)}\big{)}.

where (i) is because the mean is no larger than the maximum and (ii) is because \max_{\overline{\text{\boldmath\theta}}\in\Theta_{L,M}}[I_{\overline{\text{\boldmath\theta}}}] takes value or $1$. Combining this with (175), we deduce that with probability at least $1-\eta_{1}/2$, there exists an \overline{\text{\boldmath\theta}}\in\Theta_{L,M} such that |f_{\text{\boldmath\theta}}(\text{\boldmathx}_{i})-f_{\overline{\text{\boldmath\theta}}}(\text{\boldmathx}_{i})|<\delta for all $i\in\mathcal{I}^{\prime}$ where $\mathcal{I}^{\prime}\subset[n]$ satisfies $|\mathcal{I}^{\prime}|\geq(1-\eta_{2}/2)n$.

Note that $|\mathcal{I}\cap\mathcal{I}^{\prime}|\geq|\mathcal{I}|+|\mathcal{I}^{\prime}|-n\geq(1/2+\eta_{2}/2)n$. Therefore, the assumption of the discretized case, namely (1), is satisfied; and hence we obtain the desired lower bound.

where we used Cauchy-Schwarz inequality in (i).

Taking $t=\sqrt{2\log(16/\eta_{1})}$ yields the bound

with probability at least $1-\eta_{1}/8$, where we used the assumption that $|\sigma(0)|\leq C_{0}$.

ii) Bounding $T_{i,2}$. By assumption, $\sigma$ has weak derivatives, so we have

Recall the Assumption 3.2 on the activation function $|\sigma^{\prime}(z)|\leq B(1+|z|)^{B}$. We have $\max_{|z|\leq 2L\sqrt{d}}|\sigma^{\prime}(z)|\leq B[1+(2L\sqrt{d})^{B}]\leq 2B(2L\sqrt{d})^{B}$. Therefore,

We take $t=CL(2L\sqrt{d})^{B}\sqrt{N}$ where $C>0$ is a sufficiently large constant so that the above probability upper bound (right-hand side) is smaller than $\eta_{1}\eta_{2}/16$. Denote the event $\mathcal{E}_{i}$ as

iii) Bounding $T_{i,3}$. By the assumption on $\sigma^{\prime}$, we can write

By the assumption on $\sigma^{\prime}$, we have $\max_{|z|\leq 2L\sqrt{d}}|\sigma^{\prime}(z)|\leq B[1+(2L\sqrt{d})^{B}]\leq 2B(2L\sqrt{d})^{B}$. Therefore, we can bound $T_{i,3}$ as follows. For each $i\in[n]$,

which is a consequence of Bernstein’s inequality (see [Ver10] Thm. 5.39 for example). Taking the union bound over $i$, (178) holds for all $i\in[n]$ with probability at least $1-2ne^{-cd}-2ne^{-cN}$.

(iv) Combining three bounds. Finally, combining the bounds on $T_{i,1}$, $T_{i,2}$, and $T_{i,3}$, we obtain that with probability at least $1-\eta_{1}/4-4n(e^{-cN}+e^{-cd})-2e^{-n^{2}/2}$,

Under the asymptotic assumption \log n=o_{d}\big{(}\min\{N,d\}\big{)}, we have $4n(e^{-cN}+e^{-cd})=o_{d}(1)$, so there exists a sufficient large $d_{0}$ such that $4n(e^{-cN}+e^{-cd})+2e^{-n^{2}/2}\leq\eta_{1}/4$ if $d>d_{0}$. We choose $M=C\delta^{-1}\cdot 2L(L\sqrt{d})^{B}$ (where the $C$ has the same value as in Eq. 179) and get

with probability $1-\eta_{1}/2$. This proves the claim. Note that with this choice of $M$, \log(LM+1)=O_{d}\big{(}\log(dL/\delta)\big{)} so the lower bound is obtained.

The cardinality of the discrete set $\Theta_{L,M}$ defined in (172) have the bound

By the volume argument, we have the bound

where in (i) we used the formula of the volume of a Euclidean ball and Stirling’s approximation.

Recall that $\mathcal{D}_{M}=\{0,\pm\frac{1}{M},\pm\frac{2}{M},\ldots\}$. To apply this result to bounding $|\Theta_{L,M}|$, first we observe that

Suppose \text{\boldmatha}_{1},\text{\boldmatha}_{2} lie in the set on the RHS of (181) and \text{\boldmatha}_{1}\neq\text{\boldmatha}_{2}. Then, by the definition of $\mathcal{D}_{M}$, we must have \|\text{\boldmatha}_{1}-\text{\boldmatha}_{2}\|_{\infty}>\frac{1}{2M}. This means that the cardinality of the set on the RHS of (181) is bounded by the packing number $D(B^{N}(\sqrt{N}\,L),\|\cdot\|_{\infty},\frac{1}{2M})$. By (180), we get an upper bound on the cardinality

Similarly, we can bound the cardinality of each of the $N$ sets in (182) by

Recall that $N=N(d)\to\infty$ as $d\to\infty$, so $o_{N}(1)$ in (183) can be replaced by $o_{d}(1)$. Combining (183) and (184), we obtain

References