# Kernel methods through the roof: handling billions of points efficiently

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

## Key facts

- Cited by 89 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2020.

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

- [Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation](https://mlsanity.com/paper/2105.14368/) (2021)
- [Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2205.14027/) (2022)
- [Unbalanced Optimal Transport, from Theory to Numerics](https://mlsanity.com/paper/2211.08775/) (2022)
- [Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression](https://mlsanity.com/paper/2102.08208/) (2021)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [A Witness Two-Sample Test](https://mlsanity.com/paper/2102.05573/) (2021)
- [Neural Tangent Kernel: A Survey](https://mlsanity.com/paper/2208.13614/) (2022)
- [Learning new physics efficiently with nonparametric methods](https://mlsanity.com/paper/2204.02317/) (2022)
- [Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradients](https://mlsanity.com/paper/2102.08314/) (2021)
- [Distribution Regression with Sliced Wasserstein Kernels](https://mlsanity.com/paper/2202.03926/) (2022)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networks](https://mlsanity.com/paper/2108.00131/) (2021)
- [Few-shot Backdoor Attacks via Neural Tangent Kernels](https://mlsanity.com/paper/2210.05929/) (2022)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Memory-Scalable and Simplified Functional Map Learning](https://mlsanity.com/paper/2404.00330/) (2024)
- [Toward Large Kernel Models](https://mlsanity.com/paper/2302.02605/) (2023)
- [Kermut: Composite kernel regression for protein variant effects](https://mlsanity.com/paper/2407.00002/) (2024)
- [Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regression](https://mlsanity.com/paper/2201.06314/) (2022)
- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [Robustifying Generalizable Implicit Shape Networks with a Tunable Non-Parametric Model](https://mlsanity.com/paper/2311.12967/) (2023)
- [Kernel Regression with Infinite-Width Neural Networks on Millions of Examples](https://mlsanity.com/paper/2303.05420/) (2023)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [Sampling from Arbitrary Functions via PSD Models](https://mlsanity.com/paper/2110.10527/) (2021)
- [Stochastic Zeroth order Descent with Structured Directions](https://mlsanity.com/paper/2206.05124/) (2022)
- [Fast kernel methods for Data Quality Monitoring as a goodness-of-fit test](https://mlsanity.com/paper/2303.05413/) (2023)
- [Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretization](https://mlsanity.com/paper/2106.08598/) (2021)
- [Efficient kernel surrogates for neural network-based regression](https://mlsanity.com/paper/2310.18612/) (2023)
- [Multiple testing for signal-agnostic searches of new physics with machine learning](https://mlsanity.com/paper/2408.12296/) (2024)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Explaining Preferences with Shapley Values](https://mlsanity.com/paper/2205.13662/) (2022)

## Abstract (arXiv)

Kernel methods provide an elegant and principled approach to nonparametric learning, but so far could hardly be used in large scale problems, since na"ive implementations scale poorly with data size. Recent advances have shown the benefits of a number of algorithmic ideas, for example combining optimization, numerical linear algebra and random projections. Here, we push these efforts further to develop and test a solver that takes full advantage of GPU hardware. Towards this end, we designed a preconditioned gradient solver for kernel methods exploiting both GPU acceleration and parallelization with multiple GPUs, implementing out-of-core variants of common linear algebra operations to guarantee optimal hardware utilization. Further, we optimize the numerical precision of different operations and maximize efficiency of matrix-vector multiplications. As a result we can experimentally show dramatic speedups on datasets with billions of points, while still guaranteeing state of the art performance. Additionally, we make our software available as an easy to use library.