# Relative concentration bounds for the spectrum of kernel matrices

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2018.

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

- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimension](https://mlsanity.com/paper/2305.14077/) (2023)
- [Learning curves for Gaussian process regression with power-law priors and targets](https://mlsanity.com/paper/2110.12231/) (2021)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)

## Abstract (arXiv)

In this paper we study the concentration properties for the eigenvalues of kernel matrices, which are central objects in a wide range of kernel methods and, more recently, in network analysis. We present a set of concentration inequalities tailored for each individual eigenvalue of the kernel matrix with respect to its known asymptotic limit. The inequalities presented here are of relative type, meaning that they scale with the eigenvalue in consideration, which results in convergence rates that vary across the spectrum. The rates we obtain here are faster than the typical O(frac1√ n) and are often exponential, depending on regularity assumptions of Sobolev type. One key feature of our results is that they apply to non positive kernels, which is fundamental in the context of network analysis. We show how our results are well suited for the study of dot product kernels, which are related to random geometric graphs on the sphere, via the graphon formalism. We illustrate our results by applying them to a variety of dot product kernels on the sphere and to the one dimensional Gaussian kernel.