Kernel solvers stop choking on preconditioner memory: sketched blocks push model size to ten million parameters with better accuracy

A kernel ridge regression solver can now decouple model size from memory: the preconditioner keeps only one block, so its memory no longer grows with the dataset size or the number of parameters. Earlier sketched preconditioners had to store a matrix scaling quadratically with the number of parameters, running out of memory as the model grew and forcing practitioners to keep models small. On the Higgs dataset, Falkon cannot scale beyond a certain parameter count without running out of memory because of the quadratic storage requirement, while Bloks holds memory fixed and scales parameters to ten million, with test accuracy improving noticeably.

The construction partitions the Nyström centers into disjoint blocks, builds a sketched diagonal block for each, and stacks them into the preconditioner. A plain block Jacobi preconditioner also avoids memory growth with parameters, but each block requires a Gram product that is numerically unstable and too costly at scale. Each sketched block is expressed through a Cholesky factor, and two in-place Cholesky decompositions store only a single matrix; the blocks are decoupled, so they can be processed sequentially or in parallel, and experiments ran on a single A100 with training times competitive with state-of-the-art methods.

The report covers a solver for Nyström-sketched kernel ridge regression, with experiments run in single precision on a single A100 and compared against EigenPro 4, Joker, ASkotch and Falkon. The authors propose extending the method to other loss functions, investigating different block partitioning strategies, and adding coarse corrections that capture inter-block interactions.

The authors note that the extra regularization introduced by the block approximation makes Bloks worse than standard block Jacobi in training error, while test performance is nearly indistinguishable, and a rigorous theoretical analysis is left for future work. Training time grows super-linearly with block size, and once all blocks no longer fit in memory the preconditioning cost is no longer negligible.