Randomized sketches for kernels: Fast and optimal non-parametric
  regression
  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.
