Advances in Computational Mathematics Вычислительная математика

Robust, randomized preconditioning for kernel ridge regression

Mateo Díaz, Ethan N. Epperly, Zachary Frangella, Joel A. Tropp, Robert J. Webber
Springer Nature · 2026-09-18 · DOI 10.1007/s10444-026-10360-1

Аннотация

Abstract We investigate preconditioned conjugate gradient methods for kernel ridge regression (KRR) problems with a moderate to large number of data points ( $$10^4 \le N \le 10^7$$ 10 4 ≤ N ≤ 10 7 ). We develop and analyze two randomized preconditioners with complementary guarantees. For full-data KRR, RPCholesky preconditioning requires $$\mathcal {O}(N^2)$$ O ( N 2 ) arithmetic operations for fixed accuracy under sufficiently rapid eigenvalue decay of the kernel matrix. For restricted KRR with $$k\ll N$$ k ≪ N centers, KRILL preconditioning requires $$\mathcal {O}((N+k^2)k\log k)$$ 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.

Читать у издателя →