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

Yun Yang, Mert Pilanci, Martin J. Wainwright

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…