# When Do Neural Networks Outperform Kernel Methods?

arXiv: https://arxiv.org/abs/2006.13409 · HTML: https://mlsanity.com/paper/2006.13409/

## Key facts

- Cited by 150 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

## Built on by (most cited first, 30 of 150)

- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [Neural Networks can Learn Representations with Gradient Descent](https://mlsanity.com/paper/2206.15144/) (2022)
- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Challenges in Training PINNs: A Loss Landscape Perspective](https://mlsanity.com/paper/2402.01868/) (2024)
- [Efficient Dataset Distillation Using Random Feature Approximation](https://mlsanity.com/paper/2210.12067/) (2022)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction](https://mlsanity.com/paper/2106.15013/) (2021)
- [Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed](https://mlsanity.com/paper/2102.11742/) (2021)
- [How Two-Layer Neural Networks Learn, One (Giant) Step at a Time](https://mlsanity.com/paper/2305.18270/) (2023)
- [Neural Networks Efficiently Learn Low-Dimensional Representations with SGD](https://mlsanity.com/paper/2209.14863/) (2022)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [How Feature Learning Can Improve Neural Scaling Laws](https://mlsanity.com/paper/2409.17858/) (2024)
- [The Benefits of Reusing Batches for Gradient Descent in Two-Layer Networks: Breaking the Curse of Information and Leap Exponents](https://mlsanity.com/paper/2402.03220/) (2024)
- [Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networks](https://mlsanity.com/paper/2112.03968/) (2021)
- [Neural networks trained with SGD learn distributions of increasing complexity](https://mlsanity.com/paper/2211.11567/) (2022)
- [What can linearized neural networks actually say about generalization?](https://mlsanity.com/paper/2106.06770/) (2021)
- [The Shaped Transformer: Attention Models in the Infinite Depth-and-Width Limit](https://mlsanity.com/paper/2306.17759/) (2023)
- [Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression](https://mlsanity.com/paper/2204.10425/) (2022)
- [Quantifying the Benefit of Using Differentiable Learning over Tangent Kernels](https://mlsanity.com/paper/2103.01210/) (2021)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Asymptotics of feature learning in two-layer networks after one gradient-step](https://mlsanity.com/paper/2402.04980/) (2024)
- [Repetita Iuvant: Data Repetition Allows SGD to Learn High-Dimensional Multi-Index Functions](https://mlsanity.com/paper/2405.15459/) (2024)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Limitations of the NTK for Understanding Generalization in Deep Learning](https://mlsanity.com/paper/2206.10012/) (2022)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)

## Abstract (arXiv)

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.