mlsanityData to 14 Oct 2026

Kernel methods through the roof: handling billions of points efficiently

arXiv 2006.10350 ↗First posted 18 Jun 2020cs.LG stat.MLcited by 89

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 16; 2022: 20; 2023: 17; 2024: 14; 2025: 15; 2026: 7.

89 papers.

Sort:

By area:

  1. 2021Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolationcited by 132
  2. 2022Learning Dynamical Systems via Koopman Operator Regression in Reproducing Kernel Hilbert Spacescited by 67
  3. 2022Unbalanced Optimal Transport, from Theory to Numericscited by 46
  4. 2021Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regressioncited by 40
  5. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 32
  6. 2021A Witness Two-Sample Testcited by 23
  7. 2022Neural Tangent Kernel: A Surveycited by 23
  8. 2022Learning new physics efficiently with nonparametric methodscited by 21
  9. 2021Tighter Bounds on the Log Marginal Likelihood of Gaussian Process Regression Using Conjugate Gradientscited by 20
  10. 2022Distribution Regression with Sliced Wasserstein Kernelscited by 18
  11. 2021Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processescited by 17
  12. 2021Simple, Fast, and Flexible Framework for Matrix Completion with Infinite Width Neural Networkscited by 17
38 more
  1. 2022Few-shot Backdoor Attacks via Neural Tangent Kernelscited by 15
  2. 2023Estimating Koopman operators with sketching to provably learn large scale dynamical systemscited by 15
  3. 2024Memory-Scalable and Simplified Functional Map Learningcited by 14
  4. 2023Toward Large Kernel Modelscited by 13
  5. 2024Kermut: Composite kernel regression for protein variant effectscited by 12
  6. 2022Efficient Hyperparameter Tuning for Large Scale Kernel Ridge Regressioncited by 11
  7. 2022Low-Precision Arithmetic for Fast Gaussian Processescited by 10
  8. 2023Robustifying Generalizable Implicit Shape Networks with a Tunable Non-Parametric Modelcited by 10
  9. 2023Kernel Regression with Infinite-Width Neural Networks on Millions of Examplescited by 9
  10. 2023Robust, randomized preconditioning for kernel ridge regressioncited by 9
  11. 2021Sampling from Arbitrary Functions via PSD Modelscited by 8
  12. 2022Stochastic Zeroth order Descent with Structured Directionscited by 8
  13. 2023Fast kernel methods for Data Quality Monitoring as a goodness-of-fit testcited by 8
  14. 2021Ada-BKB: Scalable Gaussian Process Optimization on Continuous Domains by Adaptive Discretizationcited by 7
  15. 2023Efficient kernel surrogates for neural network-based regressioncited by 7
  16. 2024Multiple testing for signal-agnostic searches of new physics with machine learningcited by 7
  17. 2021ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitionscited by 6
  18. 2022Explaining Preferences with Shapley Valuescited by 6
  19. 2023The Galerkin method beats Graph-Based Approaches for Spectral Algorithmscited by 6
  20. 2023Quantized Fourier and Polynomial Features for more Expressive Tensor Network Modelscited by 6
  21. 2021Faster Kernel Interpolation for Gaussian Processescited by 5
  22. 2022Fast Kernel Methods for Generic Lipschitz Losses via p-Sparsified Sketchescited by 5
  23. 2023Kernelized Diffusion mapscited by 5
  24. 2023Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernelscited by 5
  25. 2023Nonlinear SVD with Asymmetric Kernels: feature learning and asymmetric Nystr"om methodcited by 5
  26. 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
  27. 2022Memory Safe Computations with XLA Compilercited by 4
  28. 2023Transfer learning for atomistic simulations using GNNs and kernel mean embeddingscited by 4
  29. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  30. 2024Practical multi-fidelity machine learning: fusion of deterministic and Bayesian modelscited by 4
  31. 2024A Theoretical Characterization of Optimal Data Augmentations in Self-Supervised Learningcited by 4
  32. 2025Computational Efficiency under Covariate Shift in Kernel Ridge Regressioncited by 4
  33. 2025Comparing Generative Models with the New Physics Learning Machinecited by 4
  34. 2025Learning to Validate Generative Models: a Goodness-of-Fit Approachcited by 4
  35. 2021Sublinear Time Approximation of Text Similarity Matricescited by 3
  36. 2022Active Labeling: Streaming Stochastic Gradientscited by 3
  37. 2022Learn Fast, Segment Well: Fast Object Segmentation Learning on the iCub Robotcited by 3
  38. 2024Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nystr"om methodcited by 3

50 most cited of 89 All 89 (JSON)