Recursive Sampling for the Nyström Method

Abstract

We give the first algorithm for kernel Nyström approximation that runs in *linear time in the number of training points* and is provably accurate for all kernel matrices, without dependence on regularity or incoherence conditions. The algorithm projects the kernel onto a set of $s$ landmark points sampled by their *ridge leverage scores*, requiring just $O(ns)$ kernel evaluations and $O(n{s}^2)$ additional runtime. While leverage score sampling has long been known to give strong theoretical guarantees for Nyström approximation, by employing a fast recursive sampling scheme, our algorithm is the first to make the approach scalable. Empirically we show that it finds more accurate, lower rank kernel approximations in less time than popular techniques such as uniformly sampled Nyström approximation and the random Fourier features method.

To appear, NIPS 2017

References in corpus (5)

• Fast DPP Sampling for Nyström with Application to Kernel Methods
• Large Scale Kernel Learning using Block Coordinate Descent
• Frequent Directions : Simple and Deterministic Matrix Sketching
• On Column Selection in Approximate Kernel Canonical Correlation Analysis
• Relative Error Embeddings for the Gaussian Kernel Distance

Cited by in corpus (26)

• Improved Fixed-Rank Nyström Approximation via QR Decomposition: Practical and Theoretical Aspects
• On Coresets for Logistic Regression
• Massively scalable Sinkhorn distances via the Nyström method
• On Fast Leverage Score Sampling and Optimal Learning
• Improved guarantees and a multiple-descent curve for Column Subset Selection and the Nyström method
• Nonparametric Testing under Random Projection
• Eigenvalue Decay Implies Polynomial-Time Learnability for Neural Networks
• Fourier Sparse Leverage Scores and Approximate Kernel Learning
• Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling
• Linear quadratic control of nonlinear systems with Koopman operator learning and the Nyström method
• Accumulation of Sub-Sampling Matrices with Applications to Statistical Computation
• Almost Optimal Tensor Sketch
• Hashing-Based-Estimators for Kernel Density in High Dimensions
• Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning
• Scaling Neural Tangent Kernels via Sketching and Random Features
• QuicK-means: Acceleration of K-means by learning a fast transform
• Coresets for Kernel Clustering
• Optimal Sketching Bounds for Exp-concave Stochastic Minimization
• Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
• Learning with Neural Tangent Kernels in Near Input Sparsity Time
• Faster Kernel Matrix Algebra via Density Estimation
• Deep Kernel Learning for Clustering
• Isolation Kernel: The X Factor in Efficient and Effective Large Scale Online Kernel Learning
• Improving classification performance by feature space transformations and model selection
• Oversampling Divide-and-conquer for Response-skewed Kernel Ridge Regression
• Statistically and Computationally Efficient Variance Estimator for Kernel Ridge Regression