# Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regression

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

## Key facts

- Cited by 45 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 21 Apr 2022.

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

- [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)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [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 Overparameterized Neural Networks via Stochastic Gradient Descent on Structured Data](https://mlsanity.com/paper/1808.01204/) (2018)
- [To understand deep learning we need to understand kernel learning](https://mlsanity.com/paper/1802.01396/) (2018)
- [When Do Neural Networks Outperform Kernel Methods?](https://mlsanity.com/paper/2006.13409/) (2020)
- [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)
- [Learning with invariances in random features and kernel models](https://mlsanity.com/paper/2102.13219/) (2021)
- [On the Convergence Rate of Training Recurrent Neural Networks](https://mlsanity.com/paper/1810.12065/) (2018)
- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Asymptotics of Ridge (less) Regression under General Source Condition](https://mlsanity.com/paper/2006.06386/) (2020)
- [Kernel Alignment Risk Estimator: Risk Prediction from Training Data](https://mlsanity.com/paper/2006.09796/) (2020)
- [Optimal ridge penalty for real-world high-dimensional data can be zero or negative due to the implicit ridge regularization](https://mlsanity.com/paper/1805.10939/) (2018)
- [Consistency of Interpolation with Laplace Kernels is a High-Dimensional Phenomenon](https://mlsanity.com/paper/1812.11167/) (2018)
- [Kernel regression in high dimensions: Refined analysis beyond double descent](https://mlsanity.com/paper/2010.02681/) (2020)
- [Learning with convolution and pooling operations in kernel methods](https://mlsanity.com/paper/2111.08308/) (2021)

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

- [Grokking as the Transition from Lazy to Rich Training Dynamics](https://mlsanity.com/paper/2310.06110/) (2023)
- [Scaling and renormalization in high-dimensional regression](https://mlsanity.com/paper/2405.00592/) (2024)
- [A Theory of Non-Linear Feature Learning with One Gradient Step in Two-Layer Neural Networks](https://mlsanity.com/paper/2310.07891/) (2023)
- [Bayes-optimal Learning of Deep Random Networks of Extensive-width](https://mlsanity.com/paper/2302.00375/) (2023)
- [Deterministic equivalent and error universality of deep random features learning](https://mlsanity.com/paper/2302.00401/) (2023)
- [Universality laws for Gaussian mixtures in generalized linear models](https://mlsanity.com/paper/2302.08933/) (2023)
- [An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalings](https://mlsanity.com/paper/2205.06308/) (2022)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Asymptotics of Random Feature Regression Beyond the Linear Scaling Regime](https://mlsanity.com/paper/2403.08160/) (2024)
- [Precise Learning Curves and Higher-Order Scaling Limits for Dot Product Kernel Regression](https://mlsanity.com/paper/2205.14846/) (2022)
- [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)
- [On the non-universality of deep learning: quantifying the cost of symmetry](https://mlsanity.com/paper/2208.03113/) (2022)
- [Characterizing Overfitting in Kernel Ridgeless Regression Through the Eigenspectrum](https://mlsanity.com/paper/2402.01297/) (2024)
- [Noisy Interpolation Learning with Shallow Univariate ReLU Networks](https://mlsanity.com/paper/2307.15396/) (2023)
- [Optimal Rate of Kernel Regression in Large Dimensions](https://mlsanity.com/paper/2309.04268/) (2023)
- [Optimal Rates of Kernel Ridge Regression under Source Condition in Large Dimensions](https://mlsanity.com/paper/2401.01270/) (2024)
- [Multiple Descent in the Multiple Random Feature Model](https://mlsanity.com/paper/2208.09897/) (2022)
- [Benign Overfitting in Two-Layer ReLU Convolutional Neural Networks for XOR Data](https://mlsanity.com/paper/2310.01975/) (2023)
- [Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime](https://mlsanity.com/paper/2310.18280/) (2023)
- [Feature learning as alignment: a structural property of gradient descent in non-linear neural networks](https://mlsanity.com/paper/2402.05271/) (2024)
- [The phase diagram of kernel interpolation in large dimensions](https://mlsanity.com/paper/2404.12597/) (2024)
- [A Theoretical Analysis of the Test Error of Finite-Rank Kernel Ridge Regression](https://mlsanity.com/paper/2310.00987/) (2023)
- [Overparameterized random feature regression with nearly orthogonal data](https://mlsanity.com/paper/2211.06077/) (2022)
- [Overfitting Behaviour of Gaussian Kernel Ridgeless Regression: Varying Bandwidth or Dimensionality](https://mlsanity.com/paper/2409.03891/) (2024)
- [Random features and polynomial rules](https://mlsanity.com/paper/2402.10164/) (2024)
- [Gradient flow in the gaussian covariate model: exact solution of learning curves and multiple descent structures](https://mlsanity.com/paper/2212.06757/) (2022)
- [Interpolation Learning With Minimum Description Length](https://mlsanity.com/paper/2302.07263/) (2023)
- [An Agnostic View on the Cost of Overfitting in (Kernel) Ridge Regression](https://mlsanity.com/paper/2306.13185/) (2023)
- [Optimal Activation Functions for the Random Features Regression Model](https://mlsanity.com/paper/2206.01332/) (2022)

## Abstract (arXiv)

We study the spectrum of inner-product kernel matrices, i.e., n × n matrices with entries h (langle xi ,xj rangle/d) where the ( xi)i ≤ n are i.i.d.~random covariates in ℝd. In the linear high-dimensional regime n asymp d, it was shown that these matrices are well approximated by their linearization, which simplifies into the sum of a rescaled Wishart matrix and identity matrix. In this paper, we generalize this decomposition to the polynomial high-dimensional regime n asymp dℓ,ℓ ∈ mathbbN, for data uniformly distributed on the sphere and hypercube. In this regime, the kernel matrix is well approximated by its degree-ℓ polynomial approximation and can be decomposed into a low-rank spike matrix, identity and a `Gegenbauer matrix' with entries Qℓ (langle xi , xj rangle), where Qℓ is the degree-ℓ Gegenbauer polynomial. We show that the spectrum of the Gegenbauer matrix converges in distribution to a Marchenko-Pastur law. This problem is motivated by the study of the prediction error of kernel ridge regression (KRR) in the polynomial regime n asymp d^kappa, kappa >0. Previous work showed that for kappa not∈ mathbbN, KRR fits exactly a degree-lfloor kappa rfloor polynomial approximation to the target function. In this paper, we use our characterization of the kernel matrix to complete this picture and compute the precise asymptotics of the test error in the limit n/d^kappa → psi with kappa ∈ mathbbN. In this case, the test error can present a double descent behavior, depending on the effective regularization and signal-to-noise ratio at level kappa. Because this double descent can occur each time kappa crosses an integer, this explains the multiple descent phenomenon in the KRR risk curve observed in several previous works.