The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces
This work addresses the theoretical understanding of kernel methods for safety-critical applications, providing foundational insights into sample complexity bounds.
The paper tackles the problem of learning functions in reproducing kernel Hilbert spaces under the L∞ norm, establishing that for dot-product kernels on the sphere, polynomial sample complexity is achievable when the kernel spectrum decay parameter β is independent of input dimension, but exponential samples are required if β scales inversely with dimension.
In this work, we analyze the learnability of reproducing kernel Hilbert spaces (RKHS) under the $L^\infty$ norm, which is critical for understanding the performance of kernel methods and random feature models in safety- and security-critical applications. Specifically, we relate the $L^\infty$ learnability of a RKHS to the spectrum decay of the associate kernel and both lower bounds and upper bounds of the sample complexity are established. In particular, for dot-product kernels on the sphere, we identify conditions when the $L^\infty$ learning can be achieved with polynomial samples. Let $d$ denote the input dimension and assume the kernel spectrum roughly decays as $λ_k\sim k^{-1-β}$ with $β>0$. We prove that if $β$ is independent of the input dimension $d$, then functions in the RKHS can be learned efficiently under the $L^\infty$ norm, i.e., the sample complexity depends polynomially on $d$. In contrast, if $β=1/\mathrm{poly}(d)$, then the $L^\infty$ learning requires exponentially many samples.