Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration

Introduction

A number of statistical learning methods can be viewed as a combination of two steps: featurization and training. Featurization maps sample points into a convenient ‘feature space’ ${\mathcal{H}}$ (a vector space) via a featurization map ${\bm{\phi}}:{\mathcal{X}}\to{\mathcal{H}}$, ${\bm{x}}_{i}\mapsto{\bm{\phi}}({\bm{x}}_{i})$. Training fits a model that is linear in the feature space: $\hat{f}({\bm{x}})=\langle{\bm{a}},{\bm{\phi}}({\bm{x}})\rangle_{{\mathcal{H}}}$. In this paper we will be concerned with a relatively simple method for training, ridge regression:

Here it is implicitly assumed that ${\mathcal{H}}$ is an Hilbert space, and therefore ${\bm{a}}\in{\mathcal{H}}$ and $\langle\,\cdot\,,\,\cdot\,\rangle_{{\mathcal{H}}}$, $\|\,\cdot\,\|_{{\mathcal{H}}}$ are the scalar product and norm in ${\mathcal{H}}$.

It is useful to discuss a few examples of this paradigm, some of which will play a role in what follows (we refer to Section 2.1 for formal definitions).

Here $\langle f,g\rangle_{n}:=n^{-1}\sum_{i=1}^{n}f({\bm{x}}_{i})g({\bm{x}}_{i})$ denotes the scalar product with respect to the empirical measure.

Because of the connection to two-layers neural networks (see below) we shall refer to $N$ as the ‘number of neurons’ (although, ‘number of parameters’ would be more appropriate), and to $\sigma$ as the ‘activation function.’ The resulting function $\hat{f}$ takes the form

We will refer to the procedure defined by Eq. (1) with ${\bm{\phi}}$ the random feature map defined here as ‘random features ridge regression’ (RFRR). RFRR is closely related to KRR. First of all, we can view RFRR as an example of KRR, with kernel

Notice however that the kernel $H_{N}$ has finite rank and is random, because of the random features ${\bm{\theta}}_{1},\dots,{\bm{\theta}}_{N}$.

Second, for large $N$, we can expect $H_{N}$ to be a good approximation of its expectation

Hence, for large $N$, we expect RFRR to have similar generalization properties as the underlying RKHS, while possibly exhibiting lower complexity because it only operates on $N\times n$ matrices (instead of $n\times n$ matrices as for KRR).

Neural networks in the linear (lazy) regime. The methods described above fit the general paradigm of Eq. (1). Training does not affect the feature map ${\bm{\phi}}$. The model $\hat{f}_{\lambda}(\,\cdot\,)$ is linear in ${\bm{y}}$, as a consequence of the fact that the loss is quadratic (see also Eq. (2)). In contrast, neural networks aim at learning the best feature representation of the data. The feature map changes during training, and indeed there is no clear separation between the feature map ${\bm{\phi}}({\bm{x}})$ and the coefficients ${\bm{a}}$.

Apart from the zero-th order term $f({\bm{x}};{\bm{\theta}}_{0})$ (which has no free parameters, and hence plays the role of an offset), this linearized model takes the same form $\hat{f}({\bm{x}})=\langle{\bm{a}},{\bm{\phi}}({\bm{x}})\rangle$. The featurization map is given by ${\bm{\phi}}({\bm{x}})=\nabla_{{\bm{\theta}}}f({\bm{x}};{\bm{\theta}}_{0})$. We refer to the model ${\bm{x}}\mapsto\langle{\bm{a}},\nabla_{{\bm{\theta}}}f({\bm{x}};{\bm{\theta}}_{0})\rangle$ as the neural tangent (NT) model.

Notice that the NT featurization map is random, because of the random initialization ${\bm{\theta}}_{0}$. However, in general it does not take the form of the RF model, because the entries of $\nabla_{{\bm{\theta}}}f({\bm{x}};{\bm{\theta}}_{0})$ are not independent. Despite this important difference, we expect key properties of the RF model to generalize to suitable classes of NT models. Examples of this phenomenon were studied recently in [GMMM19, MZ20].

In particular our results allow to answer in a quantitative way two sets of key questions that emerge from the above discussion:

How does the test error of KRR depends on the sample size $n$, on the target function $f$, and on the kernel $H$? While this question has attracted considerable attention in the past (see Section 1.3 for an overview), a very precise answer can be given in the present setting.

How does the test error of RFRR depend on the sample size $n$, and the number of neurons $N$? In particular, for a given sample size, how big $N$ should be to achieve the same error as for the associated KRR (which corresponds formally to $N=\infty$)?

How do the answers to the previous questions depend on the regularization parameter $\lambda$? In particular, in which cases the optimal test error is achieved by choosing $\lambda\to 0$, i.e. by using the minimum norm interpolator to the training data?

Let us emphasize that the second question is technically more challenging than the first one, because it amounts to studying KRR with a random kernel. The setting introduced here is particularly motivated by the objective to address Q2 (and its ramifications in Q3). Indeed, to the best of our knowledge, we provide the first set of results on the optimal choice of the overparametrization $N/n$ under polynomial scalings of $N,n,d$.

2 Summary of main results

Before summarizing our results, it is useful to describe informally our assumptions: we refer to Sections 2.2 and 3.2 for a formal statement of the same assumptions. We consider $({\bm{x}}_{i})_{i\leq n}\sim_{iid}\nu$ with $\nu$ a probability distribution of the covariates space ${\mathcal{X}}$, and $y_{i}=f({\bm{x}}_{i})+\varepsilon_{i}$, where $f$ is the target function and $\varepsilon_{i}\sim{\sf N}(0,\sigma_{\varepsilon}^{2})$ independent of ${\bm{x}}_{i}$ is noise.

We will consider sequences of such problems indexed by an integer $d$, and characterize their behavior as $N,n,d\to\infty$. In applications, $d$ typically corresponds to the dimension of the covariates space ${\mathcal{X}}$. In this informal summary, we drop any reference to $d$ for simplicity.

We next describe informally our key assumptions, which depends on integers $({\mathsf{m}},{\mathsf{M}},u)$, with $u\geq\max({\mathsf{M}},{\mathsf{m}})$. (For the sake of simplicity, we omit some assumptions of a more technical nature.)

Concentration of diagonal elements of the kernels. Denote by $H_{>{\mathsf{m}}}$ the kernel obtained from $H$ by setting to zero the eigenvalues $\lambda_{1},\dots,\lambda_{\mathsf{m}}$. We require that the diagonal elements $\{H_{>{\mathsf{m}}}({\bm{x}}_{i},{\bm{x}}_{i})\}_{i\leq n}$ concentrate around their expectation with respect to the measure $\nu$ on ${\mathcal{X}}$. Analogously, we require the diagonal elements $\{U_{>{\mathsf{M}}}({\bm{\theta}}_{i},{\bm{\theta}}_{i})\}_{i\leq N}$ to concentrate around their expectation.

This assumption amounts to a condition of symmetry: most points ${\bm{x}}$ in the support of $\nu$ are roughly equivalent, in the sense of having the same value of $H_{>{\mathsf{m}}}({\bm{x}},{\bm{x}})$, and similarly for most ${\bm{\theta}}$ in the support of $\nu$.

Spectral gap. Recall that $(\lambda_{j}^{2})_{j\geq 1}$ denote the eigenvalues of the kernel $H$ in decreasing order. We then assume one of the following two conditions to hold:

Undeparametrized regime. We have $N\ll n$ and

Overparametrized regime. We have $n\ll N$ and

This assumption is ensures a clear separation between the subspace of ${\mathcal{D}}_{d}$ which is estimated accurately (spanned by the eigenfunction of $H$ corresponding to the top eigenvalues) and the subspace that is estimated trivially by (corresponding to the low eigenvalues of $H$.) As we will see, a spectral gap condition holds for classical high-dimensional examples. On the other hand, we believe it should be possible to avoid this condition at the price of a more complicate characterization of the risk, and indeed we do not require it for KRR.

As explained above, KRR attempts to estimate accurately the projection of the target function $f_{*}$ onto the top eigenvectors of the kernel $H$, and shrinks to zero its other components. RFRR behaves similarly, except that it only constructs a finite rank approximation of the kernel $H$. How many components of the target function are estimated accurately? There are of course two limiting factors: the statistical error which depends on the sample size $n$, and the approximation error which depends on the number of neurons $N$.

It turns out that, in the present setting, the interplay between $n$ and $N$ takes a particularly simple form. In a nutshell what matters is the smaller of $n$ and $N$. If $n\ll N$, then the statistical error dominates and ridge regression estimates correctly the projection of $f_{*}$ onto the top ${\mathsf{m}}$ eigenfunctions of $H$ (where ${\mathsf{m}}$ is defined per Eq. (8)). If on the other hand $N\ll n$, then the approximation error dominates and ridge regression estimates correctly the projection of $f_{*}$ onto the top ${\mathsf{M}}$ eigenfunctions of $H$ (where ${\mathsf{M}}$ is defined per Eq. (7)).

This characterization implies a relatively simple answer to questions Q1, Q2, and Q3, which we posed in the previous section. We summarize some of the insights that follow from this result.

As mentioned above, Eq. (9) can be restated as saying that (for the special case $N=\infty$), $\hat{f}_{\lambda}({\bm{x}})\approx{\mathsf{P}}_{\leq{\mathsf{m}}}f_{*}({\bm{x}})$. Indeed, we will prove a stronger result, which does not require the spectral gap assumption of Eq. (8). The KRR estimator $\hat{f}_{\lambda}$ is well approximated by the KRR estimator for the population problem ($n=\infty$), but with a larger value of the ridge regularization $\gamma>\lambda$. In other words KRR acts as a shrinkage operator along the eigenfunctions of the kernel.

In random features models, we are free to choose the number of neurons $N$. Equation (9) indicates that any choice of $N$ has roughly the same test error (which is also the test error of KRR) as long as $N\gg n$. This is interesting in both directions. First, the test error does not deteriorate as the number of parameters increases, and becomes much larger than the sample size. This contrasts with a naive measure of the model complexity: indeed, counting the number of parameters would naively suggest that $N\gg n$ might hurt generalization. Second, the error does not improve with overparametrization either, as long as $N\gg n$.

At what level of overparametrization should we operate? In view of the previous point, it is sufficient to use a model with a number of parameters much larger than the sample size (formally, $N\geq n^{1+\delta}$ for some $\delta>0$, although this specific condition is mainly dictated by our proof technique). Further overparametrization does not improve the statistical behavior.

Let us also note that —as proven in [MM19]— choosing $N/n=:\psi=O(1)$ can lead to sub-optimal test error, with the suboptimality vanishing if $\psi\to\infty$ after, $N,n\to\infty$.

3 Related literature

The test error of KRR was studied by a number of authors in the past [CDV07, JŞS+20], [Wai19, Theorem 13.17]. In particular, [CDV07] establishes that KRR achieves minimax optimal rates over certain subclasses of the associated RKHS. However these results require a strictly positive ridge regularizer (and hence do not cover interpolation) and characterize the decay of the error as $n\to\infty$ in fixed dimension $d$. In contrast our focus is on the case in which both $d$ and $n$ grow simultaneously. Further, we provide upper and lower bounds that hold pointwise (for a given target function $f_{*}$) while earlier work mostly establish pointwise upper bound and minimax lower bounds (for the worst case $f_{*}$). The recent work [JŞS+20] also derived pointwise upper and lower bounds for kernel ridge regression (but with strictly positive ridge regularizer), which is very similar to our Theorem 4. However, these results are based on a universality assumption whose validity is unclear in specific settings.

Recently, the ridge-less (interpolation) limit of KRR was studied by Liang, Rakhlin and Zhai [LR20, LRZ19]. Again, these authors provide minimax upper bounds that hold within the RKHS, holding for inner product kernel, when the feature vectors ${\bm{x}}$ have independent coordinates. Their results are related but not directly comparable to ours.

The complexity of training kernel machine scales at least quadratically in the sample size. This has motivated the development of randomized techniques to lower the complexity of training and testing. While our focus is on random features methods, alternative approaches are based on subsampling the columns-rows of the empirical kernel matrix, see e.g. [Bac13, AM15, RCR15]. In particular, [RCR15] compares the prediction errors using the sketched and the full kernel matrices, and shows that —for a fixed RKHS— it is sufficient to use a number of rows/columns of the order of the square root of the sample size in order to achieve the minimax rate over that RKHS.

The generalization properties of random features methods have been studied in a smaller number of papers [RR09, RR17, MWW20]. Rahimi and Recht [RR09] proved an upper bound of the order $1/\sqrt{N}+1/\sqrt{n}$ on the generalization error. The insight provided by this bound is similar to one of our points: about $N\asymp n$ neurons are sufficient for the error to be of the same order as for $N\to\infty$. On the other hand, [RR09] proves only a minimax upper bound, it is limited to Lipschitz losses, and, crucially, requires the coefficients $\max_{i\leq N}|a_{i}|\leq C$ so that $\|{\bm{a}}\|_{2}^{2}=O(N)$. In contrast, in the present setting, we typically have $\|{\bm{a}}\|_{2}^{2}=\Theta(nN)$ The case of square loss was considered earlier by Rudi and Rosasco [RR17] who proved that, for a target function $f_{*}$ in the RKHS, $N=C\sqrt{n}\log n$ is sufficient to learn a random features model with test error of order $1/\sqrt{n}$. These authors interpret this finding as implying that roughly $\sqrt{n}$ random features are sufficient: we will discuss the difference between their setting and ours in Section 2.3.

Finally, [Bac15] studies optimized distributions for sampling the random features, while [YLM+12] provides a comparison between random features approaches and subsampling of the kernel matrix.

As pointed out above, we find that taking $\lambda\to 0$ yields nearly optimal test error, within our setting. Optimality of minimum norm interpolators has attracted considerable attention recently [BHMM19, BRT19, HMRT19, BLLT20, TB20]. In particular our results point in the same direction as the general analysis of ridge regression in [BLLT20, TB20]. Note however that the general results of [BLLT20, TB20] do not apply to the present setting because they require subgaussian features ${\bm{\phi}}({\bm{x}}_{i})$. Further, they only provide upper and lower bounds that match up to factors depending on the condition number of a certain random matrix. In contrast, our characterization is specialized to the random features setting, does not require subgaussianity, and holds up to additive errors that are negligible compared to the null risk.

The present paper solves a number of open problems that were left open in our earlier work [GMMM19]. First of all, [GMMM19] only considered the cases $n=\infty$ (approximation error of random features models) or $N=\infty$ (generalization error of KRR). Here instead we establish the complete picture for both $n$ and $N$ finite. Second, [GMMM19] assumed a special data distribution ($\nu$ was the uniform distribution over the $d$-dimensional sphere), a special structure for the kernel (inner product kernels), and a special type of activation functions (depending on the inner product $\langle{\bm{\theta}},{\bm{x}}\rangle)$). The present paper considers general data distribution, kernel, and activation functions, under a set of assumptions that covers the previous example as a special case. Finally, the proofs of [GMMM19] made use of the moment method, which is difficult to generalize beyond special examples. Here we use a decoupling approach and matrix concentration methods which are significantly more flexible.

The results of [GMMM19] were generalized to certain anisotropic distributions in [GMMM20]. For the inner product activation functions on the sphere, the precise asymptotics (for $N,n,d\to\infty$ with $N/d\to\psi_{1}$, $n/d\to\psi_{2}$, $\psi_{1},\psi_{2}\in(0,\infty)$) of generalization error of random features models was calculated in [MM19].

4 Notations

Generalization error of random features ridge regression

In this section, we present our results on the generalization error of random features models. We begin in Section 2.1 by introducing the general abstract setting in which we work, and some of its basic properties. We then state our assumptions in Section 2.2, and state our main theorem (Theorem 1) in Section 2.3.

We consider two sequences of Polish probability spaces $({\mathcal{X}}_{d},\nu_{d})$ and $(\Omega_{d},\tau_{d})$, indexed by an integer $d$. We denote by $L^{2}({\mathcal{X}}_{d})=L^{2}({\mathcal{X}}_{d},\nu_{d})$ the space of square integrable functions on $({\mathcal{X}}_{d},\nu_{d})$, and by $L^{2}(\Omega_{d})=L^{2}(\Omega_{d},\tau_{d})$ the space of square integrable functions on $(\Omega_{d},\tau_{d})$. Since $({\mathcal{X}}_{d},\nu_{d})$ and $(\Omega_{d},\tau_{d})$ are standard probability spaces [Dud18, Theorem 13.1.1], it follows that $L^{2}({\mathcal{X}}_{d})$ and $L^{2}(\Omega_{d})$ are separable.

While in simple examples we might assume ${\mathcal{D}}_{d}=L^{2}({\mathcal{X}}_{d})$, the extra flexibility afforded by a general subspace ${\mathcal{D}}_{d}\subseteq L^{2}({\mathcal{X}}_{d})$ allows to model some important applications [MMM21].

By Cauchy-Schwartz inequality, we have $U_{d}\in L^{2}(\Omega_{d}\times\Omega_{d})$ and $H_{d}\in L^{2}({\mathcal{X}}_{d}\times{\mathcal{X}}_{d})$.

(Here convergence holds in operator norm.) In terms of the kernel, these identities read

Here convergence holds in $L^{2}({\mathcal{X}}_{d}\times\Omega_{d})$, $L^{2}(\Omega_{d}\times\Omega_{d})$, and $L^{2}({\mathcal{X}}_{d}\times{\mathcal{X}}_{d})$.

where $\|\cdot\|_{{\mathcal{H}}}$ denotes the RKHS norm associated to ${\mathcal{H}}$. In particular, ${\mathcal{H}}$ is dense in ${\mathcal{D}}_{d}$, provided $\lambda_{d,j}^{2}>0$ for all $j$.

2 Assumptions

Let ${\bm{\Theta}}=({\bm{\theta}}_{i})_{i\in[N]}\sim_{iid}\tau_{d}$. We define the random features function class to be

Note that the factor $1/N$ is immaterial here, and only introduced in order to match the definition of feature map and scalar product in Section 1.1.

We observe pairs $(y_{i},{\bm{x}}_{i})_{i\in[n]}$, with $({\bm{x}}_{i})_{i\in[n]}\sim_{iid}\nu_{d}$, and $y_{i}=f_{d}({\bm{x}}_{i})+\varepsilon_{i}$, $f_{d}\in L^{2}({\mathcal{X}}_{d})$ and $\varepsilon_{i}\sim{\sf N}(0,\sigma_{\varepsilon}^{2})$ independently. We fit the coefficients $(a_{i})_{i\leq N}$ using ridge regression, cf. Eq. (1) that we reproduce here

We allow $\lambda$ to depend on the dimension parameter $d$. The test error is given by

We say that the sequence of activation functions $\{\sigma_{d}\}_{d\geq 1}$ satisfies the Feature Map Concentration Property (FMCP) with respect to the sequence $\{(N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d))\}_{d\geq 1}$ if there exists a sequence $\{u(d)\}_{d\geq 1}$ with $u(d)\geq\max({\mathsf{M}}(d),{\mathsf{m}}(d))$ such that the following hold.

(Hypercontractivity of finite eigenspaces)

(Hypercontractivity of finite eigenspaces on ${\mathcal{D}}_{d}$.) For any integer $k\geq 1$, there exists $C$ such that, for any $g\in{\mathcal{D}}_{d,\leq u(d)}={\rm span}(\psi_{s},1\leq s\leq u(d))$, we have

(Hypercontractivity of finite eigenspaces on ${\mathcal{V}}_{d}$.) For any integer $k\geq 2$, there exists $C^{\prime}$ such that, for any $g\in{\mathcal{V}}_{d,\leq u(d)}={\rm span}(\phi_{s},1\leq s\leq u(d))$, we have

(Properly decaying eigenvalues.) There exists a fixed $\delta_{0}>0$, such that , for all $d$ large enough

(Hypercontractivity of the high degree part.) Let $\sigma_{d,>u(d)}$ corresponds to the projection on the high degree part of $\sigma_{d}$. Then there exists a fixed $\delta_{0}>0$ and an integer $k$ such that

(Concentration of diagonal elements) For $({\bm{x}}_{i})_{i\in[n(d)]}\sim_{iid}\nu_{d}$ and $({\bm{\theta}}_{i})_{i\in[N(d)]}\sim_{iid}\tau_{d}$, we have

The second assumption (assumption $(b)$) requires that the eigenvalues of kernel operators do not decay too rapidly. If this is not the case, the RKHS will be very close to a low-dimensional space. For instance, if $\lambda^{2}_{d,k}\asymp k^{-2\alpha}$, $\alpha>0$, then this condition holds as long as we take $u(d)\geq\max(N(d),n(d))^{2+\delta_{0}}$ for some $\delta_{0}>0$.

Finally, assumption $(d)$ concerns the diagonal elements of the kernel matrices. They require the truncated kernel functions $H_{d,>{\mathsf{m}}(d)}$ and $U_{d,>{\mathsf{M}}(d)}$ evaluated on covariates and weight vectors to have nearly constant diagonal values.

The second set of assumptions concerns the spectrum of the kernel operator, defined by the sequence of eigenvalues $(\lambda_{d,j}^{2})_{j\geq 1}$. We require that the spectrum has a gap: the location of this gap dictates the relationship between $N(d)$ and ${\mathsf{M}}(d)$ and between $n(d)$ and ${\mathsf{m}}(d)$.

We say that the sequence of activation functions $\{\sigma_{d}\}_{d\geq 1}$ has a spectral gap at level $\{(N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d))\}_{d\geq 1}$ if one of the following conditions $(a)$, $(b)$ hold for all $d$ large enough.

(Overparametrized regime.) We have $N(d)\geq n(d)$ and

(Number of samples) There exists fixed $\delta_{0}>0$ such that ${\mathsf{m}}(d)\leq n(d)^{1-\delta_{0}}$ and

(Number of features) There exists fixed $\delta_{0}>0$ such that ${\mathsf{M}}(d)\leq N(d)^{1-\delta_{0}}$, ${\mathsf{M}}(d)\geq{\mathsf{m}}(d)$ and

(Underparametrized regime) We have $n(d)\geq N(d)$ and

(Number of features) There exists fixed $\delta_{0}>0$ such that ${\mathsf{M}}(d)\leq N(d)^{1-\delta_{0}}$ and

(Number of samples) There exists fixed $\delta_{0}>0$ such that ${\mathsf{m}}(d)\leq n(d)^{1-\delta_{0}}$, ${\mathsf{m}}(d)\geq{\mathsf{M}}(d)$ and

The assumption of a spectral gap is useful in that it leads to a clear-cut separation in our main statement below. For instance, in the overparametrized regime $n(d)\ll N(d)$, the projection of the target function onto ${\mathcal{D}}_{d,\leq{\mathsf{m}}(d)}$ is estimated with negligible error, while the projection onto ${\mathcal{D}}_{d,>{\mathsf{m}}(d)}$ is estimated with . If there was no spectral gap, the transition would not be as sharp. However, we expect this to affect only target functions with a large projection onto eigenfunctions whose indices are close to ${\mathsf{m}}(d)$. In this sense, while restrictive, the spectral gap assumption can be in fact a good model for a more generic situation.

3 A general theorem

We are now in position to state our main results for random features ridge regression.

Let $\{f_{d}\in{\mathcal{D}}_{d}\}_{d\geq 1}$ be a sequence of functions, ${\bm{X}}=({\bm{x}}_{i})_{i\in[n(d)]}$ and ${\bm{\Theta}}=({\bm{\theta}}_{j})_{j\in[N(d)]}$ with $({\bm{x}}_{i})_{i\in[n(d)]}\sim\nu_{d}$ and $({\bm{\theta}}_{j})_{j\in[N(d)]}\sim\tau_{d}$ independently. Let $y_{i}=f_{d}({\bm{x}}_{i})+\varepsilon_{i}$ and $\varepsilon_{i}\sim_{iid}{\sf N}(0,\sigma_{\varepsilon}^{2})$ for some $\sigma_{\varepsilon}>0$. Let $\{\sigma_{d}\}_{d\geq 1}$ be a sequence of activation functions satisfying $\{(N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d))\}_{d\geq 1}$-FMCP (Assumption 1) and spectral gap at level $\{(N(d),{\mathsf{M}}(d),n(d),{\mathsf{m}}(d)))\}_{d\geq 1}$ (Assumption 2). Then the following hold for the test error of RFRR (see Eq. (17)):

The two limits $N=\infty$ and $n=\infty$ play a special role. For $N=\infty$, the random kernel $H_{N}({\bm{x}}_{1},{\bm{x}}_{2})=N^{-1}\sum_{i=1}^{N}\sigma({\bm{x}}_{1};{\bm{\theta}}_{i})\sigma({\bm{x}}_{2};{\bm{\theta}}_{i})$ converges to its expectation, and we recover KRR. While this case is not technically covered by Theorem 1, we establish the relevant characterization in Theorems 3 and 4.

In the case $n=\infty$ the generalization error vanishes, and we are left with the approximation error. This case is covered separately in Appendix A. In both these limit cases we confirm the result that would have been obtained by naively setting $N=\infty$ or $n=\infty$ in the last theorem.

Notice that the sample size $n$ and the number of neurons $N$ play a nearly symmetric role in this statement, and the smallest of the two determines the test error. An important insight follows: in the present setting, the test error is nearly insensitive to the number of neurons as long as we take $N\gg n$. If we want to minimize computational complexity subject to achieving nearly optimal generalization properties, we should operate, say, at $N\asymp n^{1+\delta}$ for some small $\delta>0$.

It is instructive to compare this result with [RR17] which instead suggests $N\asymp\sqrt{n}\log n$. While our setting differs from the one of [RR17] in a number of technical aspects, we believe that the core difference between the two results lies in the treatment of the target function $f_{d}$. Simplifying, the recommendation of [RR17] is based on two results, the second of which proved in [CDV07] (with an abuse of notation, we indicate the number of neurons and sample size as arguments of $R_{{\rm RF}}(f_{d})=R_{{\rm RF}}(f_{d};N,n)$, and use $N=\infty$ to denote the KRR limit case):

where $b\in(1,\infty)$ encodes the decay of eigenvalues of the kernelThe results of [CDV07, RR17] assume the weaker condition that $\inf_{g\in{\mathcal{H}}}\|f_{d}-g\|_{L^{2}}$ is achieved in ${\mathcal{H}}$: since ${\mathcal{H}}$ is dense in $L^{2}({\mathcal{X}}_{d})$ (provided the kernel is strictly positive definite), this is equivalent to $f_{d}\in{\mathcal{H}}$.. Now, considering the worst case decay $b\to 1$, the error rate achieved by RFRR, cf. Eq. (23), is of the same order as the one achieved by KRR, cf. Eq. (24).

Note several differences with respect to our results: $(i)$ The analysis of [RR17, CDV07] is minimax, over balls in the RKHS, while our results hold pointwise, i.e., for a given function $f_{d}$; $(ii)$ Optimality in [RR17] is established in terms of rates, i.e., up to multiplicative constant, while ours hold up to additive errors (multiplicative constants are exactly characterized); $(iii)$ The results of [RR17, CDV07] apply to a fixed RKHS (in particular, a fixed dimension $d$), while we study the case in which $d$ is large and $N,n,d$ are polynomially related.

Some of these distinction are also relevant in comparing our work to recent results on KRR. In particular points $(i)$ and $(ii)$ apply when comparing with [LR20, LRZ19].

4 Examples: The binary hypercube and the sphere

In order to apply Theorem 1, we make the following assumption about $\bar{\sigma}_{d}$.

There exists an integer $k$ and constants $c_{1}<1$ and $c_{0}>0$, $\delta_{0}>1/k$ such that $n\leq N^{1-\delta_{0}}$ or $N\leq n^{1-\delta_{0}}$ and $|\bar{\sigma}_{d}(x)|\leq c_{0}\exp(c_{1}x^{2}/(4k))$.

where ${\bm{e}}\in{\mathcal{A}}_{d}$ is a fixed vector (it is easy to see that these quantities do not depend on ${\bm{e}}$).

If ${\mathcal{A}}_{d}={\mathscrsfs Q}^{d}$, we have, for all $d$ large enough

Assumption $(a)$ requires $n$, $N$ to be well separated and a technical integrability condition. The latter is necessary for the hypercontractivity condition in Assumption 1.$(c)$ to make sense.

Equations (26) and (27) (Assumption $(b)$) are a quantitative version of a universality condition: if ${\overline{\mathsf{P}}}_{k}\bar{\sigma}_{d}(\langle{\bm{e}},\cdot\rangle/\sqrt{d})=0$ for some $k$, then linear combinations of $\bar{\sigma}_{d}$ can only span a linear subspace of $L^{2}({\mathcal{A}}_{d},\rho_{d})$. Equation (28) (Assumption $(b)$) requires the high degree part of $\bar{\sigma}_{d}$ to be non-vanishing (and therefore induce a non-zero regularization from the high degree non-linearity).

For ${\mathcal{A}}_{d}={\mathscrsfs Q}^{d}$, we further require Assumption $(c)$, namely that the last eigenvalues of $\bar{\sigma}_{d}$ decrease sufficiently fast. This is a necessary conditions to avoid pathological sequences $\{\bar{\sigma}_{d}\}_{d\geq 1}$ which are very rapidly oscillating.

If $\bar{\sigma}_{d}=\bar{\sigma}$ is independent of the dimension, then Assumptions $(b)$, $(c)$ are easy to check:

The third part of Assumption $(b)$ (Eq. (28)) amounts to requiring $\bar{\sigma}$ not to be a degree-$(2\max({\mathsf{s}},{\mathsf{S}})+1)$ polynomial.

In Appendix D.2 we check that Assumption $(c)$ holds if $\bar{\sigma}$ is smooth and there exists $c_{0}>0$ and $c_{1}<1$ constants such that the $(2\max({\mathsf{s}},{\mathsf{S}})+2)$-th derivative verifies $|\bar{\sigma}^{(2\max({\mathsf{s}},{\mathsf{S}})+2)}(x)|\leq c_{0}\exp(c_{1}x^{2}/4)$.

Let $\{f_{d}\in L^{2}({\mathcal{A}}_{d},\rho_{d})\}_{d\geq 1}$ be a sequence of functions. Let ${\bm{\Theta}}=({\bm{\theta}}_{i})_{i\in[N]}$ with $({\bm{\theta}}_{i})_{i\in[N]}\sim\rho_{d}$ independently and ${\bm{X}}=({\bm{x}}_{i})_{i\in[n]}$ with $({\bm{x}}_{i})_{i\in[n]}\sim\rho_{d}$ independently. Let $y_{i}=f_{d}({\bm{x}}_{i})+\varepsilon_{i}$ and $\varepsilon_{i}\sim_{iid}{\sf N}(0,\sigma_{\varepsilon}^{2})$ for some $\sigma_{\varepsilon}>0$. Assume $d^{{\mathsf{s}}+\delta_{0}}\leq n\leq d^{{\mathsf{s}}+1-\delta_{0}}$ and $d^{{\mathsf{S}}+\delta_{0}}\leq N\leq d^{{\mathsf{S}}+1-\delta_{0}}$ for fixed integers ${\mathsf{s}},{\mathsf{S}}$ and for some $\delta_{0}>0$. Let $\{\bar{\sigma}_{d}\}_{d\geq 1}$ satisfy Assumption 3 at level $({\mathsf{s}},{\mathsf{S}})$. Then the following hold for the test error of RFRR (see Eq. (17)):

Assume $N\geq nd^{\delta}$ for some $\delta>0$. Then for any regularization parameter $\lambda=O_{d}(1)$ (including $\lambda=0$ identically), any $\eta>0$ and $\varepsilon>0$, we have, with high probability,

Assume $n\geq Nd^{\delta}$ for some $\delta>0$. Then, for any regularization parameter $\lambda=O_{d}(n/N)$ (including $\lambda=0$ identically), $\eta>0$ and $\varepsilon>0$, we have, with high probability,

As mentioned in the introduction, [GMMM19] proves this theorem in the cases $n=\infty$ (RF approximation error) and $N=\infty$ (generalization error of KRR), for the uniform measure on the sphere. The general case follows here as a consequence of Theorem 1.

which matches the assumptions in Theorem 2.

We plot the observed average risk in the sample-size/number-of-parameters plane whose axes are $\log n/\log d$ and $\log N/\log d$ (corresponding to the exponents in the polynomial relation between $n$ and $d$, and between $N$ and $d$). Several prominent features of this plot are worth of note:

The risk has a large peak for $N\approx n$. This phenomenon was characterized precisely in the proportional regime $N\asymp d$, $n\asymp d$ in [HMRT19, MM19].

The plot appears completely symmetric under exchange of $N$ and $n$: the number of parameters and sample size plays the same role in limiting the generalization abilities, as anticipated by Theorem 1 and Theorem 2.

The risk is bounded away from zero even for $N,n\asymp d^{3}$. Indeed, Theorem 2 implies that consistent estimation would require $N,n\gg d^{4}$ in this case.

Finally, for a fixed $n$, near optimal test error is achieved when $N\asymp n^{1+\delta_{*}}$, for $\delta_{*}$ a small positive constant.

Generalization error of kernel machines

Formally, kernel ridge regression (KRR) corresponds to the limit $N\to\infty$ of random feature ridge regression. Despite this, we cannot apply directly Theorem 1 with $N=\infty$. We state therefore a separate theorems for kernel methods. As a side benefit, we establish somewhat stronger results in this case. In particular:

We simplify the set of assumptions (in particular, the assumptions concern only $H_{d}$ and not the activation function $\sigma_{d}$, as they should).

We prove a risk lower bound, Theorem 3, that holds for general kernel methods, not only KRR.

Crucially, we remove the spectral gap assumption. In this more general setting, the risk of KRR is not approximated by the square norm of the projection of $f_{d}$ orthogonal to the leading eigenfunctions of the kernel. We instead obtain an approximation in terms of a population-level ridge regression problem, with an effective value of the regularization parameter, which we determine.

Throughout this section, the setting is the same as in the previous one: we observe i.i.d. data $(y_{i},{\bm{x}}_{i})_{i\in[n]}$, with feature vectors ${\bm{x}}_{i}$ from the probability space $({\mathcal{X}}_{d},\nu_{d})$. Responses are given by $y_{i}=f_{d}({\bm{x}}_{i})+\varepsilon_{i}$, $f_{d}\in{\mathcal{D}}_{d}$ and $\varepsilon_{i}\sim{\sf N}(0,\sigma_{\varepsilon}^{2})$ independently of ${\bm{x}}_{i}$.

We introduce some general background in Section 3.1, then state our assumptions in Section 3.2, and formally state our results in Sections 3.3 and 3.4.

Given a choice of this square root, we can rewrite the estimator (36) as $\hat{f}_{\lambda}({\bm{x}})=f({\bm{x}};{\hat{a}}_{\lambda})$, where ${\hat{a}}_{\lambda}\in L^{2}(\Omega_{d};\nu_{d})$ and

This can be informally seen as the $N\to\infty$ limit of Eq. (16) if we choose the square loss function.

2 Assumptions on the kernel

As for the case of RFRR, we collect our assumptions in two groups. The first one is mainly concerned with the concentration properties of the kernel, which are quantified in terms of the sequences of integers $n(d)$, ${\mathsf{m}}(d)$.

(Hypercontractivity of finite eigenspaces.) For any fixed $q\geq 1$, there exists a constant $C$ such that, for any $h\in{\mathcal{D}}_{d,\leq u(d)}={\rm span}(\psi_{s},1\leq s\leq u(d))$, we have

(Properly decaying eigenvalues.) There exists fixed $\delta_{0}>0$, such that, for all $d$ large enough,

(Concentration of diagonal elements of kernel) For $({\bm{x}}_{i})_{i\in[n(d)]}\sim_{iid}\nu_{d}$, we have:

The next condition essentially connects the sample size $n(d)$ to the eigenvalue index ${\mathsf{m}}(d)$, via the eigenvalues sequence.

There exists fixed $\delta_{0}>0$, such that

There exists fixed $\delta_{0}>0$, such that

Unlike in the case of RFRR, we do not require the existence of a spectral gap, but we assume two different upper bounds $n(d)$ to hold simultaneously. In many cases of interest, the right hand sides of (45) and (46) have roughly the same value, which is given by the number of eigenvalues between $\lambda_{d,{\mathsf{m}}(d)+1}$ and $c_{0}\lambda_{d,{\mathsf{m}}(d)+1}$ for a small $c_{0}$ (counting degeneracy). The technical requirement $(b)$ is mild and we do not know of any interesting counterexample.

3 Lower bound for general kernel methods

Consider any regression method of the form (36). By the representer theorem, there exist coefficients $\hat{\zeta}_{1},\dots,\hat{\zeta}_{n}$ such that

We are therefore led to define the following data-dependent prediction risk function for kernel methods

This is a lower bound on the prediction error of any kernel methods of the form (36).

The next theorem provides a lower bound on the generalization of kernel methods that is a consequence of the approximation bound in Theorem 5.$(a)$ derived for the random features model, in Appendix A.

This follows immediately from Theorem 5 $(a)$ stated in Appendix A. Indeed, setting $\sigma_{d}({\bm{x}},{\bm{x}}^{\prime})=H_{d}({\bm{x}},{\bm{x}}^{\prime})$, we obtain $R_{H}(f_{d},{\bm{X}})=R_{{\rm RF}}(f_{d},{\bm{X}})$, whence the claim follows by applying Eq. (57). ∎

Notice that $R_{H}({\mathsf{P}}_{\leq{\mathsf{m}}(d)}f_{d},{\bm{X}})\geq 0$ by construction and therefore this theorem immediately implies a lower bound of the test error of kernel ridge regression (cf. Eq. (37))

4 The risk of kernel ridge regression

where the kernel matrix ${\bm{H}}=(H_{ij})_{ij\in[n]}$ is given by $H_{ij}=H_{d}({\bm{x}}_{i},{\bm{x}}_{j})$, and ${\bm{y}}=(y_{1},\ldots,y_{n})^{\mathsf{T}}$.

It is convenient to state our main results in terms of an effective ridge regression estimator

Further, the ridge regression estimator $\hat{f}_{\lambda}$ is close to the effective estimator $\hat{f}_{\gamma^{\mbox{\tiny\rm eff}}}^{\mbox{\tiny\rm eff}}$, namely

The proof of Theorem 4 is deferred to Appendix C.

As mentioned above, we do not assume here any eigenvalue gap condition. However, formulas simplify if we assume an eigenvalue gap, e.g.:

Under this additional assumption, Theorem 4 implies the following simplified formula for the test error:

As anticipated, this coincides with the risk of RFRR, if we heuristically set $N=\infty$ in Theorem 1.

Acknowledgnements

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-2006489, IIS-1741162 and the ONR grant N00014-18-1-2729.

References

Appendix A Approximation error of random features model

In this section, we consider the approximation error of the random features function class. Formally, the approximation error can be seen as the generalization error of random features ridge regression for finite number of neurons $N<\infty$ and infinite data $n=\infty$. However, we cannot apply directly Theorem 1 with $n=\infty$. We therefore state a separate theorem. This is also used to prove the lower bound of Theorem 3 on the generalization error of general kernel methods.

In Section A.1, we state our assumptions and theorem. Sections A.2 and A.3 provide a proof of the theorem, while Section A.4 gathers key technical concentration results that will also be used in the proofs of Theorem 1 and Theorem 4.

Recall the definition of the random features function class (see Section 2.1): let ${\bm{\Theta}}=({\bm{\theta}}_{i})_{i\in[N]}\sim_{iid}\tau_{d}$,

We define the approximation error of the random features function class for a target function $f_{d}\in L^{2}({\mathcal{X}}_{d})$ as

Similarly to Sections 2.2 and 3.2, we will quantify our assumptions on the sequences of probability spaces $({\mathcal{X}}_{d},\nu_{d})$ and $(\Omega_{d},\tau_{d})$, and on the activation functions $\sigma_{d}\in L^{2}({\mathcal{X}}_{d}\times\Omega_{d})$, in terms of the sequences of integers $N(d),{\mathsf{M}}(d)$. We state the assumptions in two groups: Assumption 6 and Assumption 7 deal respectively with the concentration properties and the spectrum of the sequence of feature kernel operator $\{U_{d}\}_{d\geq 1}$ defined as

(Hypercontractivity of finite eigenspaces.) For any fixed $q\geq 1$, there exists $C$ such that, for any $g\in{\mathcal{V}}_{d,\leq u(d)}={\rm span}(\phi_{s},1\leq s\leq u(d))$, we have

(Properly decaying eigenvalues.) There exists a fixed $\delta_{0}>0$, such that

(Upper bound on the diagonal elements of the kernel) For $({\bm{\theta}}_{i})_{i\in[N(d)]}\sim_{iid}\tau_{d}$ and any $\delta>0$, we have

(Lower bound on the diagonal elements of the kernel) For $({\bm{\theta}}_{i})_{i\in[N(d)]}\sim_{iid}\tau_{d}$ and any $\delta>0$, we have

There exists a fixed $\delta_{0}>0$, such that

There exists a fixed $\delta_{0}>0$, such that ${\mathsf{M}}(d)\leq N(d)^{1-\delta_{0}}$ and

In Assumption 6.$(c)$, we can replace $U_{d,>{\mathsf{M}}(d)}$ by $U_{d,>u(d)}$ (see Lemma 7).

We are now in position to state our theorem on the approximation error of the random features function class. We state the lower and upper bounds and their assumptions separately.

Let $\{f_{d}\in{\mathcal{D}}_{d}\}_{d\geq 1}$ be a sequence of functions and ${\bm{\Theta}}=({\bm{\theta}}_{i})_{i\in[N(d)]}$ with $({\bm{\theta}}_{i})_{i\in[N(d)]}\sim\tau_{d}$ independently. Let $\{\sigma_{d}\}_{d\geq 1}$ be a sequence of activation functions satisfying Assumptions 6.(a) and 6.$(b)$ at level $\{{\mathsf{M}}(d)\}_{d\geq 1}$. Then the following hold for the approximation error of the random features class (see Eq. (56)):

(Lower bound) If $\{\sigma_{d}\}_{d\geq 1}$ satisfies further Assumptions 6.$(d)$ and 7.(a), then we have

(Upper bound) If $\{\sigma_{d}\}_{d\geq 1}$ satisfies further Assumptions 6.(c) and 7, then we have

Point $(a)$ is proved in Section A.2, while point $(b)$ is proved in Section A.3.

The lower bound on general kernel methods in Theorem 3 is obtained as a direct consequence of Theorem 5.(a), by taking $\sigma_{d}({\bm{x}},{\bm{x}}^{\prime})=H_{d}({\bm{x}},{\bm{x}}^{\prime})$. Indeed, it is easy to check that Eqs. (40) and (42) imply Assumptions 6.(a) and 6.$(b)$, Eq. (44) implies Assumptions 6.$(c)$ and 6.$(d)$, and Eq. (46) implies Assumption 7.(a).

A.2 Proof of Theorem 5.(a)𝑎(a): lower bound on the approximation error

Define the random vectors ${\bm{V}}=(V_{1},\ldots,V_{N})^{\mathsf{T}}$, ${\bm{V}}_{\leq{\mathsf{M}}}=(V_{1,\leq{\mathsf{M}}},\ldots,V_{N,\leq{\mathsf{M}}})^{\mathsf{T}}$, ${\bm{V}}_{>{\mathsf{M}}}=(V_{1,>{\mathsf{M}}},\ldots,V_{N,>{\mathsf{M}}})^{\mathsf{T}}$, with

Define the random matrix ${\bm{U}}=(U_{ij})_{i,j\in[N]}$, with

In what follows, we write $R_{{\rm App}}(f_{d})=R_{{\rm App}}(f_{d},{\bm{\Theta}})$ for the approximation error of the random features model, omitting the dependence on the weights ${\bm{\Theta}}$. By definition and a simple calculation, we have

where the last inequality used the fact that

By Eq. (60), to prove Theorem 5.$(a)$, we need to bound $\|{\bm{U}}^{-1}\|_{{\rm op}}\|{\bm{V}}_{>{\mathsf{M}}}\|_{2}^{2}$. This is achieved in the two following propositions.

Let $\{f_{d}\in{\mathcal{D}}_{d}\}$ be a sequence of target functions. Define ${\mathcal{E}}_{>{\mathsf{M}}}$ by

This is a direct consequence of Theorem 6.$(a)$. ∎

Next, by Proposition 2 and Assumption 6.$(d)$, for any fixed $\delta>0$ with $\delta<\delta^{\prime}$, we have

Combining Eq. (64) with Eq. (60) proves Theorem 5.$(a)$.

A.3 Proof of Theorem 5.(b)𝑏(b): upper bound on the approximation error

In the following, we would like to calculate the quantity $R_{{\rm App}}({\mathsf{P}}_{\leq{\mathsf{M}}}f_{d},{\bm{\Theta}})$. We have

where ${\bm{V}}_{\leq{\mathsf{M}}}=(V_{\leq{\mathsf{M}},1},\ldots,V_{\leq{\mathsf{M}},N})^{\mathsf{T}}$ and ${\bm{U}}=(U_{ij})_{ij\in[N]}$ with

By orthonormality of the $(\psi_{k})_{k\geq 1}$, we have

The last equation is by Lemma 1 which is stated and proved below. This proves the theorem.

Let Assumptions 6.$(a)$, 6.$(b)$, 6.$(c)$ and 7 hold. Then we have

By the Sherman-Morrison-Woodbury formula, we have

By Assumption 7.$(b)$, there exists $\delta_{0}>0$, such that

Combining the above equalities with Eq. (66) and choosing $\delta$ such that $0<\delta<\delta_{0}$, we have

Combining with Eq. (65) proves the lemma. ∎

A.4 Structure of the empirical kernel matrix

Let Assumptions 6.$(a)$, 6.$(b)$ and 7.$(a)$ hold. Let $({\bm{\theta}}_{i})_{i\in[N]}\sim\tau_{d}$ independently, and define ${\bm{U}}=(U_{ij})_{ij\in[N]}$ with

There exists a fixed $\delta^{\prime}>0$, such that

If further we assume ${\mathsf{M}}(d)\leq N(d)^{1-\delta_{0}}$ for a fixed $\delta_{0}>0$, then we have

For $S\subseteq\{1,2,3,\dots\}$, recall that

By decomposing the entries of ${\bm{U}}$ in the orthonormal basis $\{\phi_{j}\}_{j\geq 1}$, we can write ${\bm{U}}={\bm{U}}_{\leq{\mathsf{M}}}+{\bm{U}}_{>{\mathsf{M}}}$ where

Taking $q>1/\delta_{0}$, the right hand side become $o_{d}(1)$ and Theorem 6.$(b)$ follows by Markov’s inequality.

The next proposition establishes a generalization of this fact for the case in which both $D$ and $N$ diverge.

Then for any $q\geq 2$, there exists $K=K(q)$ that only depends on $C(q)$, such that denoting $\delta\equiv K(q)D\log(D\vee N)/N^{1-1/q}$, we have

By the hypercontractivity assumption, cf. Eq. (69), we have

Applying Lemma 2 below proves the proposition. ∎

We state a key proposition) whose proof will be presented in Section A.5. The statement and the assumptions are self-contained.

When $S\subseteq\{1,2,3,\ldots\}$, we denote

There exists a sequence $\{v(d)\}_{d\geq 1}$, such that for any fixed $q\geq 1$, there exists $C=C(q,\{v(d)\}_{d\geq 1})$ such that, for any $f_{d}\in\widehat{\mathcal{V}}_{d,\leq v(d)}\equiv{\rm span}(\hat{\phi}_{s},1\leq s\leq v(d))$, we have

For the same sequence $\{v(d)\}_{d\geq 1}$ as in (A1), there exists fixed $\delta_{0}>0$, such that

Then there exists $\delta^{\prime}>0$, such that

A.5 Proof of Proposition 4

We begin by stating two key estimates which are used in the proof of Proposition 4. The notations of Lemma 3 follow the notations of Proposition 4. The notations and assumptions of Proposition 5 are self-contained. We collect a number of technical lemmas in Section A.5.1.

Consider the same setup as Proposition 4. Let $\{N(d)\}_{d\geq 1}$ and $\{v(d)\}_{d\geq 1}$ be two sequences, and assume that there exists $\delta_{0}>0$ such that (this is Assumption (A2) in Proposition 4)

Then for any integer $p>0$, there exists a constant $K(p)$ which only depends on the constant $C(p)$, such that

We are now in position to prove Proposition 4.

By Assumption (A2) and by Lemma 3, we have

Combining the equations in the last two displays proves the proposition. ∎

where the last equation is by Eq. (71). This proves the lemma. ∎

Note by the hypercontractivity assumption as in Eq. (72), we have

Step 5. Combining the equations. Combining Eq. (75), (76), and (77), we have

The following standard decoupling trick follows, for instance, from [Ver10] in Lemma 5.60.

Let $\{\phi_{k}\}_{1\leq k\leq Z}\subseteq L^{2}(\Omega,\tau)$ be a set of orthonormal functions. We assume that, for any fixed $q\geq 1$, there exists $C=C(q)$, such that for any $f\in{\rm span}\{\phi_{k}:1\leq k\leq Z\}$, we have

For ${\bm{\theta}},{\bm{\theta}}^{\prime}\in\Omega$, we denote $\overline{U}({\bm{\theta}},{\bm{\theta}}^{\prime})=\sum_{k=1}^{Z}\lambda_{k}^{2}\phi_{k}({\bm{\theta}})\phi_{k}({\bm{\theta}}^{\prime})$ where $\{\lambda_{k}\}_{1\leq k\leq Z}$ are fixed real numbers. Then for any $q\geq 1$, we have

Here, inequality $(a)$ follows by applying the hypercontractivity inequality with respect to $f({\bm{\theta}}_{2})=\sum_{k=1}^{Z}\lambda_{k}^{2}\phi_{k}({\bm{\theta}}_{1})\phi_{k}({\bm{\theta}}_{2})$ (and conditional on ${\bm{\theta}}_{1}$). Equality $(b)$ by the fact that $(\phi_{k})_{1\leq k\leq Z}$ are orthonormal functions. Inequality $(c)$ is by the Minkowski inequality. Inequality $(d)$ follows by applying the hypercontractivity inequality with respect to $f({\bm{\theta}}_{1})=\phi_{k}({\bm{\theta}}_{1})$. Equality $(e)$ holds because $(\phi_{k})_{1\leq k\leq Z}$ are orthonormal functions. Finally, equality $(f)$ follows by simple calculation. This proves Eq. (78).

Here, inequality $(a)$ holds by Minkowski inequality. Inequality $(b)$ follows by applying the hypercontractivity inequality with respect to $f({\bm{\theta}})=\phi_{k}({\bm{\theta}})$. Equality $(c)$ holds because $(\phi_{k})_{1\leq k\leq Z}$ are orthonormal functions, and equality $(d)$ by a simple calculation. This proves Eq. (79). ∎

Consider a sequence of probability spaces $(\Omega_{d},\tau_{d})$ with $\{\phi_{d,k}\}_{k\geq 1}$ an orthonormal basis of functions for ${\mathcal{D}}_{d}\subseteq L^{2}(\Omega_{d},\tau_{d})$. Assume that there exists a sequence of integers $\{u(d)\}_{d\geq 1}$ such that the subspace ${\mathcal{D}}_{d,\leq u(d)}={\rm span}(\phi_{d,k}:1\leq k\leq u(d))$ is hypercontractive, i.e., for any fixed $k\geq 1$, there exists a constant $C$ such that, for any $g\in{\mathcal{D}}_{d,\leq u(d)}$, we have

Let $\{U_{d}\}_{d\geq 1}$ be a sequence of positive definite kernels $U_{d}\in L^{2}(\Omega_{d}\times\Omega_{d})$ with

Furthermore, if we assume that for any $\delta>0$,

Let us decompose $U_{d}$ in a high and low degree parts, $U_{d}=U_{d,\leq u}+U_{d,>u}$ where

Hence, by Markov’s inequality and condition (80), we get for any $\delta>0$, taking $q$ sufficiently large,

The proof of Eq. (83) follows from a similar argument. ∎

Appendix B Generalization error of random features model: Proof of Theorem 1

In this section, we prove Theorem 1. The proof in the overparametrized regime is presented in Section B.1. The proof in the underparametrized regime follows from a very similar argument: we will omit it and simply add comments in the overparametrized proof where they differ.

We defer the proofs of some technical results to later sections. Section B.2 proves a key proposition on the structure of the feature matrix ${\bm{Z}}=(\sigma_{d}({\bm{x}}_{i};{\bm{\theta}}_{j}))_{i\in[n],j\in[N]}$. Section B.3 gather some technical bounds necessary for the proof of Theorem 1. Finally, Section B.4 contains concentration results on the high degree part of the feature matrix.

In this section, we prove Theorem 1 in the overparametrized regime. We defer the proofs of some of the technical lemmas and matrix concentration results to Sections B.2, B.3 and B.4. The underparametrized case follows from the same proof with the following mapping $n\leftrightarrow N$, ${\mathsf{m}}\leftrightarrow{\mathsf{M}}$ and $\lambda\rightarrow\lambda_{N}=N\lambda/n$. We will add remarks in the proof when a difference arises.

Step 1. Rewrite the ${\bm{y}}$, ${\bm{V}}$, ${\bm{U}}$, ${\bm{Z}}$ matrices.

We recall that the random features ridge regression solution is given by

where ${\bm{V}}=(V_{1},\ldots,V_{N})^{\mathsf{T}}$ and ${\bm{U}}=(U_{ij})_{ij\in[N]}$with

and $\hat{{\bm{U}}}_{\lambda}={\bm{Z}}^{\mathsf{T}}{\bm{Z}}/N+\lambda{\mathbf{I}}_{N}$ is the (rescaled) regularized empirical kernel matrix

We recall that the eigendecomposition of $\sigma_{d}$ is given by

We write the orthogonal decomposition of $f_{d}$ in this basis as

Recall that ${\bm{y}}=(y_{1},\ldots,y_{n})^{\mathsf{T}}={\bm{f}}+{\bm{\varepsilon}}$ with

Using the above notations, we can decompose the vectors and matrices ${\bm{f}}$, ${\bm{V}}$, ${\bm{U}}$, and as

We decompose the risk with respect to ${\bm{y}}={\bm{f}}+{\bm{\varepsilon}}$ as follows

The proof relies on the following key result on the structure of the feature matrix ${\bm{Z}}$:

Follow the assumptions and the notations in the proof of Theorem 1 in the overparametrized regime (note in particular that $N\geq n^{1+\delta_{0}}$ and $n\geq{\mathsf{m}}^{1+\delta_{0}}$ for some fixed $\delta_{0}>0$). Consider the singular value decomposition of ${\bm{Z}}=(Z_{ij})_{i\in[n],j\in[N]}$ with $Z_{ij}=\sigma_{d}({\bm{x}}_{i};{\bm{\theta}}_{j})$: