Linearized two-layers neural networks in high dimension

We consider the problem of learning an unknown function $f_{\star}$ on the $d$-dimensional sphere with respect to the square loss, given i.i.d. samples $\{(y_i,{\boldsymbol x}_i)\}_{i\le n}$ where ${\boldsymbol x}_i$ is a feature vector uniformly distributed on the sphere and $y_i=f_{\star}({\boldsymbol x}_i)$. We study two popular classes of models that can be regarded as linearizations of two-layers neural networks around a random initialization: (RF) The random feature model of Rahimi-Recht; (NT) The neural tangent kernel model of Jacot-Gabriel-Hongler. Both these approaches can also be regarded as randomized approximations of kernel ridge regression (with respect to different kernels), and hence enjoy universal approximation properties when the number of neurons $N$ diverges, for a fixed dimension $d$. We prove that, if both $d$ and $N$ are large, the behavior of these models is instead remarkably simpler. If $N \le d^{2-\delta_d}$ for $\delta_d^2\log d\to\infty$, then RF performs no better than linear regression with respect to the raw features ${\boldsymbol x}_i$, and NT performs no better than linear regression with respect to degree-one and two monomials in the ${\boldsymbol x}_i$. More generally, if $N\le d^{\ell+1-\delta_d}$ then RF fits at most a degree-$\ell$ polynomial in the raw features, and NT fits at most a degree-$(\ell+1)$ polynomial. As a direct consequence of our main theorem, we obtain an equally simple bound on the generalization error of Kernel Ridge Regression (KRR). In the same setting of ${\boldsymbol x}_i$ i.i.d. uniformly distributed on the sphere and for any rotational-invariant kernel, if the number of samples is $n \le d^{\ell +1-\delta_d}$, then KRR only captures degree-$\ell$ polynomials in the raw features.