Analysis of Nystrom method with sequential ridge leverage scores

ArXi:2604.20077v1 Announce Type: new Large-scale kernel ridge regression (KRR) is limited by the need to a large kernel matrix K_t. To avoid storing the entire matrix K_t, Nystrom methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed matrix. The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, recent works show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for the approximation.