Robust and Efficient Kernel Hyperparameter Paths with Guarantees
Joachim Giesen, Soeren Laue, Patrick Wieschollek · 2014
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.