Robust, randomized preconditioning for kernel ridge regression
Abstract
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.
Fields of Study & Subjects
Sparse and Compressive Sensing Techniques
Machine Learning and Algorithms
Stochastic Gradient Optimization Techniques
Publication details
- Journal / source
- Advances in Computational Mathematics
- Publisher
- Springer Science and Business Media LLC
- Volume
- 52
- Issue
- 5
- Publication date
- 18 September 2026
- Language
- EN