Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks

Abstract

Generalization beyond a training dataset is a main goal of machine learning, but theoretical understanding of generalization remains an open problem for many models. The need for a new theory is exacerbated by recent observations in deep neural networks where overparameterization leads to better performance, contradicting the conventional wisdom from classical statistics. In this paper, we investigate generalization error for kernel regression, which, besides being a popular machine learning method, also includes infinitely overparameterized neural networks trained with gradient descent. We use techniques from statistical mechanics to derive an analytical expression for generalization error applicable to any kernel or data distribution. We present applications of our theory to real and synthetic datasets, and for many kernels including those that arise from training deep neural networks in the infinite-width limit. We elucidate an inductive bias of kernel regression to explain data with "simple functions", which are identified by solving a kernel eigenfunction problem on the data distribution. This notion of simplicity allows us to characterize whether a kernel is compatible with a learning task, facilitating good generalization performance from a small number of training examples. We show that more data may impair generalization when noisy or not expressible by the kernel, leading to non-monotonic learning curves with possibly many peaks. To further understand these phenomena, we turn to the broad class of rotation invariant kernels, which is relevant to training deep neural networks in the infinite-width limit, and present a detailed mathematical analysis of them when data is drawn from a spherically symmetric distribution and the number of input dimensions is large.

arXiv commentAccepted for publication in Nature Communications. SI Eq.71 is corrected

References in corpus (8)

• Reconciling modern machine learning practice and the bias-variance trade-off
• GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding
• Statistical Mechanics of Support Vector Networks
• Just Interpolate: Kernel "Ridgeless" Regression Can Generalize
• A jamming transition from under- to over-parametrization affects loss landscape and generalization
• Neural Tangents: Fast and Easy Infinite Neural Networks in Python
• Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm
• Deep learning versus kernel learning: an empirical study of loss landscape geometry and the time evolution of the Neural Tangent Kernel

Cited by in corpus (32)

• Generalization in Quantum Machine Learning: a Quantum Information Perspective
• Explaining Neural Scaling Laws
• Efficient measure for the expressivity of variational quantum algorithms
• Representation Learning via Quantum Neural Tangent Kernels
• A statistical mechanics framework for Bayesian deep neural networks beyond the infinite-width limit
• Noisy Quantum Kernel Machines
• Contrasting random and learned features in deep Bayesian linear regression
• Tackling Sampling Noise in Physical Systems for Machine Learning Applications: Fundamental Limits and Eigentasks
• Numerical evidence against advantage with quantum fidelity kernels on classical data
• Locality defeats the curse of dimensionality in convolutional teacher-student scenarios
• Deep neural networks have an inbuilt Occam's razor
• Automatic and effective discovery of quantum kernels
• Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime
• Laziness, Barren Plateau, and Noise in Machine Learning
• Dimensionality reduction, regularization, and generalization in overparameterized regressions
• Random features and polynomial rules
• Gradient domain machine learning with composite kernels: improving the accuracy of PES and force fields for large molecules
• Energy-information trade-off makes the cortical critical power law the optimal coding
• Error Scaling Laws for Kernel Classification under Source and Capacity Conditions
• Statistical Mechanics of Support Vector Regression
• Quantum Kerr Learning
• On the similarity of bandwidth-tuned quantum kernels and classical kernels
• Nadaraya-Watson kernel smoothing as a random energy model
• Wilsonian Renormalization of Neural Network Gaussian Processes
• Uncertainty Quantification From Scaling Laws in Deep Neural Networks
• Generalization Bounds in Hybrid Quantum-Classical Machine Learning Models
• Simplified derivations for high-dimensional convex learning problems
• Equivalence between exponential concentration in quantum machine learning kernels and barren plateaus in variational algorithms
• New perspectives on quantum kernels through the lens of entangled tensor kernels
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation