When Do Neural Networks Outperform Kernel Methods?

Abstract

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.

100 pages, 12 figures

References in corpus (6)

• Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• An Investigation into Neural Net Optimization via Hessian Eigenvalue Density
• Enhanced Convolutional Neural Tangent Kernels
• Mean Field Limit of the Learning Dynamics of Multilayer Neural Networks
• Neural Kernels Without Tangents

Cited by in corpus (22)

• LoRA: Low-Rank Adaptation of Large Language Models
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Learning with invariances in random features and kernel models
• The Quantum Path Kernel: a Generalized Quantum Neural Tangent Kernel for Deep Quantum Machine Learning
• Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration
• Kernel Two-Sample Tests in High Dimension: Interplay Between Moment Discrepancy and Dimension-and-Sample Orders
• Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstruction
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Analysis of feature learning in weight-tied autoencoders via the mean field lens
• Relative stability toward diffeomorphisms indicates performance in deep nets
• Noether: The More Things Change, the More Stay the Same
• On Energy-Based Models with Overparametrized Shallow Neural Networks
• Neural Tangent Kernel Maximum Mean Discrepancy
• Efficient Online Bayesian Inference for Neural Bandits
• Benefit of deep learning with non-convex noisy gradient descent: Provable excess risk bound and superiority to kernel methods
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Deep Networks Provably Classify Data on Curves
• Understanding Deflation Process in Over-parametrized Tensor Decomposition
• Analytic Study of Families of Spurious Minima in Two-Layer ReLU Neural Networks: A Tale of Symmetry II
• Classification and Adversarial examples in an Overparameterized Linear Model: A Signal Processing Perspective
• Minimum complexity interpolation in random features models
• How rotational invariance of common kernels prevents generalization in high dimensions