  This paper studies the statistical complexity of kernel hyperparameter tuning
in the setting of active regression under adversarial noise. We consider the
problem of finding the best interpolant from a class of kernels with unknown
hyperparameters, assuming only that the noise is square-integrable. We provide
finite-sample guarantees for the problem, characterizing how increasing the
complexity of the kernel class increases the complexity of learning kernel
hyperparameters. For common kernel classes (e.g. squared-exponential kernels
with unknown lengthscale), our results show that hyperparameter optimization
increases sample complexity by just a logarithmic factor, in comparison to the
setting where optimal parameters are known in advance. Our result is based on a
subsampling guarantee for linear regression under multiple design matrices,
combined with an {\epsilon}-net argument for discretizing kernel
parameterizations.
