# Approximation beats concentration? An approximation view on inference with smooth radial kernels

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jan 2018.

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

- [Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks](https://mlsanity.com/paper/2006.13198/) (2020)
- [Rigorous data-driven computation of spectral properties of Koopman operators for dynamical systems](https://mlsanity.com/paper/2111.14889/) (2021)
- [Neural Contextual Bandits without Regret](https://mlsanity.com/paper/2107.03144/) (2021)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Generalization in Kernel Regression Under Realistic Assumptions](https://mlsanity.com/paper/2312.15995/) (2023)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Fast Statistical Leverage Score Approximation in Kernel Ridge Regression](https://mlsanity.com/paper/2103.05238/) (2021)
- [Robust Uncertainty Bounds in Reproducing Kernel Hilbert Spaces: A Convex Optimization Approach](https://mlsanity.com/paper/2104.09582/) (2021)
- [Harmless interpolation in regression and classification with structured features](https://mlsanity.com/paper/2111.05198/) (2021)
- [A general approximation lower bound in Lp norm, with applications to feed-forward neural networks](https://mlsanity.com/paper/2206.04360/) (2022)
- [Tighter Confidence Bounds for Sequential Kernel Regression](https://mlsanity.com/paper/2403.12732/) (2024)
- [Koopman-Equivariant Gaussian Processes](https://mlsanity.com/paper/2502.06645/) (2025)
- [Adversarially Robust Kernel Smoothing](https://mlsanity.com/paper/2102.08474/) (2021)
- [Generalization Performance of Empirical Risk Minimization on Over-parameterized Deep ReLU Nets](https://mlsanity.com/paper/2111.14039/) (2021)
- [A general technique for approximating high-dimensional empirical kernel matrices](https://mlsanity.com/paper/2511.03892/) (2025)
- [Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embedding](https://mlsanity.com/paper/2304.03907/) (2023)
- [An Improved Uniform Convergence Bound with Fat-Shattering Dimension](https://mlsanity.com/paper/2307.06644/) (2023)
- [Regularized KL-Divergence for Well-Defined Function-Space Variational Inference in Bayesian neural networks](https://mlsanity.com/paper/2406.04317/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Dynamic Pricing and Demand Learning on a Large Network of Products: A PAC-Bayesian Approach](https://mlsanity.com/paper/2111.00790/) (2021)
- [Provably Reliable Large-Scale Sampling from Gaussian Processes](https://mlsanity.com/paper/2211.08036/) (2022)
- [Symphony in the Latent Space: Provably Integrating High-dimensional Techniques with Non-linear Machine Learning Models](https://mlsanity.com/paper/2212.00852/) (2022)
- [A Bound on the Maximal Marginal Degrees of Freedom](https://mlsanity.com/paper/2402.12885/) (2024)
- [Bayesian Optimization over Bounded Domains with the Beta Product Kernel](https://mlsanity.com/paper/2506.16316/) (2025)
- [Shallow Representation is Deep: Learning Uncertainty-aware and Worst-case Random Feature Dynamics](https://mlsanity.com/paper/2106.13066/) (2021)
- [Interpolation with the polynomial kernels](https://mlsanity.com/paper/2212.07658/) (2022)
- [Spatial Process Approximations: Assessing Their Necessity](https://mlsanity.com/paper/2311.03201/) (2023)
- [Approximating invariant functions with the sorting trick is theoretically justified](https://mlsanity.com/paper/2403.01671/) (2024)
- [Entrywise error bounds for low-rank approximations of kernel matrices](https://mlsanity.com/paper/2405.14494/) (2024)
- [Fast Second-Order Online Kernel Learning through Incremental Matrix Sketching and Decomposition](https://mlsanity.com/paper/2410.11188/) (2024)

## Abstract (arXiv)

Positive definite kernels and their associated Reproducing Kernel Hilbert Spaces provide a mathematically compelling and practically competitive framework for learning from data. In this paper we take the approximation theory point of view to explore various aspects of smooth kernels related to their inferential properties. We analyze eigenvalue decay of kernels operators and matrices, properties of eigenfunctions/eigenvectors and "Fourier" coefficients of functions in the kernel space restricted to a discrete set of data points. We also investigate the fitting capacity of kernels, giving explicit bounds on the fat shattering dimension of the balls in Reproducing Kernel Hilbert spaces. Interestingly, the same properties that make kernels very effective approximators for functions in their "native" kernel space, also limit their capacity to represent arbitrary functions. We discuss various implications, including those for gradient descent type methods. It is important to note that most of our bounds are measure independent. Moreover, at least in moderate dimension, the bounds for eigenvalues are much tighter than the bounds which can be obtained from the usual matrix concentration results. For example, we see that the eigenvalues of kernel matrices show nearly exponential decay with constants depending only on the kernel and the domain. We call this "approximation beats concentration" phenomenon as even when the data are sampled from a probability distribution, some of their aspects are better understood in terms of approximation theory.