Manifold regularization based on Nystr{ö}m type subsampling
This work addresses scalability issues in kernel methods for big data applications, representing an incremental improvement over existing manifold regularization techniques.
The paper tackles the computational complexity of large-scale kernel methods by proposing a multi-penalty regularization scheme based on Nyström type subsampling, achieving optimal minimax convergence rates and demonstrating performance on image classification and intrusion detection datasets.
In this paper, we study the Nystr{ö}m type subsampling for large scale kernel methods to reduce the computational complexities of big data. We discuss the multi-penalty regularization scheme based on Nystr{ö}m type subsampling which is motivated from well-studied manifold regularization schemes. We develop a theoretical analysis of multi-penalty least-square regularization scheme under the general source condition in vector-valued function setting, therefore the results can also be applied to multi-task learning problems. We achieve the optimal minimax convergence rates of multi-penalty regularization using the concept of effective dimension for the appropriate subsampling size. We discuss an aggregation approach based on linear function strategy to combine various Nystr{ö}m approximants. Finally, we demonstrate the performance of multi-penalty regularization based on Nystr{ö}m type subsampling on Caltech-101 data set for multi-class image classification and NSL-KDD benchmark data set for intrusion detection problem.