# Pack only the essentials: Adaptive dictionary learning for kernel ridge regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 5 references that are in the map.
- First posted on arXiv 24 Apr 2026.

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

- [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)
- [Fast Randomized Kernel Methods With Statistical Guarantees](https://mlsanity.com/paper/1411.0306/) (2014)
- [Analysis of Nystrom method with sequential ridge leverage scores](https://mlsanity.com/paper/2604.20077/) (2026)

## Abstract (arXiv)

One of the major limits of kernel ridge regression (KRR) is that storing and manipulating the kernel matrix K_n for n samples requires O(n^2) space, which rapidly becomes unfeasible for large n. Nystrom approximations reduce the space complexity to O(nm) by sampling m columns from K_n. Uniform sampling preserves KRR accuracy (up to epsilon) only when m is proportional to the maximum degree of freedom of K_n, which may require O(n) columns for datasets with high coherence. Sampling columns according to their ridge leverage scores (RLS) gives accurate Nystrom approximations with m proportional to the effective dimension, but computing exact RLS also requires O(n^2) space. (Calandriello et al. 2016) propose INK-Estimate, an algorithm that processes the dataset incrementally and updates RLS, effective dimension, and Nystrom approximations on-the-fly. Its space complexity scales with the effective dimension but introduces a dependency on the largest eigenvalue of K_n, which in the worst case is O(n). In this paper we introduce SQUEAK, a new algorithm that builds on INK-Estimate but uses unnormalized RLS. As a consequence, the algorithm is simpler, does not need to estimate the effective dimension for normalization, and achieves a space complexity that is only a constant factor worse than exact RLS sampling.