Randomized sketches for kernels: Fast and optimal non-parametric regression
Randomized sketches for kernels: Fast and optimal non-parametric regression
复制标题
DOI：
10.1214/16-aos1472
复制
发表时间：
2015-01
期刊：
影响因子：
--
通讯作者：
Yun Yang;Mert Pilanci;M. Wainwright
中科院分区：
文献类型：
--
作者：
Yun Yang;Mert Pilanci;M. Wainwright
核脊回归（KRR）是在再现核希尔伯特空间上进行非参数回归的一种标准方法。给定$n$样本，计算KRR估计尺度的时间和空间复杂度分别为$\mathcal{O}(n^3)$和$\mathcal{O}(n^2)$，因此在许多情况下是令人望而却步的。我们提出了基于核矩阵的$m$维随机草图的KRR近似，并研究了在保持KRR近似估计的极大极小最优性的同时，可以选择多小的投影维$m$。对于各种类型的随机草图，包括基于高斯矩阵和随机Hadamard矩阵的草图，我们证明了选择与统计维数（模对数因子）成比例的草图维数$m$就足够了。因此，我们获得了非参数回归KRR估计的快速和极大极小最优逼近。
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.