When do neural networks outperform kernel methods?

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

214 citations recorded by the source corpus.

For a certain scaling of the initialization of stochastic gradient descent (SGD), wide neural networks (NN) have been shown to be well approximated by reproducing kernel Hilbert space (RKHS) methods. Recent empirical work showed that, for some classification tasks, RKHS methods can replace NNs without a large loss in performance. On the other hand, two-layers NNs are known to encode richer smoothness classes than RKHS and we know of special examples for which SGD-trained NN provably outperform RKHS. This is true even in the wide network limit, for a different scaling of the initialization. How can we reconcile the above claims? For which tasks do NNs outperform RKHS? If covariates are nearly isotropic, RKHS methods suffer from the curse of dimensionality, while NNs can overcome it by learning the best low-dimensional representation. Here we show that this curse of dimensionality becomes milder if the covariates display the same low-dimensional structure as the target function, and we precisely characterize this tradeoff. Building on these results, we present the spiked covariates model that can capture in a unified framework both behaviors observed in earlier work. We hypothesize that such a latent low-dimensional structure is present in image classification. We test numerically this hypothesis by showing that specific perturbations of the training distribution degrade the performances of RKHS methods much more significantly than NNs.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, 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 Statistical Learning Theory

Citations in the corpus

LoRA: Low-Rank Adaptation of Large Language Models (2021, background): “In theory literature, it is known that neural networks outperform other classical learning methods, including the corresponding (finite-width) neural tangent kernels [5, 22] when the underlying concept class has certain low-rank structure [2, 3, 11].”
Spectral Analysis of the Neural Tangent Kernel for Deep Residual Networks (2021, background): “For example, (Liang et al., 2020; 2019; Pagliana et al., 2020) analyzed the bias-variance interplay of minimum norm interpolation with a growing number of samples when the dimension is either ﬁxed or growing at the same rate.”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, methodology): “In this case, our model is closely related to the mismatched models in [12] and [25].”