# Analysis of Nystrom method with sequential ridge leverage scores

arXiv: https://arxiv.org/abs/2604.20077 · HTML: https://mlsanity.com/paper/2604.20077/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 25 references that are in the map.
- First posted on arXiv 22 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [Divide and Conquer Kernel Ridge Regression: A Distributed Algorithm with Minimax Optimal Rates](https://mlsanity.com/paper/1305.5029/) (2013)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Analysis of Resparsification](https://mlsanity.com/paper/1605.08194/) (2016)

## Built on by (most cited first, 2 of 2)

- [Pack only the essentials: Adaptive dictionary learning for kernel ridge regression](https://mlsanity.com/paper/2604.22386/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

Large-scale kernel ridge regression (KRR) is limited by the need to store 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. While exact RLSs are as difficult to compute as a KRR solution, we may be able to approximate them well enough. In this paper, we study KRR problems in a sequential setting and introduce the INK-ESTIMATE algorithm, that incrementally computes the RLSs estimates. INK-ESTIMATE maintains a small sketch of K_t, that at each step is used to compute an intermediate estimate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel matrix is sufficient. Second, the algorithm requires a fixed, small space budget to run dependent only on the effective dimension of the kernel matrix. Finally, our sketch provides strong approximation guarantees on the distance between the true kernel matrix and its approximation, and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.