Robust, randomized preconditioning for kernel ridge regression
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917029578014720 |
|---|---|
| author | Díaz, Mateo Epperly, Ethan N. Frangella, Zachary Tropp, Joel A. Webber, Robert J. |
| author_facet | Díaz, Mateo Epperly, Ethan N. Frangella, Zachary Tropp, Joel A. Webber, Robert J. |
| contents | 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 \leq N \leq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12465 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Robust, randomized preconditioning for kernel ridge regression Díaz, Mateo Epperly, Ethan N. Frangella, Zachary Tropp, Joel A. Webber, Robert J. Numerical Analysis Machine Learning 68W20, 65F10, 65F55 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 \leq N \leq 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. |
| title | Robust, randomized preconditioning for kernel ridge regression |
| topic | Numerical Analysis Machine Learning 68W20, 65F10, 65F55 |
| url | https://arxiv.org/abs/2304.12465 |