Manifold regularization based on Nystr{ö}m type subsampling
arXiv:1710.04872 · doi:10.1016/j.acha.2018.12.002
Abstract
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.
References in corpus (9)
- Efficiently Summarising Event Sequences with Rich Interleaving Patterns
- Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
- Multi-view Vector-valued Manifold Regularization for Multi-label Image Classification
- Sharp analysis of low-rank kernel matrix approximations
- Multiple Kernel Sparse Representations for Supervised and Unsupervised Learning
- Less is More: Nyström Computational Regularization
- Convex Learning of Multiple Tasks and their Structure
- Accelerating Approximate Bayesian Computation with Quantile Regression: Application to Cosmological Redshift Distributions
- Learning Multiple Visual Tasks while Discovering their Structure