Randomized sketches for kernels: Fast and optimal non-parametric regression
By Yun Yang, Mert Pilanci, Martin J. Wainwright. 2015
188 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Mechanics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Yuchen Zhang
- Martin J. Wainwright
- John C. Duchi
- Michael I. Jordan
- Lorenzo Rosasco
- Alessandro Rudi
- Francis R. Bach
- Lin F. Yang
In Computational Mechanics
- Yuchen Zhang
- John C. Duchi
- Alessandro Rudi
- Martin J. Wainwright
- Luigi Carratino
- Lorenzo Rosasco
- Lin F. Yang
- Mengdi Wang
Citations in the corpus
- Divide and conquer kernel ridge regression: a distributed algorithm with minimax optimal rates (2013, background): “Then the mean-squared error is bounded as The upper bound (21) is minimax optimal; see, for example, Theorem 1 and Example 2 of the recent paper by Yang et al. (2015).”
- Frequentist coverage and sup-norm convergence rate in Gaussian process regression (2017, unknown): “Notice that a typical analysis of the KRR estimator using basic inequality (such as [51]) requires a lower bound on the regularization parameter λ , while our analysis is free of such an assumption.”
- Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “08), in dealing with KΨ matrices), still polynomial in T. We can apply the random features or sketching techniques for kernel to additionally accelerate the computation (e.g. (Rahimi and Recht, 2008; Yang et al., 2017)). 5 Summary Thispaper provided the algorithm MatrixRL for episodic reinforcement ”
- Learning with SGD and Random Features (2018, methodology): “This idea can be used within a penalized empirical risk minimization framework [26, 27, 28] but also considering gradient [29, 30] and stochastic gradient [31] techniques.”