Linearized two-layers neural networks in high dimension

By Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, Andrea Montanari. 2019

274 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Model Architectures, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

In Model Architectures

In Statistical Learning Theory

Citations in the corpus

When do neural networks outperform kernel methods? (2020, methodology): “Our analysis is analogous and generalizes the recent results of [17].”
Generalization Guarantees for Neural Networks via Harnessing the Low-rank Structure of the Jacobian (2019, background): “This is particularly important in light of a few recent literature [17, 23, 56] suggesting a significant gap between generalization capabilities of kernel methods/linearized neural nets when compared with neural nets operating beyond a linear or NTK learning regime (e.”
Scaling Laws for Neural Machine Translation (2021, background): “…theoretical understanding of the factors governing the quality and training dynamics of large neural networks has also being developing (Advani et al., 2020; Rosenfeld et al., 2019; Geiger et al., 2020; Ghorbani et al., 2021; Cho, 2020; Hutter, 2021; Bahri et al., 2021; Loureiro et al., 2021).”
On Lazy Training in Differentiable Programming (2018, background): “Other works in this line of research have appeared since the first version of this article was communicated, studying the optimization and statistical properties of various neural networks architectures in what we refer to as the lazy regime [5, 33, 32, 29, 46, 8, 27, 16, 4, 43].”
Towards Understanding Ensemble, Knowledge Distillation and Self-Distillation in Deep Learning (2020, background): “, ensemble) in deep learning works very differently from model averaging in random feature mappings — in particular, different from the neural tangent kernel (NTK) approach [3, 6, 7, 9, 10, 20, 25, 27, 28, 40, 41, 45, 55, 59, 86, 92].”
A Fine-Grained Spectral Perspective on Neural Networks (2019, background): “Finally, we note that several recent works (Basri et al., 2019; Bietti and Mairal, 2019; Ghorbani et al., 2019; Xie et al., 2016) studied one-hidden layer neural networks over the sphere, building on Smola et al.”
Neural Kernels Without Tangents (2020, background): “Recent research has drawn exciting connections between neural networks and kernel methods, providing new insights into training dynamics, generalization, and expressibility [1, 7, 11, 12, 14, 16, 21].”
Proving the Lottery Ticket Hypothesis: Pruning is All You Need (2020, background): “A few recent works (e.g. [36], [12], [11]) studied the limitations of random features.”
On the Power and Limitations of Random Features for Understanding Neural Networks (2019, background): “[17] studied the representation capabilities of random features, and showed that in high dimensions random features are not good at fitting high degree polynomials.”
Limitations of Lazy Training of Two-layers Neural Networks (2019, background): “In particular, [14] shows that, if the feature vectors xi are uniformly random over the d-dimensional sphere, and N, d are large with N = O(d), then FRF,N (W ) can only capture linear functions, while FNT,N (W ) can only capture quadratic functions.”
On the Similarity between the Laplace and Neural Tangent Kernels (2020, background): “[24] studied approximation bounds for two layer neural networks, and [8, 9, 13, 32] studied generalization properties of kernel methods in the context of neural networks.”
Generalization of Two-layer Neural Networks: An Asymptotic Viewpoint (2020, background): “In the student-teacher setup, Tian (2017); Zhong et al. (2017), Ghorbani et al. (2019b;a) showed that kernel models in high dimensions perform no better than low-degree polynomials on the input or two-layer neural network.”
Mean-field Behaviour of Neural Tangent Kernel for Deep Neural Networks (2019, background): “Indeed, recent works have shown that the NTK for ﬁnite width neural networks changes with time (Chizat and Bach, 2018; Ghorbani et al., 2019; Huang and Yau, 2020), and might even be random as shown by (Hanin and Nica, 2019) where authors prove that in the limit n, L → ∞ (where n is a width of the…”
Surprises in High-Dimensional Ridgeless Least Squares Interpolation (2019, methodology): “For example, recent work has investigated interpolation—via kernel ridge regression—in reproducing kernel Hilbert spaces [30, 47].”