Robust, randomized preconditioning for kernel ridge regression

This paper investigates preconditioned conjugate gradient techniques for solving kernel ridge regression (KRR) problems with a medium to large number of data points (${10}^4\le N\le {10}^7$), and it describes two methods with the strongest guarantees available. 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\ll N$ selected data centers at a cost of $O((N+k^2)k\log k)$ operations. The proposed methods efficiently solve a range of KRR problems, making them well-suited for practical applications.