On Fast Leverage Score Sampling and Optimal Learning
This work addresses a computational bottleneck in machine learning for large-scale kernel methods, offering incremental improvements in algorithm performance.
The paper tackles the challenge of leverage score sampling for positive definite kernel matrices by introducing a novel algorithm and applying it to kernel ridge regression, resulting in improved efficiency and accuracy compared to existing methods.
Leverage score sampling provides an appealing way to perform approximate computations for large matrices. Indeed, it allows to derive faithful approximations with a complexity adapted to the problem at hand. Yet, performing leverage scores sampling is a challenge in its own right requiring further approximations. In this paper, we study the problem of leverage score sampling for positive definite matrices defined by a kernel. Our contribution is twofold. First we provide a novel algorithm for leverage score sampling and second, we exploit the proposed method in statistical learning by deriving a novel solver for kernel ridge regression. Our main technical contribution is showing that the proposed algorithms are currently the most efficient and accurate for these problems.