The $L^\infty$ Learnability of Reproducing Kernel Hilbert Spaces
Hongrui Chen Jihao Long Lei Wu
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
$\lambda_k\sim k^{-1-\beta}$ with $\beta>0$. We prove that if $\beta$ 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 $\beta=1/\mathrm{poly}(d)$, then
the $L^\infty$ learning requires exponentially many samples.