Randomized sketches for kernels: Fast and optimal non-parametric regression

Abstract

Kernel ridge regression (KRR) is a standard method for performing non-parametric regression over reproducing kernel Hilbert spaces. Given $n$ samples, the time and space complexity of computing the KRR estimate scale as $\mathcal{O}(n^3)$ and $\mathcal{O}(n^2)$ respectively, and so is prohibitive in many cases. We propose approximations of KRR based on $m$-dimensional randomized sketches of the kernel matrix, and study how small the projection dimension $m$ can be chosen while still preserving minimax optimality of the approximate KRR estimate. For various classes of randomized sketches, including those based on Gaussian and randomized Hadamard matrices, we prove that it suffices to choose the sketch dimension $m$ proportional to the statistical dimension (modulo logarithmic factors). Thus, we obtain fast and minimax optimal approximations to the KRR estimate for non-parametric regression.

27 pages, 3 figures

References in corpus (3)

• 2004 IMS Medallion Lecture: Local Rademacher complexities and oracle inequalities in risk minimization
• Fast Randomized Kernel Methods With Statistical Guarantees
• Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares

Cited by in corpus (10)

• Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
• Optimal approximate matrix product in terms of stable rank
• Sketched Subspace Clustering
• OverSketch: Approximate Matrix Multiplication for the Cloud
• Learning Theory for Distribution Regression
• Kernel Ridge Regression via Partitioning
• Sketching Meets Random Projection in the Dual: A Provable Recovery Algorithm for Big and High-dimensional Data
• Sketching the order of events
• Optimal Rates of Sketched-regularized Algorithms for Least-Squares Regression over Hilbert Spaces
• Statistically and Computationally Efficient Variance Estimator for Kernel Ridge Regression