Less is More: Nyström Computational Regularization
This provides a computationally efficient solution for large-scale kernel learning problems, though it appears incremental as it builds on existing Nyström methods.
The paper tackles the computational challenge of large-scale kernel methods by proving that Nyström subsampling can achieve optimal learning bounds when the subsampling level is properly chosen, and shows experimentally that this approach achieves state-of-the-art performance on benchmark datasets.
We study Nyström type subsampling approaches to large scale kernel methods, and prove learning bounds in the statistical learning setting, where random sampling and high probability estimates are considered. In particular, we prove that these approaches can achieve optimal learning bounds, provided the subsampling level is suitably chosen. These results suggest a simple incremental variant of Nyström Kernel Regularized Least Squares, where the subsampling level implements a form of computational regularization, in the sense that it controls at the same time regularization and computations. Extensive experimental analysis shows that the considered approach achieves state of the art performances on benchmark large scale datasets.