Robust and Efficient Kernel Hyperparameter Paths with Guarantees

Algorithmically, many machine learning tasks boil down to solving parameterized optimization problems. The choice of the parameter values in these problems can have a significant influ-ence on the statistical performance of the cor-responding methods. Thus, algorithmic support for choosing good parameter values has received quite some attention recently, especially algo-rithms for computing the whole solution path of a parameterized optimization problem. These al-gorithms can be used, for instance, to track the solution of a regularized learning problem along the regularization parameter path, or for tracking the solution of kernelized problems along a ker-nel hyperparameter path. Since exact path fol-lowing algorithms can be numerically unstable, robust and efficient approximate path tracking al-gorithms have gained in popularity for regular-ized learning problems. By now algorithms with optimal path complexity in terms of a guaranteed approximation error are known for many regular-ized learning problems. That is not the case for kernel hyperparameter path tracking algorithms, where the exact path tracking algorithms can also suffer from numerical problems. Here we ad-dress this problem by devising a robust and effi-cient path tracking algorithm that can also handle kernel hyperparameter paths. The algorithm has asymptotically optimal complexity. We use this algorithm to compute approximate kernel hyper-paramter solution paths for support vector ma-chines and robust kernel regression. Experimen-tal results for these problems applied to various data sets confirm the theoretical complexity anal-ysis.