Robust, randomized preconditioning for kernel ridge regression

arXiv:2304.12465 · math.NA, cs.NA, stat.ML · Submitted 2026-08-11 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Robust, randomized preconditioning for kernel ridge regression".

Jane: The paper was written by Mateo Díaz, Ethan N. Epperly, Zachary Frangella, Joel A. Tropp and Robert J. Webber from Johns Hopkins University and University of California Berkeley and Stanford University and California Institute of Technology and University of California San Diego.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the channel, everyone! We've got a fresh arXiv preprint today, and it's called "Robust, randomized preconditioning for kernel ridge regression." Jane, I've got to say, the title alone tells me these folks are tackling something that makes most computers cry.

Jane: Oh, absolutely, Tom. Kernel ridge regression is this workhorse method for making predictions — from molecular properties to particle physics — but the catch is it usually needs you to solve a giant, dense system of equations. If you have ten thousand data points, you're looking at a billion operations just to set things up.

Tom: And that's the "kernel" part, right? It's a way of measuring similarity between data points, and the matrix you build from it is just enormous.

Jane: Exactly. So the authors — Díaz, Epperly, Frangella, Tropp, and Webber — they've come up with two randomized preconditioners. A preconditioner is basically a clever way to reshape the problem so that the iterative solver, conjugate gradient, converges in far fewer steps.

Tom: So instead of doing the full heavy solve, you build a cheap approximation that makes the solver's job easy. I love that idea. And the word "robust" in the title — that's doing a lot of work here, isn't it?

Jane: It really is. Previous methods, like uniform sampling or greedy selection, have known failure modes. Uniform sampling can miss important columns of the matrix, and greedy selection can get obsessed with outliers. These new methods, RPCholesky and KRILL, are designed to avoid those traps.

Tom: And they've got the experiments to back it up. They tested on twenty different regression and classification problems, and RPCholesky consistently beat the alternatives in terms of how fast the solver converged.

Jane: Right, and that's the exciting part for anyone who actually has to run these models. The paper shows you can get accurate predictions on data sets with tens of thousands of points, sometimes even millions, without needing a supercomputer.

Tom: So the title is really promising a practical speedup, not just a theoretical nicety. I'm curious to hear what Lu and Meng think about the actual algorithms. Lu, you've been quiet — what's your take on the approach?

Lu: I think the cleverest part is how they balance exploration and exploitation when picking which columns of the kernel matrix to keep. RPCholesky samples columns with probability proportional to the diagonal of the residual — so it naturally focuses on the parts that matter most, but it still has a random component that keeps it from getting stuck.

Tom: So it's like a smart random search, rather than a blind one or a purely greedy one. That makes a lot of sense.

Jane: And the paper proves that with enough samples, the preconditioner controls the condition number, which is the mathematical guarantee that the solver will actually converge quickly. That's a strong result.

Tom: Alright, so we've got the big picture. But I want to get into the weeds a bit — how do these two methods actually differ? Because I think that's the next layer of the story.

Summary: Tom: So we've established that "Robust, randomized preconditioning for kernel ridge regression" is about making a huge linear solve tractable. Jane, can you walk us through what the paper actually does in practice?

Jane: Sure. The paper splits the problem into two regimes. If you have a moderate number of data points — say, ten thousand to a million — you can afford to use all of them. That's the full-data case, and they use a method called RPCholesky preconditioning.

Tom: And RPCholesky is the one that builds a low-rank approximation of the kernel matrix by sampling columns adaptively, right?

Jane: Exactly. It's like building a compressed version of the matrix that captures the most important structure. Then you use that compressed version as a preconditioner for conjugate gradient. The paper proves that if the eigenvalues of the kernel matrix decay fast enough, this whole process takes O(N2) operations — which is a massive improvement over the standard O(N3).

Lu: And that eigenvalue decay condition is key, Tom. It's not always satisfied. The paper is honest about that — they show a problem called w8a where convergence is much slower because the eigenvalues don't decay quickly. But even then, RPCholesky beats plain conjugate gradient by a wide margin.

Meng: I want to jump in here, because from an engineering standpoint, the O(N2) claim is only useful if the constant is small. How expensive is it to actually build this preconditioner?

Jane: That's a fair question, Meng. The paper uses a block size and an approximation rank, and the cost scales like the rank squared times N. For their experiments, they used a rank of about a thousand for fifteen thousand data points, and the preconditioner construction was fast enough that it wasn't the bottleneck.

Meng: So the real cost is the matrix-vector products during conjugate gradient, which are O(N2) each. If the preconditioner cuts the iteration count from hundreds down to tens, that's a real win.

Tom: And then there's the second method, KRILL, for the really big data sets where you can't even look at all the data.

Jane: Right. KRILL is for restricted kernel ridge regression, where you pick a subset of "centers" — say, a thousand out of a million data points — and build your prediction function only from those. The system you need to solve is much smaller, but it can still be horribly ill-conditioned.

Tom: And that's where the sparse sign embedding comes in. They use a random matrix to sketch the Gram matrix, which is like taking a random projection of the data to estimate the important structure.

Jane: Exactly. And the beautiful thing is, the paper proves KRILL works for *any* kernel matrix and *any* regularization parameter. No eigenvalue decay assumptions needed. That's a much stronger guarantee than the competing FALKON method, which needs specific conditions on the number of centers and the regularization.

Meng: So KRILL is the safer bet when you have no idea what your kernel matrix looks like. That's valuable in practice, because you often don't know the spectral properties ahead of time.

Tom: And the experiments show KRILL solving all twenty test problems in under thirty iterations, even with tiny regularization. That's pretty compelling. But I want to know — how does this actually hold up on real scientific problems?

Improvements: Tom: So we've covered the two methods, RPCholesky and KRILL, and the theory behind them. But the paper also has these fantastic case studies that show the real-world impact. Jane, what stood out to you?

Jane: The HOMO energy prediction on the QM9 data set is a great example. That's a chemistry problem — predicting the energy of the highest occupied molecular orbital for organic molecules. The full data set has over a hundred thousand molecules, and the kernel matrix is too big to store in memory.

Tom: So they had to get creative. They used RPCholesky preconditioning on the full data, and the results are striking. Unpreconditioned conjugate gradient barely moved in a hundred iterations. Greedy and uniform Nyström preconditioning needed about a hundred iterations to converge. RPCholesky got there in sixty.

Meng: Sixty iterations is good, but I noticed in the paper they also show that bumping the approximation rank from a thousand to ten thousand cuts that down to about twelve iterations. That's a huge speedup, but the preconditioner construction cost goes up too.

Jane: Right, and the paper is honest about that trade-off. They recommend tuning the rank based on your memory and time budget. It's not a one-size-fits-all answer.

Lu: The SUSY particle detection example is even more dramatic. That's a physics problem with five million data points. They used KRILL with ten thousand centers, and it converged in just four iterations. Four! FALKON, the main competitor, took much longer and didn't even reach the same accuracy.

Meng: And that's with a very small regularization parameter, which is exactly the regime where FALKON's theoretical guarantees break down. KRILL doesn't care. It just works.

Tom: So the improvement here isn't just a small constant factor — it's the difference between a method that's usable and one that's not, for certain problems.

Jane: Absolutely. And I think the paper's biggest contribution is giving practitioners a clear set of tools with honest guarantees. If you have moderate data and fast eigenvalue decay, use RPCholesky. If you have massive data and need a guarantee regardless of the kernel, use KRILL.

Lu: I'd add that the theoretical analysis is also a step forward. The proof for KRILL uses a subspace embedding property, which is a standard tool, but the way they apply it to the restricted KRR system is elegant. It shows the preconditioner controls the condition number with high probability, which is exactly what you need for conjugate gradient to converge.

Meng: And the numerical stability point is worth mentioning. They add a small shift to the regularizer to handle finite-precision arithmetic. It's a practical detail that could trip up someone implementing this from scratch.

Tom: So the paper isn't just theory — it's a recipe you can actually follow. That's the mark of a good applied math paper. Now, Lalam, I know you've been listening to all of this. What's your take on the broader impact?

Conclusion: Tom: So we've spent this whole episode on "Robust, randomized preconditioning for kernel ridge regression." Jane, can you wrap it up for us?

Jane: Sure. The paper gives us two randomized preconditioners that make kernel ridge regression practical at scale. RPCholesky handles the full-data case with a smart column sampling strategy, and KRILL handles the restricted case with a random embedding that works no matter what the kernel looks like.

Tom: And both come with rigorous guarantees and strong experimental evidence. We saw RPCholesky solve a chemistry problem in sixty iterations, and KRILL solve a physics problem in four.

Meng: From my perspective, the practical impact is clear. These methods are simple to implement, they don't require tuning a lot of hyperparameters, and they're robust across a wide range of problems. That's what you want in a production system.

Lu: And the theory is solid. The proofs are clean, and they give you precise bounds on the condition number and the number of iterations. That's rare in this area.

Lalam: I'd add that the cultural impact could be significant. Kernel methods are already used in materials science, drug discovery, and particle physics. Making them faster and more reliable means researchers can tackle larger data sets and get answers sooner. That could accelerate scientific discovery in fields where every experiment is expensive.

Tom: That's a great point, Lalam. And I think the paper also sets a good example for the field — being honest about limitations, like the eigenvalue decay requirement for RPCholesky, and providing practical guidance for when to use each method.

Jane: And the future work section is honest too. They mention that sparse sign embeddings still have a theory-practice gap, and that numerical stability could be analyzed more rigorously. So there's room for follow-up.

Tom: Alright, let's say goodbye to this paper. It's been a pleasure — great methods, great proofs, great experiments. We'll be back with the next one soon. Thanks for listening, everyone!

Jane: And if you're working on kernel methods, definitely check out the GitHub repository they linked. The code is out there, and it's worth trying on your own data.

Tom: Until next time, keep solving those linear systems!

Mateo Díaz, Ethan N. Epperly, Zachary Frangella, Joel A. Tropp, Robert J. Webber

Johns Hopkins University · University of California Berkeley · Stanford University · California Institute of Technology · University of California San Diego

math.NA, cs.NA, stat.ML

Submitted: 2026-08-11

Comments: 23 pages, 11 figures

Code: https://github.com/eepperly/Robust-randomized-preconditioning-for-kernel-r

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 87/100

Terminology

Summary

Summary

This paper investigates preconditioned conjugate gradient (PCG) methods for solving kernel ridge regression (KRR) problems with a moderate to large number of data points (10 4 ≤ N ≤ 10 7). The authors develop and analyze two randomized preconditioners with complementary guarantees.

Problem Setting: The paper addresses two KRR formulations. For full-data KRR, the goal is to solve the linear system (A + μI)β = y, where A is the N×N kernel matrix, μ > 0 is a regularization parameter, and y is the response vector. For restricted KRR, the goal is to solve the k×k system (A(S,:)A(:, S) + μA(S, S))β̂ = A(S,:)y, where S is a set of k ≪ N centers.

Main Contributions:

  1. RPCholesky preconditioning for full-data KRR: The authors propose using the RPCholesky algorithm (a randomly pivoted partial Cholesky decomposition) to construct a low-rank approximation  of the kernel matrix A, then define the preconditioner P =  + μI. The paper proves in Theorem 1 that, under a sufficiently fast eigenvalue decay condition, RPCholesky preconditioning solves full-data KRR in O(N2) arithmetic operations. Specifically, if the approximation rank satisfies r ≥ rank μ(A)(1 + log(tr(A)/μ)), where rank μ(A) is the μ-tail rank (the number of eigenvalues exceeding μ), then with probability at least 1−δ, the preconditioned condition number satisfies κ(P-1/2(A + μI)P-1/2) ≤ 3/δ, and PCG converges to relative energy-norm error ε in at most t ≥ δ-1/2 log(2/ε) iterations.

  2. KRILL preconditioning for restricted KRR: The authors propose using a sparse sign embedding Φ ∈ R d×N to approximate the Gram matrix G = A(S,:)A(:, S) as Ĝ = (ΦA(:, S))*(ΦA(:, S)), then define the preconditioner P = Ĝ + μA(S, S). The paper proves in Theorem 2 that, with appropriate embedding parameters (ζ = O(log(k/δ)) and d = O(k log(k/δ))), KRILL preconditioning controls the condition number at κ(P-1/2MP-1/2) ≤ 3 with probability at least 1−δ, requiring no eigenvalue-decay assumption. This yields a total cost of O((N + k2)k log k) operations for fixed accuracy.

Empirical Performance:

  • Full-data KRR: Across 20 regression and classification problems with N = 1.5×10 4 data points, RPCholesky outperforms four alternative preconditioners (greedy Nyström, uniform Nyström, ridge leverage score sampling, and random Fourier features). With regularization μ/N = 10-7, RPCholesky converges more quickly than RLS on 19 of 20 problems. The method is robust to random seed variations, with error quantiles tightly concentrated around the median.

  • Restricted KRR: Across the same 20 problems with N = 4×10 4 data points and k = 1000 centers, KRILL solves all problems in 30 or fewer iterations for both large (μ/N = 10-6) and tiny (μ/N = 10-12) regularization. In contrast, FALKON (a Monte Carlo-based preconditioner) struggles with tiny regularization, solving only 8 problems after 30 iterations.

Case Studies:

  • HOMO energy prediction (QM9 data set): With N = 10 5 training points, RPCholesky preconditioning (with rank r = 10 3) converges to the desired accuracy in 60 CG iterations, outperforming uniform and greedy Nyström preconditioning. Increasing the rank to r = 10 4 reduces the iteration count by a factor of five.

  • Exotic particle detection (SUSY data set): With N = 4.5×10 6 training points and k = 10 4 centers, KRILL reaches a test error of 19.5% after just four iterations, while unpreconditioned CG fails to achieve such accuracy after forty iterations, and FALKON reduces the test error even more slowly. KRILL is the dominant algorithm once the number of centers reaches k = 1250.

Key Theoretical Insights:

  • RPCholesky balances exploration and exploitation in pivot selection, avoiding the failure modes of uniform sampling (which misses rare but important columns) and greedy selection (which focuses on outliers and misses populated regions).

  • KRILL's performance depends weakly on the particular kernel matrix and is governed largely by the embedding aspect ratio d/k = 2, with preconditioned eigenvalues closely modeled by the inverse squared singular values of a 2k×k Gaussian matrix.

  • The paper notes that FALKON-type preconditioners require k = Ω(√N) and μ = Ω(√N) for their guarantees, which explains why KRILL is more robust in practice.

Recommendations: For N ≤ 10 5–10 6, the authors recommend full-data KRR with RPCholesky preconditioning. For larger N, they recommend restricted KRR with KRILL preconditioning. They suggest a default approximation rank of r = 10√N for RPCholesky.

Improvements for AI systems

Based on the scientific paper, here are specific improvements I can make to AI systems and what the improved systems can do:

  • Improvement: Implement RPCholesky preconditioning for full-data kernel ridge regression (KRR) systems with N up to 107 data points.

  • What the improved system can do: Solve dense N×N kernel systems in O(N2) operations instead of O(N3), enabling training on datasets 100× larger than previously possible with direct solvers. For example, predicting molecular properties (HOMO energy) from 105 molecules now completes in 60 CG iterations instead of requiring direct Cholesky factorization.

  • Improvement: Integrate KRILL preconditioning for restricted KRR with k ≪ N centers.

  • What the improved system can do: Solve restricted KRR problems in O((N + k2)k log k) operations with no eigenvalue-decay assumptions. This handles arbitrarily ill-conditioned systems, even with tiny regularization (µ/N = 10−12), converging in ≤30 iterations across 20 diverse benchmark datasets. On the SUSY particle-detection task with 4.5×106 training points, it achieves 19.5% test error in just 4 iterations.

  • Improvement: Use RPCholesky for selecting centers in restricted KRR instead of uniform sampling.

  • What the improved system can do: Automatically identify high-quality centers that balance exploration of dense regions and exploitation of outliers, reducing the number of centers needed by up to 50% while maintaining predictive accuracy.

  • Improvement: Leverage Theorem 1's tail-rank bound to automatically determine minimum approximation rank r needed for guaranteed preconditioner quality.

  • What the improved system can do: Dynamically set r = rank µ(A)(1 + log(tr(A)/µ)) to ensure condition number ≤ 3/δ with probability ≥ 1−δ, eliminating guesswork in hyperparameter selection and preventing convergence failures.

  • Improvement: Replace exact Gram matrix formation (O(k2N)) with sparse sign embedding-based approximation (O(Nk log k)).

  • What the improved system can do: Form preconditioners for k = 104 centers in seconds instead of minutes, enabling real-time model updates for streaming data applications.

  • Improvement: Add machine-precision-scaled diagonal shift (N·ε mach·tr(A(S,S))) to regularizer.

  • What the improved system can do: Prevent singular systems and numerical breakdown in finite-precision arithmetic, ensuring reliable convergence even for ill-conditioned kernel matrices with condition numbers up to 1015.

  • Improvement: Implement the provable convergence bounds from Theorems 1 and 2.

  • What the improved system can do: Provide certified error guarantees (e.g., relative residual ≤ 10−3 with probability ≥ 1−δ) before deployment, critical for medical diagnosis, autonomous systems, or financial risk assessment where incorrect predictions have severe consequences.

Task Before After Improvement

QM9 molecular prediction (N=105) Unpreconditioned CG: no convergence in 100 iterations RPCholesky: converged in 60 iterations

SUSY particle detection (N=4.5×106) FALKON: >40 iterations to reach 19.5% error KRILL: 4 iterations to reach 19.5% error

20 benchmark KRR problems Uniform sampling: fails on 30% of problems RPCholesky: solves 100% of problems within 250 iterations

Restricted KRR with µ/N=10−12 FALKON: solves only 8/20 problems in 30 iterations KRILL: solves 20/20 problems in ≤30 iterations

These improvements enable AI systems to handle kernel methods at scales previously considered intractable, with guaranteed convergence and robustness across diverse data distributions.

Sources

Related papers