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

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

## Key facts

- Cited by 110 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 38 references that are in the map.
- First posted on arXiv 26 Jan 2021.

## Builds on (most cited first, 21 of 21)

- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Gradient Descent Finds Global Minima of Deep Neural Networks](https://mlsanity.com/paper/1811.03804/) (2018)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Benign Overfitting in Linear Regression](https://mlsanity.com/paper/1906.11300/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [The generalization error of random features regression: Precise asymptotics and double descent curve](https://mlsanity.com/paper/1908.05355/) (2019)
- [Learning and Generalization in Overparameterized Neural Networks, Going Beyond Two Layers](https://mlsanity.com/paper/1811.04918/) (2018)
- [Learning Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [Towards moderate overparameterization: global convergence guarantees for training shallow neural networks](https://mlsanity.com/paper/1902.04674/) (2019)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [Stochastic Gradient Descent Optimizes Over-parameterized Deep ReLU Networks](https://mlsanity.com/paper/1811.08888/) (2018)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Does data interpolation contradict statistical optimality?](https://mlsanity.com/paper/1806.09471/) (2018)
- [Towards a Mathematical Understanding of Neural Network-Based Machine Learning: what we know and what we don't](https://mlsanity.com/paper/2009.10713/) (2020)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)

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

- [High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation](https://mlsanity.com/paper/2205.01445/) (2022)
- [Learning Single-Index Models with Shallow Neural Networks](https://mlsanity.com/paper/2210.15651/) (2022)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (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)
- [A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning](https://mlsanity.com/paper/2109.02355/) (2021)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [Scaling and renormalization in high-dimensional regression](https://mlsanity.com/paper/2405.00592/) (2024)
- [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)
- [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)
- [Memorization and Optimization in Deep Neural Networks with Minimum Over-parameterization](https://mlsanity.com/paper/2205.10217/) (2022)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Random feature neural networks learn Black-Scholes type PDEs without curse of dimensionality](https://mlsanity.com/paper/2106.08900/) (2021)
- [How rotational invariance of common kernels prevents generalization in high dimensions](https://mlsanity.com/paper/2104.04244/) (2021)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Are Gaussian data all you need? Extents and limits of universality in high-dimensional generalized linear estimation](https://mlsanity.com/paper/2302.08923/) (2023)
- [Nonparametric regression using over-parameterized shallow ReLU neural networks](https://mlsanity.com/paper/2306.08321/) (2023)
- [Error Bounds for Learning with Vector-Valued Random Features](https://mlsanity.com/paper/2305.17170/) (2023)
- [The Three Stages of Learning Dynamics in High-Dimensional Kernel Methods](https://mlsanity.com/paper/2111.07167/) (2021)
- [Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression](https://mlsanity.com/paper/2205.14846/) (2022)
- [Deformed semicircle law and concentration of nonlinear random matrices for ultra-wide neural networks](https://mlsanity.com/paper/2109.09304/) (2021)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)
- [Bayesian Interpolation with Deep Linear Networks](https://mlsanity.com/paper/2212.14457/) (2022)
- [Operator Learning Using Random Features: A Tool for Scientific Computing](https://mlsanity.com/paper/2408.06526/) (2024)
- [Six Lectures on Linearized Neural Networks](https://mlsanity.com/paper/2308.13431/) (2023)
- [Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regime](https://mlsanity.com/paper/2205.06798/) (2022)
- [Provable Guarantees for Nonlinear Feature Learning in Three-Layer Neural Networks](https://mlsanity.com/paper/2305.06986/) (2023)
- [More is Better in Modern Machine Learning: when Infinite Overparameterization is Optimal and Overfitting is Obligatory](https://mlsanity.com/paper/2311.14646/) (2023)

## Abstract (arXiv)

Consider the classical supervised learning problem: we are given data (yi,boldsymbol xi), i≤ n, with yi a response and boldsymbol xi∈ mathcal X a covariates vector, and try to learn a model f:mathcal X→mathbb R to predict future responses. Random features methods map the covariates vector boldsymbol xi to a point boldsymbol φ(boldsymbol xi) in a higher dimensional space mathbb RN, via a random featurization map boldsymbol φ. We study the use of random features methods in conjunction with ridge regression in the feature space mathbb RN. 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 ℓ eigenfunctions of the kernel, where ℓ 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≤ n1-δ for some δ>0. We characterize this gap. For N≥ n1+δ, random features achieve the same error as the corresponding KRR, and further increasing N does not lead to a significant change in test error.