Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks

Abstract

We derive analytical expressions for the generalization performance of kernel regression as a function of the number of training samples using theoretical methods from Gaussian processes and statistical physics. Our expressions apply to wide neural networks due to an equivalence between training them and kernel regression with the Neural Tangent Kernel (NTK). By computing the decomposition of the total generalization error due to different spectral components of the kernel, we identify a new spectral principle: as the size of the training set grows, kernel machines and neural networks fit successively higher spectral modes of the target function. When data are sampled from a uniform distribution on a high-dimensional hypersphere, dot product kernels, including NTK, exhibit learning stages where different frequency modes of the target function are learned. We verify our theory with simulations on synthetic data and MNIST dataset.

arXiv commentICML 2020 Update: Updated section on asymptotics generalization error for power law spectra, finding agreement with Spigler, Geiger, Wyart 2019 arXiv:1905.10843. Added a section on Discrete measures and an MNIST Experiment. Eigenvalue problem can be approximated by Kernel PCA. Typo fixed on 2/25/2021

References in corpus (10)

• Reconciling modern machine learning practice and the bias-variance trade-off
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks
• Deep Learning Scaling is Predictable, Empirically
• On Exact Computation with an Infinitely Wide Neural Net
• On the Spectral Bias of Neural Networks
• Overfitting or perfect fitting? Risk bounds for classification and regression rules that interpolate
• Statistical Mechanics of Support Vector Networks
• Towards Understanding the Spectral Bias of Deep Learning
• Explicitizing an Implicit Bias of the Frequency Principle in Two-layer Neural Networks

Cited by in corpus (14)

• Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
• Explaining Neural Scaling Laws
• Towards Understanding the Spectral Bias of Deep Learning
• Learning curves of generic features maps for realistic datasets with a teacher-student model
• Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• On the Similarity between the Laplace and Neural Tangent Kernels
• Generalization bounds for deep learning
• Energy-information trade-off makes the cortical critical power law the optimal coding
• Deep frequency principle towards understanding why deeper learning is faster
• An analytic theory of shallow networks dynamics for hinge loss classification
• How isotropic kernels perform on simple invariants
• Fourier-domain Variational Formulation and Its Well-posedness for Supervised Learning