Metraipolis › archive › dc_7a67ab0a635a

Analysis of Nystrom method with sequential ridge leverage scores — arXiv:2604.20077

Source: arXiv (en)
Original: https://arxiv.org/abs/2604.20077
License (as archived): CC0-1.0
Archived: 2026-10-06T09:33:07.140Z
SHA-256 of the archived text: 1baff2fcef2d55dc2c2698f47417f88ebe8d608677064259f47be448823aae6b
Stable URL of this page: https://metraipolis.com/documento/dc_7a67ab0a635a

How to cite

Analysis of Nystrom method with sequential ridge leverage scores — arXiv:2604.20077 — arXiv (en), https://arxiv.org/abs/2604.20077 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a67ab0a635a (Metraipolis archive dc_7a67ab0a635a, sha256 1baff2fcef2d55dc2c2698f47417f88ebe8d608677064259f47be448823aae6b)

BibTeX

@misc{dc7a67ab0a635a,
  title = {Analysis of Nystrom method with sequential ridge leverage scores — arXiv:2604.20077},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2604.20077},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a67ab0a635a; sha256 1baff2fcef2d55dc2c2698f47417f88ebe8d608677064259f47be448823aae6b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2604.20077. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (elenco arXiv stat.ML, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2604.20077 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T08:24:13.965Z dalla pagina https://arxiv.org/list/stat.ML/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).