mlsanityData to 7 Oct 2026

Robust, randomized preconditioning for kernel ridge regression

arXiv 2304.12465 ↗First posted 24 Apr 2023math.NA cs.NA stat.MLcited by 8

Not on the map. Why?

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.

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

Builds on

25 of 72 references.

References · 25

  1. 2018GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Accelerationcited by 603
  2. 2014OpenML: networked science in machine learningcited by 523
  3. 2020Machine Learning Force Fieldscited by 204
  4. 2019Exact Gaussian Processes on a Million Data Pointscited by 118
  5. 2020Kernel methods through the roof: handling billions of points efficientlycited by 88
  6. 2017FALKON: An Optimal Large Scale Kernel Methodcited by 82
  7. 2015Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergencecited by 72
  8. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  9. 2016Faster Kernel Ridge Regression Using Sketching and Preconditioningcited by 43
  10. 2018On Fast Leverage Score Sampling and Optimal Learningcited by 40
  11. 2020Sparse Cholesky factorization by Kullback-Leibler minimizationcited by 40
  12. 2023Randomized Numerical Linear Algebra : A Perspective on the Field With an Eye to Softwarecited by 38
13 more
  1. 2014Scalable Kernel Methods via Doubly Stochastic Gradientscited by 36
  2. 2016Preconditioning Kernel Matricescited by 32
  3. 2022Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluationscited by 31
  4. 2017Diving into the shallows: a computational perspective on large-scale shallow learningcited by 30
  5. 2020Machine learning for electronically excited states of moleculescited by 30
  6. 2022Learning new physics efficiently with nonparametric methodscited by 20
  7. 2016Solving Ridge Regression using Sketched Preconditioned SVRGcited by 15
  8. 2019Fast and Accurate Gaussian Kernel Ridge Regression Using Matrix Decompositions for Preconditioningcited by 6
  9. 2016Hierarchically Compositional Kernels for Scalable Nonparametric Learningcited by 5
  10. 2021Kernel approximation on algebraic varietiescited by 4
  11. 2021Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditionerscited by 3
  12. 2022Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergencecited by 2
  13. 2023Linear-scaling kernels for protein sequences and small molecules outperform deep learning while providing uncertainty quantitation and improved interpretabilitycited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 3; 2026: 1.

8 papers.

  1. 2024The fast committor machine: Interpretable prediction with kernelscited by 5
  2. 2024Embrace rejection: Kernel matrix approximation by accelerated randomly pivoted Choleskycited by 5
  3. 2024Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioningcited by 4
  4. 2024Supervised Kernel Thinningcited by 3
  5. 2025Turbocharging Gaussian Process Inference with Approximate Sketch-and-Projectcited by 3
  6. 2025Accelerating Natural Gradient Descent for PINNs with Randomized Numerical Linear Algebracited by 1
  7. 2025Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nystr"om Methodcited by 1
  8. 2026Accelerating Regularized Attention Kernel Regression for Spectrum Cartographycited by 1