  Kernel methods provide a principled approach to nonparametric learning. While
their basic implementations scale poorly to large problems, recent advances
showed that approximate solvers can efficiently handle massive datasets. A
shortcoming of these solutions is that hyperparameter tuning is not taken care
of, and left for the user to perform. Hyperparameters are crucial in practice
and the lack of automated tuning greatly hinders efficiency and usability. In
this paper, we work to fill in this gap focusing on kernel ridge regression
based on the Nystr\"om approximation. After reviewing and contrasting a number
of hyperparameter tuning strategies, we propose a complexity regularization
criterion based on a data dependent penalty, and discuss its efficient
optimization. Then, we proceed to a careful and extensive empirical evaluation
highlighting strengths and weaknesses of the different tuning strategies. Our
analysis shows the benefit of the proposed approach, that we hence incorporate
in a library for large scale kernel methods to derive adaptively tuned
solutions.

Machine Learning;Machine Learning