  It is by now well-established that modern over-parameterized models seem to
elude the bias-variance tradeoff and generalize well despite overfitting noise.
Many recent works attempt to analyze this phenomenon in the relatively
tractable setting of kernel regression. However, as we argue in detail, most
past works on this topic either make unrealistic assumptions, or focus on a
narrow problem setup. This work aims to provide a unified theory to upper bound
the excess risk of kernel regression for nearly all common and realistic
settings. Specifically, we provide rigorous bounds that hold for common kernels
and for any amount of regularization, noise, any input dimension, and any
number of samples. Furthermore, we provide relative perturbation bounds for the
eigenvalues of kernel matrices, which may be of independent interest. These
reveal a self-regularization phenomenon, whereby a heavy tail in the
eigendecomposition of the kernel provides it with an implicit form of
regularization, enabling good generalization. When applied to common kernels,
our results imply benign overfitting in high input dimensions, nearly tempered
overfitting in fixed dimensions, and explicit convergence rates for regularized
regression. As a by-product, we obtain time-dependent bounds for neural
networks trained in the kernel regime.
