UC San Diego

We investigate preconditioned conjugate gradient methods for kernel ridge regression (KRR) problems with a moderate to large number of data points (104≤N≤107$$10^4 \le N \le 10^7$$). We develop and analyze two randomized preconditioners with complementary guarantees. For full-data KRR, RPCholesky preconditioning requires O(N2)$$\mathcal {O}(N^2)$$ arithmetic operations for fixed accuracy under sufficiently rapid eigenvalue decay of the kernel matrix. For restricted KRR with k≪N$$k\ll N$$ centers, KRILL preconditioning requires O((N+k2)klogk)$$\mathcal {O}((N+k^2)k\log k)$$ operations with no eigenvalue-decay assumption. Experiments on benchmark and scientific data sets demonstrate the robustness of both methods relative to existing preconditioners.