Yang, Yun; Pilanci, Mert; Wainwright, Martin J. Randomized sketches for kernels: fast and optimal nonparametric regression. (English) Zbl 1371.62039 Ann. Stat. 45, No. 3, 991-1023 (2017). Summary: Kernel ridge regression (KRR) is a standard method for performing nonparametric 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 nonparametric regression. In doing so, we prove a novel lower bound on the minimax risk of kernel regression in terms of the localized Rademacher complexity. Cited in 28 Documents MSC: 62G08 Nonparametric regression and quantile regression 68W20 Randomized algorithms Keywords:nonparametric regression; random projection; kernel method; dimensionality reduction; convex optimization; kernel ridge regression (KRR) PDFBibTeX XMLCite \textit{Y. Yang} et al., Ann. Stat. 45, No. 3, 991--1023 (2017; Zbl 1371.62039) Full Text: DOI arXiv Euclid