Non-asymptotic spectral bounds on the $varepsilon$-entropy of kernel classes

View a PDF of the paper titled Non-asymptotic spectral bounds on the $varepsilon$-entropy of kernel classes, by Rustem Takhanov

View PDF
HTML (experimental)

Abstract:Let $K: boldsymbol{Omega}times boldsymbol{Omega}$ be a continuous Mercer kernel defined on a compact subset of ${mathbb R}^n$ and $mathcal{H}_K$ be the reproducing kernel Hilbert space (RKHS) associated with $K$. Given a finite measure $nu$ on $boldsymbol{Omega}$, we investigate upper and lower bounds on the $varepsilon$-entropy of the unit ball of $mathcal{H}_K$ in the space $L_p(nu)$. This topic is an important direction in the modern statistical theory of kernel-based methods.

We prove sharp upper and lower bounds for $pin [1,+infty]$. For $pin [1,2]$, the upper bounds are determined solely by the eigenvalue behaviour of the corresponding integral operator $phito int_{boldsymbol{Omega}} K(cdot,{mathbf y})phi({mathbf y})dnu({mathbf y})$. In constrast, for $p>2$, the bounds additionally depend on the convergence rate of the truncated Mercer series to the kernel $K$ in the $L_p(nu)$-norm.

We discuss a number of consequences of our bounds and show that they are substantially tighter than previous bounds for general kernels. Furthermore, for specific cases, such as zonal kernels and the Gaussian kernel on a box, our bounds are asymptotically tight as $varepsilonto +0$.