mlsanityData to 14 Oct 2026

A general technique for approximating high-dimensional empirical kernel matrices

arXiv 2511.03892 ↗First posted 5 Nov 2025stat.ML cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We present simple, user-friendly bounds for the expected operator norm of a random kernel matrix under general conditions on the kernel function k(·,·). Our approach uses decoupling results for U-statistics and the non-commutative Khintchine inequality to obtain upper and lower bounds depending only on scalar statistics of the kernel function and a ``correlation kernel'' matrix corresponding to k(·,·). We then apply our method to provide new, tighter approximations for inner-product kernel matrices on general high-dimensional data, where the sample size and data dimension are polynomially related. Our method obtains simplified proofs of existing results that rely on the moment method and combinatorial arguments while also providing novel approximation results for the case of anisotropic Gaussian data. Finally, using similar techniques to our approximation result, we show a tighter lower bound on the bias of kernel regression with anisotropic Gaussian data.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 26 of its 56 references that are in the map. First posted on arXiv 5 Nov 2025.

Builds on

26 of 56 references.

References · 26

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2018On Lazy Training in Differentiable Programmingcited by 675
  3. 2021Deep learning: a statistical viewpointcited by 240
  4. 2018Just Interpolate: Kernel "Ridgeless" Regression Can Generalizecited by 190
  5. 2018To understand deep learning we need to understand kernel learningcited by 187
  6. 2019Linearized two-layers neural networks in high dimensioncited by 155
  7. 2020Benign overfitting in ridge regressioncited by 153
  8. 2020When Do Neural Networks Outperform Kernel Methods?cited by 150
  9. 2021Generalization error of random features and kernel methods: hypercontractivity and kernel matrix concentrationcited by 110
  10. 2020Global Convergence of Deep Networks with One Wide Layer Followed by Pyramidal Topologycited by 66
  11. 2022Dimension free ridge regressioncited by 51
  12. 2022Spectrum of inner-product kernel matrices in the polynomial regime and multiple descent phenomenon in kernel ridge regressioncited by 45
14 more
  1. 2018Approximation beats concentration? An approximation view on inference with smooth radial kernelscited by 33
  2. 2021How rotational invariance of common kernels prevents generalization in high dimensionscited by 32
  3. 2015Learning Mixtures of Gaussians in High Dimensionscited by 29
  4. 2024A non-asymptotic theory of Kernel Ridge Regression: deterministic equivalents, test error, and GCV estimatorcited by 28
  5. 2022An Equivalence Principle for the Spectrum of Random Inner-Product Kernel Matrices with Polynomial Scalingscited by 27
  6. 2023Mind the spikes: Benign overfitting of kernels and neural networks in fixed dimensioncited by 26
  7. 2023Six Lectures on Linearized Neural Networkscited by 20
  8. 2022Sharp Asymptotics of Kernel Ridge Regression Beyond the Linear Regimecited by 19
  9. 2021Harmless interpolation in regression and classification with structured featurescited by 14
  10. 2024Universality of Kernel Random Matrices and Kernel Regression in the Quadratic Regimecited by 12
  11. 2023Universality for the global spectrum of random inner-product kernel matrices in the polynomial regimecited by 10
  12. 2022Overparameterized random feature regression with nearly orthogonal datacited by 7
  13. 2025Learning single-index models via harmonic decompositioncited by 7
  14. 2023New Equivalences Between Interpolation and SVMs: Kernels and Structured Featurescited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 4.

4 papers.

  1. 2026Power-Law Spectrum of the Random Feature Modelcited by 4
  2. 2026Average Gradient Outer Product in kernel regression provably recovers the central subspace for multi-index modelscited by 1
  3. 2026Spectral Concentration and Recovery in Sparse High-Dimensional Random Geometric Graphscited by 1
  4. 2026Recovery of latent inner products from an anisotropic Gaussian random geometric graphcited by 0