Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration

Abstract

Consider the classical supervised learning problem: we are given data $(y_i,{\mathbf{x}}_i)$, $i\le n$, with $y_i$ a response and ${\mathbf{x}}_i\in \mathcal{X}$ a covariates vector, and try to learn a model $f:\mathcal{X}\to \mathbb{R}$ to predict future responses. Random features methods map the covariates vector ${\mathbf{x}}_i$ to a point $\mathbf{\varphi }({\mathbf{x}}_i)$ in a higher dimensional space ${\mathbb{R}}^N$, via a random featurization map $\mathbf{\varphi }$. We study the use of random features methods in conjunction with ridge regression in the feature space ${\mathbb{R}}^N$. This can be viewed as a finite-dimensional approximation of kernel ridge regression (KRR), or as a stylized model for neural networks in the so called lazy training regime. We define a class of problems satisfying certain spectral conditions on the underlying kernels, and a hypercontractivity assumption on the associated eigenfunctions. These conditions are verified by classical high-dimensional examples. Under these conditions, we prove a sharp characterization of the error of random features ridge regression. In particular, we address two fundamental questions: $(1)$~What is the generalization error of KRR? $(2)$~How big $N$ should be for the random features approximation to achieve the same error as KRR? In this setting, we prove that KRR is well approximated by a projection onto the top $\ell$ eigenfunctions of the kernel, where $\ell$ depends on the sample size $n$. We show that the test error of random features ridge regression is dominated by its approximation error and is larger than the error of KRR as long as $N\le n^{1-\delta }$ for some $\delta >0$. We characterize this gap. For $N\ge n^{1+\delta }$, random features achieve the same error as the corresponding KRR, and further increasing $N$ does not lead to a significant change in test error.

77 pages; 1 pdf figure

References in corpus (14)

• Reconciling modern machine learning practice and the bias-variance trade-off
• A Convergence Theory for Deep Learning via Over-Parameterization
• Gradient Descent Provably Optimizes Over-parameterized Neural Networks
• Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks
• The generalization error of random features regression: Precise asymptotics and double descent curve
• Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks
• Gradient Descent Finds Global Minima of Deep Neural Networks
• Generalization Properties of Learning with Random Features
• Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers
• Towards moderate overparameterization: global convergence guarantees for training shallow neural networks
• Benign overfitting in ridge regression
• When Do Neural Networks Outperform Kernel Methods?
• Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't
• Kernel Alignment Risk Estimator: Risk Prediction from Training Data

Cited by in corpus (13)

• Classifying high-dimensional Gaussian mixtures: Where kernel methods fail and neural networks succeed
• Learning with invariances in random features and kernel models
• Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond
• A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning
• Conditioning of Random Feature Matrices: Double Descent and Generalization Error
• Exact Gap between Generalization Error and Uniform Convergence in Random Feature Models
• Learning with convolution and pooling operations in kernel methods
• The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods
• Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks
• Deep Networks Provably Classify Data on Curves
• Harmless interpolation in regression and classification with structured features
• Minimum complexity interpolation in random features models
• How rotational invariance of common kernels prevents generalization in high dimensions