Solving Kernel Ridge Regression with Gradient Descent for a Non-Constant
  Kernel
Oskar Allerbo
Kernel ridge regression, KRR, is a generalization of linear ridge regression
that is non-linear in the data, but linear in the parameters. The solution can
be obtained either as a closed-form solution, which includes a matrix
inversion, or iteratively through gradient descent. Using the iterative
approach opens up for changing the kernel during training, something that is
investigated in this paper. We theoretically address the effects this has on
model complexity and generalization. Based on our findings, we propose an
update scheme for the bandwidth of translational-invariant kernels, where we
let the bandwidth decrease to zero during training, thus circumventing the need
for hyper-parameter selection. We demonstrate on real and synthetic data how
decreasing the bandwidth during training outperforms using a constant
bandwidth, selected by cross-validation and marginal likelihood maximization.
We also show theoretically and empirically that using a decreasing bandwidth,
we are able to achieve both zero training error in combination with good
generalization, and a double descent behavior, phenomena that do not occur for
KRR with constant bandwidth but are known to appear for neural networks.