# Generalization in Kernel Regression Under Realistic Assumptions

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 50 of its 76 references that are in the map.
- First posted on arXiv 26 Dec 2023.

## Builds on (most cited first, 30 of 50)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Reconciling modern machine learning practice and the bias-variance trade-off](https://mlsanity.com/paper/1812.11118/) (2018)
- [Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent](https://mlsanity.com/paper/1902.06720/) (2019)
- [Deep Neural Networks as Gaussian Processes](https://mlsanity.com/paper/1711.00165/) (2017)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Spectrum Dependent Learning Curves in Kernel Regression and Wide Neural Networks](https://mlsanity.com/paper/2002.02561/) (2020)
- [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)
- [Towards Understanding the Spectral Bias of Deep Learning](https://mlsanity.com/paper/1912.01198/) (2019)
- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Linearized two-layers neural networks in high dimension](https://mlsanity.com/paper/1904.12191/) (2019)
- [High-Dimensional Asymptotics of Prediction: Ridge Regression and Classification](https://mlsanity.com/paper/1507.03003/) (2015)
- [The Convergence Rate of Neural Networks for Learned Functions of Different Frequencies](https://mlsanity.com/paper/1906.00425/) (2019)
- [Generalisation error in learning with random features and the hidden manifold model](https://mlsanity.com/paper/2002.09339/) (2020)
- [Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm](https://mlsanity.com/paper/1702.07254/) (2017)
- [Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentration](https://mlsanity.com/paper/2101.10588/) (2021)
- [On the Optimal Weighted ℓ2 Regularization in Overparameterized Linear Regression](https://mlsanity.com/paper/2006.05800/) (2020)
- [Generalization Error Rates in Kernel Regression: The Crossover from the Noiseless to Noisy Regime](https://mlsanity.com/paper/2105.15004/) (2021)
- [Tight Bounds on the Smallest Eigenvalue of the Neural Tangent Kernel for Deep ReLU Networks](https://mlsanity.com/paper/2012.11654/) (2020)
- [Deep Equals Shallow for ReLU Networks in Kernel Regimes](https://mlsanity.com/paper/2009.14397/) (2020)
- [The Interpolation Phase Transition in Neural Networks: Memorization and Generalization under Lazy Training](https://mlsanity.com/paper/2007.12826/) (2020)
- [Spectra of the Conjugate Kernel and Neural Tangent Kernel for linear-width neural networks](https://mlsanity.com/paper/2005.11879/) (2020)
- [Deep Neural Tangent Kernel and Laplace Kernel Have the Same RKHS](https://mlsanity.com/paper/2009.10683/) (2020)
- [A Continuous-Time View of Early Stopping for Least Squares](https://mlsanity.com/paper/1810.10082/) (2018)
- [A Fine-Grained Spectral Perspective on Neural Networks](https://mlsanity.com/paper/1907.10599/) (2019)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces](https://mlsanity.com/paper/1801.06720/) (2018)
- [Tensor Programs IIb: Architectural Universality of Neural Tangent Kernel Training Dynamics](https://mlsanity.com/paper/2105.03703/) (2021)

## Built on by (most cited first, 27 of 27)

- [Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum](https://mlsanity.com/paper/2402.01297/) (2024)
- [The phase diagram of kernel interpolation in large dimensions](https://mlsanity.com/paper/2404.12597/) (2024)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [A Comprehensive Analysis on the Learning Curve in Kernel Ridge Regression](https://mlsanity.com/paper/2410.17796/) (2024)
- [Provable Tempered Overfitting of Minimal Nets and Typical Nets](https://mlsanity.com/paper/2410.19092/) (2024)
- [Determinant Estimation under Memory Constraints and Neural Scaling Laws](https://mlsanity.com/paper/2503.04424/) (2025)
- [Learning Curves of Stochastic Gradient Descent in Kernel Regression](https://mlsanity.com/paper/2505.22048/) (2025)
- [Optimal Rates and Saturation for Noiseless Kernel Ridge Regression](https://mlsanity.com/paper/2402.15718/) (2024)
- [When Bias Pretends to Be Truth: How Spurious Correlations Undermine Hallucination Detection in LLMs](https://mlsanity.com/paper/2511.07318/) (2025)
- [On the Pinsker bound of inner product kernel regression in large dimensions](https://mlsanity.com/paper/2409.00915/) (2024)
- [Generalization for Least Squares Regression With Simple Spiked Covariances](https://mlsanity.com/paper/2410.13991/) (2024)
- [Beyond Benign Overfitting in Nadaraya-Watson Interpolators](https://mlsanity.com/paper/2502.07480/) (2025)
- [On the Saturation Effects of Spectral Algorithms in Large Dimensions](https://mlsanity.com/paper/2503.00504/) (2025)
- [Benign Overfitting with Quantum Kernels](https://mlsanity.com/paper/2503.17020/) (2025)
- [Beyond Real Data: Synthetic Data through the Lens of Regularization](https://mlsanity.com/paper/2510.08095/) (2025)
- [Simple Relative Deviation Bounds for Covariance and Gram Matrices](https://mlsanity.com/paper/2410.05754/) (2024)
- [Generalisation and benign over-fitting for linear regression onto random functional covariates](https://mlsanity.com/paper/2508.13895/) (2025)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Benign overfitting in Fixed Dimension via Physics-Informed Learning with Smooth Inductive Bias](https://mlsanity.com/paper/2406.09194/) (2024)
- [Towards a Statistical Understanding of Neural Networks: Beyond the Neural Tangent Kernel Theories](https://mlsanity.com/paper/2412.18756/) (2024)
- [Querying Kernel Methods Suffices for Reconstructing their Training Data](https://mlsanity.com/paper/2505.19019/) (2025)
- [Spectral Analysis of Molecular Features: When Richer Features Do Not Guarantee Better Generalization](https://mlsanity.com/paper/2510.14217/) (2025)
- [Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions](https://mlsanity.com/paper/2604.23212/) (2026)
- [Large Dimensional Kernel Ridge Regression: Extending to Product Kernels](https://mlsanity.com/paper/2605.14524/) (2026)
- [On Kernel Eigen-alignments of KRR: Reconstruction and Generalization](https://mlsanity.com/paper/2605.15240/) (2026)
- [Benign Overfitting for General Norms and Distributions](https://mlsanity.com/paper/2609.33675/) (2026)

## Abstract (arXiv)

It is by now well-established that modern over-parameterized models seem to elude the bias-variance tradeoff and generalize well despite overfitting noise. Many recent works attempt to analyze this phenomenon in the relatively tractable setting of kernel regression. However, as we argue in detail, most past works on this topic either make unrealistic assumptions, or focus on a narrow problem setup. This work aims to provide a unified theory to upper bound the excess risk of kernel regression for nearly all common and realistic settings. Specifically, we provide rigorous bounds that hold for common kernels and for any amount of regularization, noise, any input dimension, and any number of samples. Furthermore, we provide relative perturbation bounds for the eigenvalues of kernel matrices, which may be of independent interest. These reveal a self-regularization phenomenon, whereby a heavy tail in the eigendecomposition of the kernel provides it with an implicit form of regularization, enabling good generalization. When applied to common kernels, our results imply benign overfitting in high input dimensions, nearly tempered overfitting in fixed dimensions, and explicit convergence rates for regularized regression. As a by-product, we obtain time-dependent bounds for neural networks trained in the kernel regime.