BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
Abstract
Kernel Ridge Regression (KRR) is a theoretically sound algorithm for nonparametric learning, which is also often used to investigate properties of deep learning. However, the exact KRR formulation incurs time and memory costs preventing applicability to large datasets, motivating the development of approximate solvers. These algorithms rely on (i) iterative methods, to avoid the computational burden of direct solutions; (ii) sketching or batching, to reduce the problem size; and (iii) preconditioning, to accelerate convergence. While crucial for fast convergence, preconditioning incurs memory costs that can be managed by lowering the number of free parameters of the model, potentially at the expense of expressivity and hence accuracy. To address this challenge, we propose BLOKS, a Conjugate Gradient-based solver for Nyström-sketched KRR built around a novel preconditioner that combines a block Jacobi approximation with sketching. The BLOKS preconditioner has memory cost independent of both the dataset size and the number of parameters, allowing scaling to large models. We provide a memory-efficient, GPU-accelerated implementation and show that BLOKS achieves excellent accuracy while retaining favorable time/memory complexity. Indeed, on standard large-scale datasets used to benchmark kernel solvers, BLOKS achieves comparable or better performances than state-of-the-art methods.
Related
- Comparative Performance Analysis of Optimization Solvers for Linear Support Vector Machines: Impact of Preconditioning and Dimensionality An Empirical Study Using the Benchopt Framework
- Preconditioning proximal Galerkin: mesh and degree robust solvers for variational inequalities
- Impact of Feature Scaling on the Convergence Speed of Linear SVM Solvers : An Empirical Benchmark
- Scaling Local Solvers with the Many-Body Expansion
- An Equivalence result for sketched Anderson Acceleration and sketched GMRES
BibTeX
@misc{vitale2026bloks,
title = {{BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning}},
author = {Giordano Vitale and Giacomo Meanti and Marco Rando and Blanca Ayuso de Dios and Lorenzo Rosasco},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13382},
eprint = {2610.13382},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13382},
}
RIS
TY - UNPB
TI - BLOKS: Scaling Kernel Solvers with Sketched Block Preconditioning
AU - Giordano Vitale
AU - Giacomo Meanti
AU - Marco Rando
AU - Blanca Ayuso de Dios
AU - Lorenzo Rosasco
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.13382
UR - https://arxiv.org/abs/2610.13382
AB - Kernel Ridge Regression (KRR) is a theoretically sound algorithm for nonparametric learning, which is also often used to investigate properties of deep learning. However, the exact KRR formulation incurs time and memory costs preventing applicability to large datasets, motivating the development of approximate solvers. These algorithms rely on (i) iterative methods, to avoid the computational burden of direct solutions; (ii) sketching or batching, to reduce the problem size; and (iii) preconditioning, to accelerate convergence. While crucial for fast convergence, preconditioning incurs memory costs that can be managed by lowering the number of free parameters of the model, potentially at the expense of expressivity and hence accuracy. To address this challenge, we propose BLOKS, a Conjugate Gradient-based solver for Nyström-sketched KRR built around a novel preconditioner that combines a block Jacobi approximation with sketching. The BLOKS preconditioner has memory cost independent of both the dataset size and the number of parameters, allowing scaling to large models. We provide a memory-efficient, GPU-accelerated implementation and show that BLOKS achieves excellent accuracy while retaining favorable time/memory complexity. Indeed, on standard large-scale datasets used to benchmark kernel solvers, BLOKS achieves comparable or better performances than state-of-the-art methods.
ER -