Simple and Almost Assumption-Free Out-of-Sample Bound for Random Feature Mapping
arXiv:1909.11207
Abstract
Random feature mapping (RFM) is a popular method for speeding up kernel methods at the cost of losing a little accuracy. We study kernel ridge regression with random feature mapping (RFM-KRR) and establish novel out-of-sample error upper and lower bounds. While out-of-sample bounds for RFM-KRR have been established by prior work, this paper's theories are highly interesting for two reasons. On the one hand, our theories are based on weak and valid assumptions. In contrast, the existing theories are based on various uncheckable assumptions, which makes it unclear whether their bounds are the nature of RFM-KRR or simply the consequence of strong assumptions. On the other hand, our analysis is completely based on elementary linear algebra and thereby easy to read and verify. Finally, our experiments lend empirical supports to the theories.
References in corpus (10)
- Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates
- Generalization Properties of Learning with Random Features
- Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
- Randomized Nonlinear Component Analysis
- Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees
- Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
- Optimal Rates for Random Fourier Features
- Kernel Approximation Methods for Speech Recognition
- Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data
- Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off