Robust, randomized preconditioning for kernel ridge regression

MaRDI QIDQ6434197zbMATH OpenFDO

Authors Mateo Díaz, Ethan N. Epperly, Joel A. Tropp, Robert J. Webber

Publication date 24 April 2023

Has companion code repository https://github.com/eepperly/fast-efficient-krr-preconditioning

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Randomized algorithms (68W20)

Abstract: This paper introduces two randomized preconditioning techniques for robustly solving kernel ridge regression (KRR) problems with a medium to large number of data points ($10^{4}leqNleq10^7$). The first method, RPCholesky preconditioning, is capable of accurately solving 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 $kllN$ selected data centers at a cost of $O((N+k^2)klogk)$ operations. The proposed methods solve a broad range of KRR problems and overcome the failure modes of previous KRR preconditioners, making them ideal for practical applications.

This page was built for publication: Robust, randomized preconditioning for kernel ridge regression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6434197)