Geometric Interpretation of Running Nyström-Based Kernel Machines and Error Analysis

As an implementation of the Nystrom method, Nystrom computational regularization (NCR) imposed on kernel classification and kernel ridge regression has proven capable of achieving optimal bounds in the large-scale statistical learning setting, while enjoying much better time complexity. In this study, we propose a Nystrom subspace learning (NSL) framework to reveal that all you need for employing the Nystrom method, including NCR, upon any kernel SVM is to use the efficient off-the-shelf linear SVM solvers as a black box. Based on our analysis, the bounds developed for the Nystrom method are linked to NSL, and the analytical difference between two distinct implementations of the Nystrom method is clearly presented. Besides, NSL also leads to sharper theoretical results for the clustered Nystrom method. Finally, both regression and classification tasks are performed to compare two implementations of the Nystrom method.