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

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