# Robust, randomized preconditioning for kernel ridge regression

arXiv: https://arxiv.org/abs/2304.12465 · HTML: https://mlsanity.com/paper/2304.12465/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 72 references that are in the map.
- First posted on arXiv 24 Apr 2023.

## Builds on (most cited first, 25 of 25)

- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [OpenML: networked science in machine learning](https://mlsanity.com/paper/1407.7722/) (2014)
- [Machine Learning Force Fields](https://mlsanity.com/paper/2010.07067/) (2020)
- [Exact Gaussian Processes on a Million Data Points](https://mlsanity.com/paper/1903.08114/) (2019)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [On Fast Leverage Score Sampling and Optimal Learning](https://mlsanity.com/paper/1810.13258/) (2018)
- [Sparse Cholesky factorization by Kullback-Leibler minimization](https://mlsanity.com/paper/2004.14455/) (2020)
- [Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Software](https://mlsanity.com/paper/2302.11474/) (2023)
- [Scalable Kernel Methods via Doubly Stochastic Gradients](https://mlsanity.com/paper/1407.5599/) (2014)
- [Preconditioning Kernel Matrices](https://mlsanity.com/paper/1602.06693/) (2016)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [Diving into the shallows: a computational perspective on large-scale shallow learning](https://mlsanity.com/paper/1703.10622/) (2017)
- [Machine learning for electronically excited states of molecules](https://mlsanity.com/paper/2007.05320/) (2020)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioning](https://mlsanity.com/paper/1905.10587/) (2019)
- [Hierarchically Compositional Kernels for Scalable Nonparametric Learning](https://mlsanity.com/paper/1608.00860/) (2016)
- [Kernel approximation on algebraic varieties](https://mlsanity.com/paper/2106.02755/) (2021)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [Linear-scaling kernels for protein sequences and small molecules outperform deep learning while providing uncertainty quantitation and improved interpretability](https://mlsanity.com/paper/2302.03294/) (2023)

## Built on by (most cited first, 9 of 9)

- [The fast committor machine: Interpretable prediction with kernels](https://mlsanity.com/paper/2405.10410/) (2024)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning](https://mlsanity.com/paper/2405.05865/) (2024)
- [Supervised Kernel Thinning](https://mlsanity.com/paper/2410.13749/) (2024)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebra](https://mlsanity.com/paper/2505.11638/) (2025)
- [Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Method](https://mlsanity.com/paper/2506.17556/) (2025)
- [Accelerating Regularized Attention Kernel Regression for Spectrum Cartography](https://mlsanity.com/paper/2604.25138/) (2026)
- [BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning](https://mlsanity.com/paper/2610.13382/) (2026)

## Abstract (arXiv)

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