When Do Neural Networks Outperform Kernel Methods?

Introduction

${\mathcal{F}}_{{\rm NN}}^{N}$ is a non-linearly parametrized class of functions: while nonlinearity poses a challenge to theoreticians, it is often claimed to be crucial in order to learn rich representation of the data. Recent efforts to understand NN have put the spotlight on two linearizations of ${\mathcal{F}}_{{\rm NN}}^{N}$, the random features [RR08] and the neural tangent [JGH18] classes

${\mathcal{F}}_{{\rm RF}}^{N}({\bm{W}})$ and ${\mathcal{F}}_{{\rm NT}}^{N}({\bm{W}})$ are linear classes of functions, depending on the realization of the input-layer weights ${\bm{W}}=({\bm{w}}_{i})_{i\leq N}$ (which are chosen randomly). The relation between NN and these two linear classes is given by the first-order Taylor expansion: $\hat{f}_{{\rm NN}}({\bm{x}};{\bm{b}}+\varepsilon{\bm{a}},{\bm{W}}+\varepsilon{\bm{S}})-\hat{f}_{{\rm NN}}({\bm{x}};{\bm{b}},{\bm{W}})=\varepsilon\hat{f}_{{\rm RF}}({\bm{x}};{\bm{a}};{\bm{W}})+\varepsilon\hat{f}_{{\rm NT}}({\bm{x}};{\bm{S}}({\bm{b}});{\bm{W}})+O(\varepsilon^{2})$, where ${\bm{S}}({\bm{b}})=(b_{i}{\bm{s}}_{i})_{i\leq N}$. A number of recent papers show that, if weights and SGD updates are suitably scaled, and the network is sufficiently wide ($N$ sufficiently large), then SGD converges to a function $\hat{f}_{{\rm NN}}$ that is approximately in ${\mathcal{F}}_{{\rm RF}}^{N}({\bm{W}})+{\mathcal{F}}_{{\rm NT}}^{N}({\bm{W}})$, with ${\bm{W}}$ determined by the SGD initialization [JGH18, DZPS19, DLL+19, AZLS19, ZCZG18, OS20]. This was termed the ‘lazy regime’ in [COB19].

where ${\rm cl}(\,\cdot\,)$ denotes closure. From this point of view, ${\rm RF}$ and ${\rm NT}$ differ in that they correspond to slightly different choices of the kernel: $h_{{\rm RF}}({\bm{x}}_{1},{\bm{x}}_{2}):=\int\sigma(\langle{\bm{w}},{\bm{x}}_{1}\rangle)\sigma(\langle{\bm{w}},{\bm{x}}_{2}\rangle)\nu({\rm d}{\bm{w}})$ versus $h_{{\rm NT}}({\bm{x}}_{1},{\bm{x}}_{2}):=\langle{\bm{x}}_{1},{\bm{x}}_{2}\rangle\int\sigma^{\prime}({\bm{w}}^{{\mathsf{T}}}{\bm{x}}_{1})\sigma^{\prime}({\bm{w}}^{{\mathsf{T}}}{\bm{x}}_{2})\nu({\rm d}{\bm{w}})$. Multi-layer fully-connected ${\rm NN}$s in the lazy regime can be viewed as randomized approximations to RKHS as well, with some changes in the kernel $h$. This motivates analogous questions for ${\mathcal{H}}(h)$: can the performances of ${\rm NN}$ be achieved by RKHS methods?

Recent work addressed the separation between NN and RKHS from several points of view, without providing a unified answer. Some empirical studies on various datasets showed that networks can be replaced by suitable kernels with limited drop in performances [ADL+20, LWY+19, LXS+19, NXB+19, LSdP+18, DMHR+18, GARA19, SFG+20]. At least two studies reported a larger gap for convolutional networks and the corresponding kernels [ADH+19, GSJW19]. On the other hand, theoretical analysis provided a number of separation examples, i.e. target functions $f_{*}$ that can be represented and possibly efficiently learnt using neural networks, but not in the corresponding RKHS [YS19, Bac17, GMMM19b, GMMM19a, AZL19, AZL20]. For instance, if the target is a single neuron $f_{*}({\bm{x}})=\sigma(\langle{\bm{w}}_{*},{\bm{x}}\rangle)$, then training a neural network with one hidden neuron learns the target efficiently from approximately $d\log d$ samples [MBM18], while the corresponding RKHS has test error bounded away from zero for every sample size polynomial in $d$ [YS19, GMMM19b]. Further even in the infinite width limit, it is known that two-layers neural networks can actually capture a richer class of functions than the associated RKHS, provided SGD training is scaled differently from the lazy regime [MMN18, CB18, RVE18, SS18, CB20].

Can we reconcile empirical and theoretical results?

In this paper we introduce a stylized scenario – which we will refer to as the spiked covariates model – that can explain the above seemingly divergent observations in a unified framework. The spiked covariates model is based on two building blocks: $(1)$ Target functions depending on low-dimensional projections; $(2)$ Approximately low-dimensional covariates.

As for the example of a single neuron $f_{*}({\bm{x}})=\sigma(\langle{\bm{w}}_{*},{\bm{x}}\rangle)$, we expect RKHS to suffer from a curse of dimensionality in learning functions of low-dimensional projections. Indeed, this is well understood in low dimension or for isotropic covariates [Bac17, GMMM19b].

$(2)$ Approximately low-dimensional covariates. RKHS behave well on certain image classification tasks [ADH+19, LWY+19, NXB+19], and this seems to contradict the previous point. However, the example of image classification naturally brings up another important property of real data that helps to clarify this puzzle. Not only we expect the target function $f_{*}({\bm{x}})$ to depend predominantly on the low-frequency components of image ${\bm{x}}$, but the image ${\bm{x}}$ itself to have most of its spectrum concentrated on low-frequency components (linear denoising algorithms exploit this very observation).

2 Notations and outline

In section 2, we introduce the spiked covariates model and characterize the performance of KRR, RF, NT, and NN models. Section 3 presents numerical experiments with real and synthetic data. Section 4 discusses our results in the context of earlier work.

Rigorous results for kernel methods and NT, RF NN expansions

We call ${\bm{z}}_{0,i}$ the signal covariates, ${\bm{z}}_{1,i}$ the noise covariates, and $r$ the covariates signal-to-noise ratio (or covariates SNR). We will take $r>1$, so that the variance of the signal covariates ${\bm{z}}_{0,i}$ is larger than that of the noise covariates ${\bm{z}}_{1,i}$. In high dimension, this model is –for many purposes– similar to an anisotropic Gaussian model ${\bm{x}}_{i}\sim{\sf N}(0,(r^{2}-1){\bm{U}}{\bm{U}}^{{\mathsf{T}}}+{\mathbf{I}})$. As shown below, the effect of anisotropy on RKHS methods is significant only if the covariate SNR $r$ is polynomially large in $d$. We shall therefore set $r=d^{\kappa/2}$ for a constant $\kappa>0$.

We will consider a more general model in Appendix C, in which the distribution of ${\bm{x}}_{i}$ takes a more general product-of-uniforms form, and we assume a general $f_{*}\in L^{2}$.

2 A sharp characterization of RKHS methods

Any RKHS method with kernel $h$ outputs a model of the form $\hat{f}({\bm{x}};{\bm{a}})=\sum_{i\leq n}a_{i}h(\langle{\bm{x}},{\bm{x}}_{i}\rangle/d)$, with RKHS norm given by $\|\hat{f}(\,\cdot\,;{\bm{a}})\|_{h}^{2}=\sum_{i,j\leq n}h(\langle{\bm{x}}_{i},{\bm{x}}_{j}\rangle/d)a_{i}a_{j}$. We consider kernel ridge regression (KRR) on the dataset $\{(y_{i},{\bm{x}}_{i})\}_{i\leq n}$ with regularization parameter $\lambda$, namely:

where ${\bm{H}}=(H_{ij})_{ij\in[n]}$, with $H_{ij}=h(\langle{\bm{x}}_{i},{\bm{x}}_{j}\rangle/d)$. We denote the prediction error of KRR by

where ${\bm{h}}({\bm{x}})=(h(\langle{\bm{x}},{\bm{x}}_{1}\rangle/d),\ldots,h(\langle{\bm{x}},{\bm{x}}_{n}\rangle/d))^{\mathsf{T}}$.

Recall that we assume the target function $f_{*}({\bm{x}}_{i})=\varphi({\bm{U}}^{{\mathsf{T}}}{\bm{x}}_{i})$. We denote ${\mathsf{P}}_{\leq k}:L^{2}\to L^{2}$ to be the projection operator onto the space of degree $k$ orthogonal polynomials, and ${\mathsf{P}}_{>k}={\mathbf{I}}-{\mathsf{P}}_{\leq k}$. Our next theorem shows that the impact of the low-dimensional latent structure on the generalization error of KRR is characterized by a certain ‘effective dimension’, $d_{\mbox{\tiny\rm eff}}$.

3 RF and NT models

How do the results of the previous section generalize to finite-width approximations of the RKHS? In particular, how do the RF and NT models behave at finite $N$? In order to simplify the picture, we focus here on the approximation error. Equivalently, we assume the sample size to be $n=\infty$ and consider the minimum population risk for ${\sf M}\in\{{\rm RF},{\rm NT}\}$

The next two theorems characterize the asymptotics of the approximation error for RF and NT models. We give generalizations of these statements to other settings and under weaker assumptions in Appendix C.

Finally, it is natural to ask what are the behaviors of RF and NT models at finite sample size. Denote by $R_{{\sf M},N,n}(f_{*};{\bm{W}})$ the corresponding test error (assuming for instance ridge regression, with the optimal regularization $\lambda$). Of course the minimum population risk provides a lower bound: $R_{{\sf M},N,n}(f_{*};{\bm{W}})\geq R_{{\sf M},N}(f_{*};{\bm{W}})$. Moreover, we conjecture that the risk is minimized at infinite $N$, $R_{{\sf M},N,n}(f_{*};{\bm{W}})\gtrsim R_{n}(f_{*};h_{{\sf M}})$. Altogether this implies the lower bound $R_{{\sf M},N,n}(f_{*};{\bm{W}})\gtrsim\max(R_{{\sf M},N}(f_{*};{\bm{W}}),R_{n}(f_{*};h_{{\sf M}}))$. We also conjecture that this lower bound is tight, up to terms vanishing as $N,n,d\to\infty$.

4 Neural network models

Moreover, the quantity $R_{{\rm NN},N}(f_{*})$ is independent of $\kappa\geq 0$.

As a consequence of Theorem 3 and 4, there is a separation between NN and (uniformly sampled) NT models when $d_{\mbox{\tiny\rm eff}}\neq d_{0}$, i.e., $\kappa<1-\eta$. As $\kappa$ increases, the gap between NN and NT becomes smaller and smaller until $\kappa=1-\eta$.

Further numerical experiments

We carried out extensive numerical experiments on synthetic data to check our predictions for RF, NT, RKHS methods at finite sample size $n$, dimension $d$, and width $N$. We simulated two-layers fully-connected NN in the same context in order to compare their behavior to the behavior of the previous models. Finally, we carried out numerical experiments on FMNIST and CIFAR-10 data to test whether our qualitative predictions apply to image datasets. Throughout we use ReLU activations.

The basic qualitative insight of our work can be summarized as follows. Kernel methods are effective when a low-dimensional structure in the target function is aligned with a low-dimensional structure in the covariates. In image data, both the target function and the covariates are dominated by the low-frequency subspace. In Figure 1 we tested this hypothesis by removing the low-dimensional structure of the covariate vectors: we simply added noise to the high-frequency part of the image. In Figure 4 we try the opposite, by removing the component of the target function that is localized on low-frequency modes. We decompose each images into a low-frequency and a high-frequency part. We leave the high-frequency part unchanged, and replace the low-frequency part by Gaussian noise with the first two moments matching the empirical moments of the data.

In the left frame, we consider FMNIST data and compare fully-connected NNs with $2$ or $3$ layers (and $N=4096$ nodes at each hidden layer) with the corresponding NT KRR model (infinite width). In the right frame, we use CIFAR-10 data and compare a Myrtle-5 network (a lightweight convolutional architecture [Pag18, SFG+20]) with the corresponding NT KRR. We observe the same behavior as in Figure 1. While for the original data NT is comparable to NN, as the proportion of perturbed Fourier modes increases, the performance of NT deteriorates much more rapidly than the one of NN.

Discussion

However, these classical statistical results have some limitations. First, they focus on the low-dimensional regime: $d$ is fixed, while the sample size $n$ diverges. This is probably unrealistic for many machine learning applications, in which $d$ is at least of the order of a few hundreds. Second, classical lower bounds are typically established for the minimax risk, and hence they do not necessarily apply to specific functions.

To bridge these gaps, we developed a sharp characterization of the test error in the high-dimensional regime in which both $d$ and $n$ diverge, while being polynomially related. This characterization holds for any target function $f_{*}$, and expresses the limiting test error in terms of the polynomial decomposition. We also present analogous results for finite-width RF and NT models.

Depending on the relation between signal dimension $d_{0}$, ambient dimension $d$, and the covariate signal-to-noise ratio $r$, the model presents a continuum of different behaviors. At one extreme, the covariates are fully $d$-dimensional, and RKHS methods are highly suboptimal compared to NN. At the other, covariates are close to $d_{0}$-dimensional and RKHS methods are instead more competitive with NN.

Finally, the Fourier decomposition of images is a simple proxy for the decomposition of the covariate vector ${\bm{x}}$ into its low-dimensional dominant component (low frequency) and high-dimensional component (high frequency) [YLS+19].

Acknowledgements

This work was partially supported by the NSF grants CCF-1714305, IIS-1741162, DMS-1418362, DMS-1407813 and by the ONR grant N00014-18-1-2729.

References

Appendix A Details of numerical experiments

where $lr_{0}=10^{-3}$ and $T=750$ is the total number of training epochs. To ensure the stability of the optimization for wide models, we use $15$ linear warm-up epochs in the beginning.

In order to use CG, we first implement a function to perform Hessian-vector products in TensorFlow [ABC+16]. The function handle is then passed to scipy.sparse.cg for CG. Our Hessian-vector product code uses tensor manipulation utilities implemented by [GKX19].

Unfortunately, scipy.sparse.cg does not support one-hot encoded labels. To avoid running CG for each class separately, when the labels are one-hot encoded, we use Adam optimizer [KB14] instead. When using Adam, the learning-rate still evolves as (11) with $lr_{0}=10^{-5}$. The batch-size is fixed at $10^{4}$ to encourage fast convergence to the minimum.

For ${\rm NN}$, ${\rm RF}$ and ${\rm NT}$, the training is primary done in TensorFlow (v1.12) [ABC+16]. For KRR, we generate the kernel matrix first and directly fit the model in regular python. The kernels associated with two-layer models are calculated analytically. For deeper models, the kernels are computed using neural-tangents library in JAX [BFH+18, NXH+20].

A.2 Synthetic data experiments

The synthetic data follows the distribution outlined in the main text. In particular,

where ${\bm{u}}_{i}$ and ${\bm{z}}_{i}$ are drawn i.i.d from the hyper-spheres with radii $r\sqrt{d_{0}}$ and $\sqrt{d}$ respectively. We choose

where $d$ is fixed to be $1024$ and $\eta=\frac{2}{5}$. We change $\kappa$ in the interval $\{0,…,0.9\}$. For each value of $\kappa$ we generate $2^{20}$ training and $10^{4}$ test observations.Strictly speaking, the model outlined in the main text requires ${\bm{z}}_{i}$ to be generated from the hyper-sphere of radius $\sqrt{d-d_{0}}$. In order to work with round numbers, in our experiments we use $\sqrt{d}$ instead of $\sqrt{d-d_{0}}$. The numerical difference between these two choices is negligible.

The function $\varphi$ is the sum of three orthogonal components $\{\varphi_{i}\}_{i=1}^{3}$ with $\|\varphi_{i}\|_{2}=1$. To be more specific,

This choice of $\varphi_{i}$ guarantees that each $\varphi_{i}$ is in the span of degree $i+1$ spherical harmonics.

In Figure 3 of the main text, we compared the generalization performance of NTK KRR with ${\rm NN}$. We use the same training and test data as above to perform this analysis. The number of training data points, $n$, takes $24$ different values ranging from $50$ to $10^{5}$. The number of test data points is always fixed at $10^{4}$.

A.3 High-frequency noise experiment on FMNIST

In effort to make the distribution of the covariates more isotropic, in this experiment, we add high-frequency noise to both the training and test data.

Finally, we normalize the ${\bm{x}}_{noisy}$ so that it has norm $\sqrt{d}$.

This choice of ${\bm{F}}$ mirrors the average frequency domain representation of FMNIST images (see Figure A.1 for a comparison). Figure A.2 shows the eigenvalues of the empirical covariance of the dataset for various noise levels. As discussed in the main text, the distribution of the covariates becomes more isotropic as more and more high-frequency noise is added to the images.

Figure A.3 shows the normalized squared loss and the classification accuracy of the models as more and more high-frequency noise is added to the data. The normalization factor $R_{0}=0.9$ corresponds to the risk achievable by the (trivial) predictor \bigg{[}\hat{y}_{j}({\bm{x}})\bigg{]}_{1\leq j\leq 10}=0.1.

A.4 High-frequency noise experiment on CIFAR-2

We perform a similar experiment on a subset of CIFAR-10. We choose two classes (airplane and cat) from the ten classes of CIFAR-10. This choice provides us with $10^{4}$ training and $2000$ test data points. Given that the number of training observations is not very large, we reduce the covariate dimension by converting the images to grayscale. This transformation reduces the covariate dimension to $d=1024$.

Figure A.5 demonstrates the evolution of the model performances as the noise intensity increases. In the noiseless regime ($\tau=0$), all models have comparable performances. However, as the noise level increases, the performance gap between ${\rm NN}$ and RKHS methods widens. For reference, the accuracy gap between ${\rm NN}$ and ${\rm NT}$ KRR is only $0.6\%$ at $\tau=0$. However, at $\tau=3$, this gap increases to $4.5\%$. The normalization factor $R_{0}=0.25$ corresponds to the risk achievable by the trivial estimator $\hat{y}({\bm{x}})=0.5$.

A.5 Low-frequency noise experiments on FMNIST

To examine the ability of NN and RKHS methods in learning the information in low-variance components of the covariates, we replace the low-frequency components of the image with Gaussian noise. To be specific, we follow the following steps to generate the noisy datasets:

We normalize all images to have mean zero and norm $\sqrt{d}$.

Let $\mathcal{D}_{train}$ denote the set of training images in the DCT-frequency domain. We compute the mean $\mu$ and the covariance $\Sigma$ of the elements of $\mathcal{D}_{train}$.

The fraction of the frequencies replaced by noise is $\alpha^{2}/k^{2}$.

For neural networks trained for this experiment, we fix the number of hidden units per-layer to $N=4096$. This corresponds to approximately $3.2\times 10^{6}$ trainable parameters for two-layer networks and $2\times 10^{7}$ trainable parameters for three-layer networks. Both models are trained using SGD with momentum with learning rate described by $\eqref{eqn:cosine_rule}$ (with $lr_{0}=10^{-3}$). For the warm-up epochs, we use batch-size of $500$. We increase the batch-size to $1000$ after the warm-up stage. The regularization grids used for training our models are presented in Table A.3.

A.6 Low-frequency noise experiments on CIFAR-10

To test whether our insights are valid for convolutional models, we repeat the same experiment for CNNs trained on CIFAR-10. The noisy data is generated as follows:

Let $\mathcal{D}_{train}$ denote the set of training images in the DCT-frequency domain. Note that CIFAR-10 images have $3$ channels. To convert the images to frequency domain, we apply two-dimensional Discrete Cosine Transform (DCT-II orthogonal) to each channel separately. We compute the mean $\mu$ and the covariance $\Sigma$ of the elements of $\mathcal{D}_{train}$.

We normalize the noisy data to have zero per-channel mean and unit per-channel standard deviation. The normalization statistics are computed using only the training data.

We use Myrtle-5 architecture for our analysis. The Myrtle family is a collection of simple light-weight high-performance purely convolutional models. The simplicity of these models coupled with their good performance makes them a natural candidate for our analysis. Figure A.7 describes the details of this architecture. We fix the number of channels in all convolutional layer to be $N=512$. This corresponds to approximately $7\times 10^{6}$ parameters. Similar to the fully-connected networks, our convolutional models are also optimized via SGD with $0.9$ momentum (learning rate evolves as (11) with $lr_{0}=0.1$ and $T=70$). We fix the batch-size to $128$. To keep the experimental setting as simple as possible, we do not use any data augmentation for training the network.

Appendix B Technical background on function spaces on the sphere

The dimension of each subspace is given by

B.2 Gegenbauer polynomials

We will use the following properties of Gegenbauer polynomials

Note in particular that property 2 implies that –up to a constant– $Q_{k}^{(d)}(\langle{\bm{x}},{\bm{y}}\rangle)$ is a representation of the projector onto the subspace of degree -$k$ spherical harmonics

B.3 Hermite polynomials

Notice that for functions $g$ that are $k$-weakly differentiable with $g^{(k)}$ the $k$-th weak derivative, we have

Here and below, for $P$ a polynomial, ${\rm Coeff}\{P(x)\}$ is the vector of the coefficients of $P$.

B.4 Tensor product of spherical harmonics

We will consider in this paper the product space

The dimension of each subspace is given by

We have the following orthonormalization property

We denote by ${\mathsf{P}}_{{\bm{k}}}$ the orthogonal projections on $V^{{\bm{d}}}_{{\bm{k}}}$ in $L^{2}({\rm PS}^{{\bm{d}}},\mu_{{\bm{d}}})$. This can be written in terms of spherical harmonics as

B.5 Tensor product of Gegenbauer polynomials

We will use the following properties of the tensor product of Gegenbauer polynomials:

Notice that Lemma 1.(c) implies that $Q_{{\bm{k}}}^{{\bm{d}}}$ is (up to a constant) a representation of the projector onto the subspace $V^{{\bm{d}}}_{{\bm{k}}}$

Part $(a)$ comes from the normalization property (22) of Gegenbauer polynomials,

while part $(c)$ is a direct consequence of Eq. (24).

B.6 Notations

Furthermore, $f=\omega_{d}(g)$ will denote $f(d)/g(d)\to\infty$.

Appendix C General framework and main theorems

In this section, define a more general model than the model considered in the main text. In the general model, we will assume the covariate vectors will follow a product of uniform distributions on the sphere, and assume a target function in $L^{2}$ space. We establish more general versions of Theorems 1, 2, 3 on the two-spheres cases in the main text as Theorems 5, 6, 7. We will prove Theorems 5, 6, 7 in the following sections. At the end of this section, we will show that Theorems 5, 6, 7 will imply Theorems 1, 2, 3 in the main text.

Assume that the data ${\bm{x}}$ lies on the product of $Q$ spheres,

where $d_{q}=d^{\eta_{q}}$ and $r_{q}=d^{(\eta_{q}+\kappa_{q})/2}$. Let ${\bm{d}}=(d_{1},\ldots,d_{q})=(d^{\eta_{1}},\ldots,d^{\eta_{q}})$ and ${\bm{\kappa}}=(\kappa_{1},\ldots,\kappa_{Q})$, where $\eta_{q}>0$ and $\kappa_{q}\geq 0$ for $q=1,\ldots,Q$. We will denote this space

Furthermore, assume that the data is generated following the uniform distribution on ${\rm PS}^{\bm{d}}_{{\bm{\kappa}}}$, i.e.

We will make the following assumption that will simplify the proofs. Denote

then $\xi$ is attained on only one of the sphere, whose coordinate will be denoted $q_{\xi}$, i.e. $\xi=\eta_{q_{\xi}}+\kappa_{q_{\xi}}$ and $\eta_{q}+\kappa_{q}<\xi$ for $q\neq q_{\xi}$.

We will denote ${\bm{\theta}}_{i}=\sqrt{D}{\bm{w}}_{i}$. Notice that the normalization in the definition of the function class insures that the scalar product $\langle{\bm{x}},{\bm{\theta}}_{i}\rangle/R$ is of order $1$. This corresponds to normalizing the data.

We consider the approximation of $f$ by functions in function classes ${\mathcal{F}}_{{\rm RF}}({\bm{\Theta}})$ and ${\mathcal{F}}_{{\rm NT}}({\bm{\Theta}})$.

C.2 Reparametrization

It is easy to check that the variables $(\overline{\bm{\theta}}^{(1)},\ldots,\overline{\bm{\theta}}^{(Q)})$ are independent and independent of $(\tau_{i}^{(1)},\ldots,\tau_{i}^{(Q)})$, and verify

We will denote $\overline{\bm{\theta}}_{i}\equiv(\overline{\bm{\theta}}^{(1)}_{i},\ldots,\overline{\bm{\theta}}^{(Q)}_{i})$ and ${\bm{\tau}}_{i}\equiv(\tau^{(1)}_{i},\ldots,\tau^{(Q)}_{i})$. With these notations, we have

where ${\rm PS}^{\bm{d}}$ is the ‘normalized space of product of spheres’, and

Similarly, we will denote the rescaled data $\overline{\bm{x}}\in{\rm PS}^{\bm{d}}$,

obtained by taking $\overline{\bm{x}}^{(q)}=\sqrt{d_{q}}{\bm{x}}^{(q)}/r_{q}=d^{-\kappa_{q}/2}{\bm{x}}^{(q)}$ for each $q\in[Q]$.

The proof will proceed as follows: first, noticing that $\tau^{(q)}$ concentrates around $1$ for every $q=1,\ldots,Q$, we will restrict ourselves without loss of generality to the following high probability event

where $\varepsilon>0$ will be chosen sufficiently small. Then, we rewrite the activation function

as a function, for a random ${\bm{\tau}}$ (but close to $(1,\ldots,1)$)

given for ${\bm{\theta}}=(\overline{\bm{\theta}},{\bm{\tau}})$ by

We can therefore apply the algebra of tensor product of spherical harmonics and use the machinery developed in [GMMM19b].

C.3 Notations

Recall the definitions ${\bm{d}}=(d_{1},\ldots,d_{q})$, ${\bm{\kappa}}=(\kappa_{1},\ldots,\kappa_{Q})$, $d_{q}=d^{\eta_{q}}$, $r_{q}=d^{(\eta_{q}+\kappa_{q})/2}$, $D=d^{\eta_{1}}+\ldots+d^{\eta_{Q}}$ and $R=(d^{\eta_{1}+\kappa_{1}}+\ldots+d^{\eta_{Q}+\kappa_{Q}})^{1/2}$. Let us denote $\xi=\max_{q\in[Q]}\{\eta_{q}+\kappa_{q}\}$ and $q_{\xi}=\arg\min_{q\in[Q]}\{\eta_{q}+\kappa_{q}\}$.

C.4 Generalization error of kernel ridge regression

We consider the Kernel Ridge Regression solution $\hat{a}_{i}$, namely

where the kernel matrix ${\bm{H}}=(H_{ij})_{ij\in[n]}$ is assumed to be given by

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

The prediction function at location ${\bm{x}}$ gives

The test error of empirical kernel ridge regression is defined as

Notice that by definition $m(\gamma)>\gamma$.

We consider sequences of problems indexed by the integer $d$, and we view the problem parameters (in particular, the dimensions $d_{q}$, the radii $r_{q}$, the kernel $h_{d}$, and so on) as functions of $d$.

For $\gamma>0$ (which is specified in the theorem), we denote $L=\max_{q\in[Q]}\lceil\gamma/\eta_{q}\rceil$. We assume that $h_{d}$ is $L$-weakly differentiable. We assume that for $0\leq k\leq L$, the $k$-th weak derivative verifies almost surely $h_{d}^{(k)}(u)\leq C$ for some constants $C>0$ independent of $d$. Furthermore, we assume there exists $k>L$ such that $h_{d}^{(k)}(0)\geq c>0$ with $c$ independent of $d$.

For $\gamma>0$ (which is specified in the theorem), we define

We assume that $\sigma$ verifies for $k\leq\overline{K}$, $h_{d}^{(k)}(0)\geq c$, with $c>0$ independent of $d$.

Let $\{f_{d}\in L^{2}({\rm PS}^{\bm{d}}_{\bm{\kappa}},\mu_{{\bm{d}}}^{\bm{\kappa}})\}_{d\geq 1}$ be a sequence of functions. Assume $w_{d}(d^{\gamma}\log d)\leq n\leq O_{d}(d^{m(\gamma)-\delta})$ for some $\gamma>0$ and $\delta>0$. Let $\{h_{d}\}_{d\geq 1}$ be a sequence of functions that satisfies Assumption 1 at level $\gamma$. Let ${\bm{X}}=({\bm{x}}_{i})_{i\in[n]}$ with $({\bm{x}}_{i})_{i\in[n]}\sim{\rm Unif}({\rm PS}^{\bm{d}}_{{\bm{\kappa}}})$ independently, and $y_{i}=f_{d}({\bm{x}}_{i})+\varepsilon_{i}$ and $\varepsilon_{i}\sim_{iid}{\sf N}(0,\tau^{2})$ for some $\tau^{2}\geq 0$. Then for any $\varepsilon>0$, and for any $\lambda=O_{d}(1)$, with high probability we have

See Section D for the proof of this Theorem.

C.5 Approximation error of the random features model

We consider the minimum population error for the random features model

For $\gamma>0$ (which is specified in the theorem), we denote $L=\max_{q\in[Q]}\lceil\gamma/\eta_{q}\rceil$. We assume that $\sigma$ is $L$-weakly differentiable. Define

We assume that for $K\leq k\leq L$, the $k$-th weak derivative verifies almost surely $\sigma^{(k)}(u)^{2}\leq c_{0}\exp(c_{1}u^{2}/2)$ for some constants $c_{0}>0$ and $c_{1}<1$.

Furthermore we will assume that $\sigma$ is not a degree-$\lfloor\gamma/\eta_{q_{\xi}}\rfloor$ polynomial where we recall that $q_{\xi}$ corresponds to the unique $\arg\min_{q\in[Q]}\{\eta_{q}+\kappa_{q}\}$.

For $\gamma>0$ (which is specified in the theorem), we define

We assume that $\sigma$ verifies for $k\leq\overline{K}$, $\mu_{k}(\sigma)\neq 0$. Furthermore we assume that for $k\leq\overline{K}$, the $k$-th weak derivative verifies almost surely $\sigma^{(k)}(u)^{2}\leq c_{0}\exp(c_{1}u^{2}/2)$ for some constants $c_{0}>0$ and $c_{1}<1$.

Assume $N\leq o_{d}(d^{\gamma})$ for a fixed $\gamma>0$. Let $\sigma$ satisfy Assumptions 2.(a) and 2.(b) at level $\gamma$. Then, for any $\varepsilon>0$, the following holds with high probability:

where ${\mathcal{Q}}\equiv{\mathcal{Q}}_{\rm RF}(\gamma)$ is defined in Equation (45).

Assume $N\geq w_{d}(d^{\gamma})$ for some positive constant $\gamma>0$, and $\sigma$ satisfy Assumptions 2.(a) and 2.(c) at level $\gamma$. Then for any $\varepsilon>0$, the following holds with high probability:

where ${\mathcal{Q}}\equiv\overline{{\mathcal{Q}}}_{\rm RF}(\gamma)$ is defined in Equation (46).

See Section E for the proof of the lower bound (48), and Section F for the proof of the upper bound (49).

such that for $N=d^{\gamma}$, ${\rm RF}$ model fits the subspace of low degree polynomials ${\mathcal{F}}({\bm{\beta}},{\bm{\kappa}},\gamma)$ and cannot fit ${\mathcal{F}}^{c}({\bm{\beta}},{\bm{\kappa}},\gamma)$, i.e.

Each subspace has therefore an effective dimension $d_{q,{\rm eff}}\equiv d^{\xi-\kappa_{q}}=d_{q}^{(\xi-\kappa_{q})/\eta_{q}}\asymp D^{(\xi-\kappa_{q})/\max_{q\in[Q]}\eta_{q}}$. This can be understood intuitively as follows,

C.6 Approximation error of the neural tangent model

We consider the minimum population error for the random features model

For $\gamma>0$ (which is specified in the theorem), we denote $L=\max_{q\in[Q]}\lceil\gamma/\eta_{q}\rceil$. We assume that $\sigma^{\prime}$ is $L$-weakly differentiable. Define

We assume that for $K-1\leq k\leq L$, the $k$-th weak derivative verifies almost surely $\sigma^{(k+1)}(u)^{2}\leq c_{0}\exp(c_{1}u^{2}/2)$ for some constants $c_{0}>0$ and $c_{1}<1$.

For $\gamma>0$ (which is specified in the theorem), we define

We assume that $\sigma$ verifies for $k\leq\overline{K}+1$, $\mu_{k}(\sigma^{\prime})=\mu_{k+1}(\sigma)\neq 0$. Furthermore we assume that for $k\leq\overline{K}+1$ , the $k$-th weak derivative verifies almost surely $\sigma^{(k+1)}(u)^{2}\leq c_{0}\exp(c_{1}u^{2}/2)$ for some constants $c_{0}>0$ and $c_{1}<1$.

In the Assumption 3.(b), it is useful to notice that the Hermite coefficients of $x^{2}\sigma^{\prime}(x)$ can be computed from the ones of $\sigma^{\prime}(x)$ using the relation $\mu_{k}(x^{2}\sigma^{\prime})=\mu_{k+2}(\sigma^{\prime})+[1+2k]\mu_{k}(\sigma^{\prime})+k(k-1)\mu_{k-2}(\sigma^{\prime})$.

Assume $N\leq o_{d}(d^{\gamma})$ for a fixed $\gamma>0$. Let $\sigma$ satisfy Assumptions 3.(a) and 3.(b) at level $\gamma$. Then, for any $\varepsilon>0$, the following holds with high probability:

where ${\mathcal{Q}}\equiv{\mathcal{Q}}_{\rm NT}(\gamma)$ is defined in Equation (50).

Assume $N\geq w_{d}(d^{\gamma})$ for some positive constant $\gamma>0$, and $\sigma$ satisfy Assumptions 3.(a) and 3.(c) at level $\gamma$. Then for any $\varepsilon>0$, the following holds with high probability:

where ${\mathcal{Q}}\equiv\overline{{\mathcal{Q}}}_{\rm NT}(\gamma)$ is defined in Equation (51).

See Section G for the proof of lower bound, and Section H for the proof of upper bound.

This theorems shows that each for each $\gamma>0$ such that ${\mathcal{Q}}_{{\rm NT}}(\gamma)^{c}\cap\overline{{\mathcal{Q}}}_{{\rm NT}}(\gamma)=\emptyset$, we can decompose our functional space as

such that for $N=d^{\gamma}$, ${\rm NT}$ model fits the subspace of low degree polynomials ${\mathcal{F}}({\bm{\beta}},{\bm{\kappa}},\gamma)$ and cannot fit ${\mathcal{F}}^{c}({\bm{\beta}},{\bm{\kappa}},\gamma)$ at all, i.e.

where $\beta=\xi-\min_{q\in S({\bm{k}})}\kappa_{q}$.

C.7 Connecting to the theorems in the main text

Let us connect the above general results to the two-spheres setting described in the main text. We consider two spheres with $\eta_{1}=\eta$, $\kappa_{1}=\kappa$ for the first sphere, and $\eta_{2}=1$, $\kappa_{2}=0$ for the second sphere. We have $\xi=\max(\eta+\kappa,1)$.

Let $w_{d}(d^{\gamma}\log d)\leq n\leq O_{d}(d^{\gamma+\delta})$ with $\delta>0$ constant sufficiently small, then by Theorem 5 the function subspace learned by KRR is given by the polynomials of degree $k_{1}$ in the first sphere coordinates and $k_{2}$ in the second sphere with

We consider functions that only depend on the first sphere, i.e., $k_{2}=0$ and denote $d_{\rm eff}=d^{\max(\eta,1-\kappa)}$. Then the subspace of approximation is given by the $k$ polynomials in the first sphere such that $d_{\rm eff}^{k}\leq d^{\gamma}$. Furthermore, one can check that the Assumptions listed in Theorem 1 in the main text verifies Assumption 1.

Similarly, for $w_{d}(d^{\gamma})\leq N\leq O_{d}(d^{\gamma+\delta})$ with $\delta>0$ constant sufficiently small, Theorem 6 implies that the ${\rm RF}$ models can only approximate $k$ polynomials in the first sphere such that $d_{\rm eff}^{k}\leq d^{\gamma}$. Furthermore, Assumptions listed in Theorem 2 in the main text verifies Assumption 2.

In the case of ${\rm NT}$, we only consider ${\bm{k}}=(k_{1},0)$ and $S({\bm{k}})=\{1\}$. We get $\min_{q\in S({\bm{k}})}\kappa_{q}=\kappa$. The subspace approximated is given by the $k$ polynomials in the first sphere such that $d_{\rm eff}^{k}\leq d^{\gamma}d_{\rm eff}$. Furthermore, Assumptions listed in Theorem 3 in the main text verifies Assumption 3.

Appendix D Proof of Theorem 5

The proof follows closely the proof of [GMMM19b, Theorem 4].

Let us rewrite the kernel functions $\{h_{d}\}_{d\geq 1}$ as functions on the product of normalized spheres: for ${\bm{x}}=\{{\bm{x}}^{(q)}\}_{q\in[Q]}$ and ${\bm{y}}=\{{\bm{y}}^{(q)}\}_{q\in[Q]}\in{\rm PS}^{\bm{d}}_{\bm{\kappa}}$:

Consider the expansion of $h_{{\bm{d}}}$ in terms of tensor product of Gegenbauer polynomials. We have

where the expectation is taken over $\overline{\bm{x}}=(\overline{\bm{x}}^{(1)},\ldots,\overline{\bm{x}}^{(Q)})\sim\mu_{{\bm{d}}}$.

Let $\{h_{d}\}_{d\geq 1}$ be a sequence of kernel functions that satisfies Assumption 1. Assume $w_{d}(d^{\gamma})\leq n\leq o_{d}(d^{m(\gamma)})$ for some $\gamma>0$. Consider ${\mathcal{Q}}=\overline{{\mathcal{Q}}}_{{\rm KRR}}(\gamma)$ as defined in Eq. (43). Then there exists constants $c,C>0$ such that for $d$ large enough,

where $\alpha_{q}=d_{q}^{-1/2}r_{q}^{2}/R^{2}=(1+o_{d}(1))d^{\eta_{q}/2+\kappa_{q}-\xi}$. By Assumption 1.$(a)$, we have

Furthermore, by Assumption 1.$(b)$ and dominated convergence,

for $k\geq\overline{K}$. The lemma then follows from the same proof as in Lemma 9 and Lemma 10, where we adapt the proofs of Lemma 19 and 20 to $h_{\bm{d}}$. ∎

D.2 Proof of Theorem 5

Step 1. Rewrite the ${\bm{y}}$, ${\bm{E}}$, ${\bm{H}}$, ${\bm{M}}$ matrices.

The test error of empirical kernel ridge regression gives

where ${\bm{E}}=(E_{1},\ldots,E_{n})^{\mathsf{T}}$ and ${\bm{M}}=(M_{ij})_{ij\in[n]}$, with

Let the spherical harmonics decomposition of $f_{d}$ be

and the Gegenbauer decomposition of $h_{{\bm{d}}}$ be

We write the decompositions of vectors ${\bm{f}}$, ${\bm{E}}$, ${\bm{H}}$, and ${\bm{M}}$. We have

The rest of the proof follows closely from [GMMM19b, Theorem 4]. We decompose the risk as follows

Further, we denote ${\bm{f}}_{{\mathcal{Q}}}$, ${\bm{f}}_{{\mathcal{Q}}^{c}}$, ${\bm{E}}_{{\mathcal{Q}}}$, and ${\bm{E}}_{{\mathcal{Q}}^{c}}$,

Using Cauchy Schwarz inequality for $T_{22}$, we get

As a result, combining Eqs. (58), (60) and (59), we have

where the last equality used the fact that $n\leq O_{d}(d^{m(\gamma)-\delta})$ and Lemma 2. Combining Eqs. (62), (63) and (64), we get

Step 5. Terms $T_{3},T_{4}$ and $T_{5}$. By Lemma 6 again, we have

We decompose $T_{5}$ using ${\bm{f}}={\bm{f}}_{{\mathcal{Q}}}+{\bm{f}}_{{\mathcal{Q}}^{c}}$,

Combining Eqs. (65), (61), (66), (67) and (68), we have

D.3 Auxiliary results

Assume that $n\geq w_{d}(d^{\gamma}\log d)$ and consider

Denote $A=\sum_{{\bm{k}}\in{\mathcal{R}}}B({\bm{d}},{\bm{k}})$ and

Notice that there exists $C>0$ such that $A\leq C\max_{{\bm{k}}\in{\mathcal{R}}}\prod_{q\in[Q]}d^{\eta_{q}k_{q}}\leq Cd^{\gamma}$ (by definition of $m(\gamma)$ and ${\mathcal{R}}$) and therefore $n\geq w_{d}(A\log A)$. Integrating the tail bound (69) proves the lemma. ∎

Let $\sigma$ be an activation function satisfying Assumption 1. Let $w_{d}(d^{\gamma}\log d)\leq n\leq O_{d}(d^{m(\gamma)-\delta})$ for some $\gamma>0$ and $\delta>0$. Then there exists sequences $\kappa_{h}$ and $\kappa_{u}$ such that

with $\kappa_{h}=\sum_{{\bm{k}}\in{\mathcal{S}}}\lambda^{\bm{d}}_{{\bm{k}}}(h_{{\bm{d}}})B({\bm{d}},{\bm{k}})=O_{d}(1)$. From Assumption 1.$(b)$ and a proof similar to Lemma 20, there exists ${\bm{k}}=(0,\ldots,k,\ldots,0)$ (for $k>L$ at position $q_{\xi}$) such that $\lim\inf_{d\to\infty}\lambda^{\bm{d}}_{{\bm{k}}}(h_{{\bm{d}}})B({\bm{d}},{\bm{k}})>0$. Hence, $\kappa_{h}=\Theta_{d}(1)$.

From Lemma 3 we have for ${\bm{k}}\in{\mathcal{R}}\cap{\mathcal{Q}}^{c}$,

Let $\sigma$ be an activation function satisfying Assumption 1. Assume $\omega_{d}(d^{\gamma}\log d)\leq n\leq O_{d}(d^{m(\gamma)-\delta})$ for some $\gamma>0$ and $\delta>0$. We have

Denote $B=\sum_{{\bm{k}}\in{\mathcal{Q}}}B({\bm{d}},{\bm{k}})$, and

Then, we can use the same proof as in [GMMM19b, Lemma 13] to bound $\|T_{1}\|_{{\rm op}}$ (recall $n=O_{d}(d^{m(\gamma)-\delta})$)

Let $\sigma$ be an activation function satisfying Assumption 1. Assume $\omega_{d}(d^{\gamma}\log d)\leq n\leq O_{d}(d^{m(\gamma)-\delta})$ for some $\gamma>0$ and $\delta>0$. We have

This lemma can be deduced directly from [GMMM19b, Lemma 14], by noticing that

Appendix E Proof of Theorem 6.(a): lower bound for the RF model

In the theorems, we show our results in high probability with respect to ${\bm{\Theta}}$. Hence, in the proof we will restrict the sample space to the high probability event $\mathcal{P}_{\varepsilon}\equiv\mathcal{P}_{d,N,\varepsilon}$ for $\varepsilon>0$ small enough, where

Assume $N=o(d^{\gamma})$ for some $\gamma>0$. We have for any fixed $\varepsilon>0$,

The tail inequality in Lemma 16 and the assumption $N=o(d^{\gamma})$ imply that there exists some constants $C,c>0$ such that

Consider the expansion of $\sigma_{{\bm{d}},{\bm{\tau}}}$ in terms of tensor product of Gegenbauer polynomials. We have

where the expectation is taken over $\overline{\bm{x}}=(\overline{\bm{x}}^{(1)},\ldots,\overline{\bm{x}}^{(Q)})\sim\mu_{{\bm{d}}}$.

Let $\sigma$ be an activation function that satisfies Assumptions 2.(a) and 2.(b). Consider $N\leq o_{d}(d^{\gamma})$ and ${\mathcal{Q}}={\mathcal{Q}}_{{\rm RF}}(\gamma)$ as defined in Theorem 6.(a). Then there exists $\varepsilon_{0}>0$ and $d_{0}$ and a constant $C>0$ such that for $d\geq d_{0}$ and ${\bm{\tau}}\in[1-\varepsilon_{0},1+\varepsilon_{0}]^{Q}$,

Notice that by Assumption 2.$(b)$ we can apply Lemma 19 to any ${\bm{k}}\in{\mathcal{Q}}^{c}$ such that $|{\bm{k}}|=k_{1}+\ldots+k_{Q}\leq L$. In particular, there exists $C>0$, $\varepsilon_{0}^{\prime}>0$ and $d_{0}^{\prime}$ such that for any ${\bm{k}}\in{\mathcal{Q}}^{c}$ with $|{\bm{k}}|\leq L$, $d\geq d_{0}^{\prime}$ and ${\bm{\tau}}\in[1-\varepsilon_{0}^{\prime},1+\varepsilon_{0}^{\prime}]^{Q}$,

Furthermore, using that $B({\bm{d}},{\bm{k}})=\Theta(d_{1}^{k_{1}}d_{2}^{k_{2}}\ldots d_{Q}^{k_{Q}})$, there exists $C^{\prime}>0$ such that for ${\bm{k}}\in{\mathcal{Q}}^{c}$ with $|{\bm{k}}|\leq L$,

where we used in the last inequality ${\bm{k}}\not\in{\mathcal{Q}}_{{\rm RF}}(\gamma)$ implies $(\xi-\kappa_{1})k_{1}+\ldots+(\xi-\kappa_{Q})k_{Q}\geq\gamma$ by definition.

Furthermore, from Assumption 2 and Lemma 17.$(b)$, there exists $\varepsilon_{0}^{\prime\prime}>0$, $d_{0}^{\prime\prime}$ and $C<\infty$, such that

In particular, for $|{\bm{k}}|=k_{1}+\ldots+k_{Q}>L=\max_{q\in[Q]}\lceil\gamma/\eta_{q}\rceil$, we have

Combining Eqs (79) and (80) yields the result. ∎

E.2 Proof of Theorem 6.(a): Outline

Define the random vectors ${\bm{V}}=(V_{1},\ldots,V_{N})^{\mathsf{T}}$, ${\bm{V}}_{{\mathcal{Q}}}=(V_{1,{\mathcal{Q}}},\ldots,V_{N,{\mathcal{Q}}})^{\mathsf{T}}$, ${\bm{V}}_{{\mathcal{Q}}^{c}}=(V_{1,{\mathcal{Q}}^{c}},\ldots,V_{N,{\mathcal{Q}}^{c}})^{\mathsf{T}}$, with

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

In what follows, we write $R_{{\rm RF}}(f_{d})=R_{{\rm RF}}(f_{d},{\bm{W}})=R_{{\rm RF}}(f_{d},{\bm{\Theta}}/\sqrt{D})$ for the random features risk, omitting the dependence on the weights ${\bm{W}}={\bm{\Theta}}/\sqrt{D}$. By the definition and a simple calculation, we have

where the last inequality used the fact that

The Theorem follows from the following two claims

This is achieved by the Proposition 1 and 2 stated below.

Let $\sigma$ be an activation function satisfying Assumptions 2.(a) and 2.(b) for a fixed $\gamma>0$. Denote ${\mathcal{Q}}={\mathcal{Q}}_{{\rm RF}}(\gamma)$. Let $\varepsilon>0$ and define ${\mathcal{E}}_{{\mathcal{Q}}^{c},\varepsilon}$ by

Then there exists a constant $C>0$ and $\varepsilon_{0}>0$ (depending only on the constants of Assumptions 2.(a) and 2.(b)) such that for $d$ sufficiently large,

The proofs of these two propositions are provided in the next sections.

Proposition 1 shows that there exists $\varepsilon_{0}>0$ such that

Hence, by Markov’s inequality, we get for any $\varepsilon>0$,

where we used Lemma 8. By assumption, we have $N=o_{d}(d^{\gamma})$, hence Eq. (86) is verified. Furthermore Eq. (87) follows simply from Proposition 2. This proves the theorem.

E.3 Proof of Proposition 1

such that $\overline{f}$ is a function on the normalized product of spheres ${\rm PS}^{\bm{d}}$ (Note that we defined ${\mathsf{P}}_{\bm{k}}f_{d}({\bm{x}})\equiv{\mathsf{P}}_{{\bm{k}}}\overline{f}_{d}(\overline{\bm{x}})$ the unambiguous polynomial approximation of $f_{d}$ with polynomial of degree ${\bm{k}}$). We have

We recall the expansion of $\sigma_{{\bm{d}},{\bm{\tau}}}$ in terms of tensor product of Gegenbauer polynomials

Using Eq. (39) to get the following property

Let $\varepsilon_{0}>0$ be a constant as specified in Lemma 9. We consider

From Lemma 9, there exists a constant $C>0$ such that for $d$ sufficiently large, we have for any ${\bm{k}}\in{\mathcal{Q}}^{c}$,

E.4 Proof of Proposition 2

Step 1. Construction of the activation functions $\hat{\sigma}$, $\bar{\sigma}$.

Without loss of generality, we will assume that $q_{\xi}=1$. From Assumption 2.$(b)$, $\sigma$ is not a degree $\lfloor\gamma/\eta_{1}\rfloor$-polynomial. This is equivalent to having $m\geq\lfloor\gamma/\eta_{1}\rfloor+1$ such that $\mu_{m}(\sigma)\neq 0$. Let us denote

Recall the expansion of $\sigma_{{\bm{d}},{\bm{\tau}}}$ in terms of product of Gegenbauer polynomials

Step 2. The kernel functions $u_{d}$, $\hat{u}_{d}$ and $\bar{u}_{d}$.

Let $u_{d}$, $\hat{u}_{d}$ and $\bar{u}_{d}$ be defined by

We immediately have $u_{{\bm{d}}}^{{\bm{\tau}}_{1},{\bm{\tau}}_{2}}=\hat{u}_{{\bm{d}}}^{{\bm{\tau}}_{1},{\bm{\tau}}_{2}}+\bar{u}_{{\bm{d}}}^{{\bm{\tau}}_{1},{\bm{\tau}}_{2}}$. Note that all three correspond to positive semi-definite kernels.

Since $\hat{\bm{U}}={\bm{U}}-\bar{\bm{U}}\succeq 0$, we immediately have ${\bm{U}}\succeq\bar{\bm{U}}$. In the following, we will lower bound $\bar{\bm{U}}$.

By the decomposition of $\bar{\bm{U}}$ in terms of Gegenbauer polynomials (93), we have

From Assumption 2.$(a)$ and Lemma 20 applied to coefficient ${\bm{m}}$, as well as the assumption that $\mu_{m}(\sigma)\neq 0$, there exists $\varepsilon_{0}>0$ and $C,c>0$ such that for $d$ large enough,

We restrict ourselves to the event $\mathcal{P}_{\varepsilon_{0}}$ defined in Eq. (76), which happens with high probability (Lemma 8). Hence from Eqs. (94) and (95), we deduce that with high probability

Appendix F Proof of Theorem 6.(b): upper bound for RF model

The first inequality comes simply from Assumption 2.$(a)$ and Lemma 17.$(b)$. For the second inequality, notice that by Assumption 2.$(c)$ we can apply Lemma 19 to any ${\bm{k}}\in{\mathcal{Q}}$. Hence (using that $\mu_{k}(\sigma)^{2}>0$ and we can choose $\delta$ sufficiently small), we deduce that there exists $c>0$, $\varepsilon_{0}>0$ and $d_{0}$ such that for any $d\geq d_{0}$, ${\bm{\tau}}\in[1-\varepsilon_{0},1+\varepsilon_{0}]^{Q}$ and ${\bm{k}}\in{\mathcal{Q}}$,

Furthermore, using that $B({\bm{d}},{\bm{k}})=\Theta(d_{1}^{k_{1}}d_{2}^{k_{2}}\ldots d_{Q}^{k_{Q}})$, there exists $c^{\prime}>0$ such that for any ${\bm{k}}\in{\mathcal{Q}}$,

where we used in the last inequality ${\bm{k}}\in\overline{{\mathcal{Q}}}_{{\rm RF}}(\gamma)$ implies $(\xi-\kappa_{1})k_{1}+\ldots+(\xi-\kappa_{Q})k_{Q}\leq\gamma$ by definition. ∎

F.2 Properties of the limiting kernel

Similarly to the proof of [GMMM19b, Theorem 1.$(b)$], we construct a limiting kernel which is used as a proxy to upper bound the RF risk.

We recall the decomposition of $\sigma_{{\bm{d}},{\bm{\tau}}}$ in terms of tensor product of Gegenbauer polynomials

F.3 Proof of Theorem 6.(b)

Without loss of generality, let us assume that $\{f_{d}\}$ are polynomials contained in $V^{\bm{d}}_{{\mathcal{Q}}}$, i.e. $\overline{f}_{d}={\mathsf{P}}_{{\mathcal{Q}}}\overline{f}_{d}$.