  In this paper, we study the Nystr{\"o}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{\"o}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{\"o}m approximants. Finally, we demonstrate the performance of
multi-penalty regularization based on Nystr{\"o}m type subsampling on
Caltech-101 data set for multi-class image classification and NSL-KDD benchmark
data set for intrusion detection problem.
