Generalization error of spectral algorithms
Maksim Velikanov Maxim Panov Dmitry Yarotsky
The asymptotically precise estimation of the generalization of kernel methods
has recently received attention due to the parallels between neural networks
and their associated kernels. However, prior works derive such estimates for
training by kernel ridge regression (KRR), whereas neural networks are
typically trained with gradient descent (GD). In the present work, we consider
the training of kernels with a family of $\textit{spectral algorithms}$
specified by profile $h(\lambda)$, and including KRR and GD as special cases.
Then, we derive the generalization error as a functional of learning profile
$h(\lambda)$ for two data models: high-dimensional Gaussian and low-dimensional
translation-invariant model. Under power-law assumptions on the spectrum of the
kernel and target, we use our framework to (i) give full loss asymptotics for
both noisy and noiseless observations (ii) show that the loss localizes on
certain spectral scales, giving a new perspective on the KRR saturation
phenomenon (iii) conjecture, and demonstrate for the considered data models,
the universality of the loss w.r.t. non-spectral details of the problem, but
only in case of noisy observation.