Maximum effective dimension and information gain

Abstract

We establish general upper bounds on the maximum effective dimension and information gain of kernel Gram matrices over arbitrary designs in terms of approximation properties of the kernel or, equivalently, of the corresponding reproducing kernel Hilbert space. We show that across three regularity regimes, covering as special cases the Matérn and squared exponential kernels, these bounds cannot be improved beyond constant factors.