# Preconditioning Kernel Matrices

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Feb 2016.

## Built on by (most cited first, 30 of 33)

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Sampling from Gaussian Process Posteriors using Stochastic Gradient Descent](https://mlsanity.com/paper/2306.11589/) (2023)
- [Posterior and Computational Uncertainty in Gaussian Processes](https://mlsanity.com/paper/2205.15449/) (2022)
- [Preconditioning for Scalable Gaussian Process Hyperparameter Optimization](https://mlsanity.com/paper/2107.00243/) (2021)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Bias-Free Scalable Gaussian Processes via Randomized Truncations](https://mlsanity.com/paper/2102.06695/) (2021)
- [Incremental Ensemble Gaussian Processes](https://mlsanity.com/paper/2110.06777/) (2021)
- [When are Iterative Gaussian Processes Reliably Accurate?](https://mlsanity.com/paper/2112.15246/) (2021)
- [Large-Scale Gaussian Processes via Alternating Projection](https://mlsanity.com/paper/2310.17137/) (2023)
- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Hierarchical Inducing Point Gaussian Process for Inter-domain Observations](https://mlsanity.com/paper/2103.00393/) (2021)
- [Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Cholesky](https://mlsanity.com/paper/2410.03969/) (2024)
- [Marginalising over Stationary Kernels with Bayesian Quadrature](https://mlsanity.com/paper/2106.07452/) (2021)
- [Log-Linear-Time Gaussian Processes Using Binary Tree Kernels](https://mlsanity.com/paper/2210.01633/) (2022)
- [Conditioning Gaussian Processes on Almost Anything](https://mlsanity.com/paper/2605.21041/) (2026)
- [Molecular Energy Learning Using Alternative Blackbox Matrix-Matrix Multiplication Algorithm for Exact Gaussian Process](https://mlsanity.com/paper/2109.09817/) (2021)
- [A Preconditioned Interior Point Method for Support Vector Machines Using an ANOVA-Decomposition and NFFT-Based Matrix-Vector Products](https://mlsanity.com/paper/2312.00538/) (2023)
- [Turbocharging Gaussian Process Inference with Approximate Sketch-and-Project](https://mlsanity.com/paper/2505.13723/) (2025)
- [Adaptive Cholesky Gaussian Processes](https://mlsanity.com/paper/2202.10769/) (2022)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [On the Nystrom Approximation for Preconditioning in Kernel Machines](https://mlsanity.com/paper/2312.03311/) (2023)
- [Gradients of Functions of Large Matrices](https://mlsanity.com/paper/2405.17277/) (2024)
- [High-Dimensional Gaussian Process Regression with Soft Kernel Interpolation](https://mlsanity.com/paper/2410.21419/) (2024)
- [Flow-Induced Diagonal Gaussian Processes](https://mlsanity.com/paper/2509.17153/) (2025)
- [nuGPR: GPU-Accelerated Gaussian Process Regression with Iterative Algorithms and Low-Rank Approximations](https://mlsanity.com/paper/2510.12128/) (2025)
- [Transformers Can Learn Posterior Predictive Distributions In-Context](https://mlsanity.com/paper/2605.26713/) (2026)
- [Locally Smoothed Gaussian Process Regression](https://mlsanity.com/paper/2210.09998/) (2022)
- [Kernel Multigrid: Accelerate Back-fitting via Sparse Gaussian Process Regression](https://mlsanity.com/paper/2403.13300/) (2024)
- [Gaussian Processes Sampling with Sparse Grids under Additive Schwarz Preconditioner](https://mlsanity.com/paper/2408.00206/) (2024)

## Abstract (arXiv)

The computational and storage complexity of kernel machines presents the primary barrier to their scaling to large, modern, datasets. A common way to tackle the scalability issue is to use the conjugate gradient algorithm, which relieves the constraints on both storage (the kernel matrix need not be stored) and computation (both stochastic gradients and parallelization can be used). Even so, conjugate gradient is not without its own issues: the conditioning of kernel matrices is often such that conjugate gradients will have poor convergence in practice. Preconditioning is a common approach to alleviating this issue. Here we propose preconditioned conjugate gradients for kernel machines, and develop a broad range of preconditioners particularly useful for kernel matrices. We describe a scalable approach to both solving kernel machines and learning their hyperparameters. We show this approach is exact in the limit of iterations and outperforms state-of-the-art approximations for a given computational budget.