Less is More: Nyström Computational Regularization

Abstract

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.

updated version of NIPS 2015 (oral)

References in corpus (2)

• Fast Randomized Kernel Methods With Statistical Guarantees
• On the Sample Complexity of Subspace Learning

Cited by in corpus (19)

• Quantum machine learning: a classical perspective
• Recursive Sampling for the Nyström Method
• Optimal Rates for Spectral Algorithms with Least-Squares Regression over Hilbert Spaces
• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Learning Theory for Distribution Regression
• Sobolev Norm Learning Rates for Regularized Least-Squares Algorithm
• Recursive nearest agglomeration (ReNA): fast clustering for approximation of structured signals
• Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off
• Kernel Ridge Regression via Partitioning
• Learning the kernel matrix via predictive low-rank approximations
• Fast Polynomial Kernel Classification for Massive Data
• Lepskii Principle in Supervised Learning
• Efficient and principled score estimation with Nyström kernel exponential families
• Improved Classification Rates for Localized SVMs
• Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling
• Manifold regularization based on Nystr{ö}m type subsampling
• Surrogate-Based Simulation Optimization
• Statistical Optimality and Computational Efficiency of Nyström Kernel PCA
• Doubly stochastic large scale kernel learning with the empirical kernel map