Robust, randomized preconditioning for kernel ridge regression

Code

• github.com/eepperly/fast-efficient-krr-preconditioning
  OfficialIn papernone★ 7
• github.com/eepperly/robust-randomized-preconditioning-for-kernel-ridge-regression
  none★ 7

Abstract

This paper investigates two randomized preconditioning techniques for solving kernel ridge regression (KRR) problems with a medium to large number of data points (10^4 N 10^7), and it introduces two new methods with state-of-the-art performance. The first method, RPCholesky preconditioning, accurately solves the full-data KRR problem in O(N^2) arithmetic operations, assuming sufficiently rapid polynomial decay of the kernel matrix eigenvalues. The second method, KRILL preconditioning, offers an accurate solution to a restricted version of the KRR problem involving k N selected data centers at a cost of O((N + k^2) k k) operations. The proposed methods solve a broad range of KRR problems, making them ideal for practical applications.

Tasks

Reproductions