Abstract
Kernel methods implicitly map data points from the input space to some feature space where even relatively simple algorithms such as linear methods can deliver very impressive performance. Of crucial importance to the success of these methods is the choice of the kernel and its hyperparameters. This paper introduces an efficient "solution path" algorithm for Kernelized LASSO (kLASSO) that allows researchers to trace the optimal model solution as a kernel hyperparameter changes, bypassing the need for exhaustive grid searches.
Introduction
Kernelized LASSO (kLASSO) is a powerful tool for handling non-linear relationships by mapping data into high-dimensional feature spaces. However, its performance is highly sensitive to two primary factors: the regularization parameter ($\lambda$), which controls model sparsity, and the kernel hyperparameter (e.g., the width $\sigma$ or $\gamma$ of an RBF kernel), which controls the shape of the mapping. While algorithms like LARS efficiently trace the regularization path for $\lambda$, tuning kernel hyperparameters has traditionally relied on computationally expensive grid searches. This paper addresses this gap by proposing the Kernel Path Algorithm, which identifies the exact points where the model's structure changes as a kernel hyperparameter varies.
Methods
The Kernel Path Algorithm leverages Karush-Kuhn-Tucker (KKT) optimality conditions to derive the relationship between the kernel hyperparameter and the model coefficients ($\beta$). Unlike the piecewise linear regularization path, the kernel path is non-linear because the hyperparameter is embedded deep within the kernel matrix entries.
The algorithm tracks an "active set" of data points that contribute to the model. It monitors for "events"—breakpoints where a data point either joins or leaves this active set. By deriving an updating formula (Equation 21), the authors allow for the exact calculation of the optimal solution between these breakpoints. Efficiency is maintained by only updating entries related to active and marginal points, reducing the complexity to roughly $O(np + m^3)$ per iteration, where $m$ is the size of the active set.
Results and Visualization
The algorithm was evaluated using a synthetic benchmark based on the Sinc function ($y = \sin(\pi x) / (\pi x)$) with added Gaussian noise. This setup allows for clear observation of model behavior across different parameter regimes.
The results demonstrate that the algorithm can exactly trace the solution path, providing a continuous view of model evolution as shown in the coefficient path above. This enables precise model selection by plotting metrics like Mean Squared Error (MSE) as continuous curves, facilitating the identification of the optimal hyperparameter value that minimizes error on validation data.
Key Insights and Discussion
A significant insight of this work is that solution paths do not need to be piecewise linear to be efficiently traceable. By solving systems of linear equations based on the active set, the exact "direction" of the solution in non-linear space can be determined.
The "Proper Fitting" zone (F) can be navigated more effectively using this path-following approach compared to discrete grid searches. However, limitations remain regarding scalability to massive datasets where the active set ($m$) might become very large, leading to $O(m^3)$ bottlenecks. Furthermore, while the algorithm traces one hyperparameter at a time, future work could explore simultaneous multi-parameter path tracing to further enhance model optimization in high-dimensional real-world applications.
Conclusion
The Kernel Path Algorithm offers a significant advancement in hyperparameter optimization for kernel methods. By providing an exact and efficient way to trace model solutions, it reduces the computational burden of model selection and improves the precision of finding optimal kernel configurations.
Summary updated