Analysis of Nyström method with sequential ridge leverage scores

Daniele Calandriello, Alessandro Lazaric, Michal Valko
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:712-721, 2016.

Abstract

Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix Kt. To avoid storing the entire matrix Kt, Nystro?m methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed Kt . The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, [15, 1] show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for Kt. 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 Kt, 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 ?Kt?Kt?2 , and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-calandriello16a, title = {Analysis of Nystr{ö}m method with sequential ridge leverage scores}, author = {Calandriello, Daniele and Lazaric, Alessandro and Valko, Michal}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {712--721}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/calandriello16a/calandriello16a.pdf}, url = {https://proceedings.mlr.press/r14/calandriello16a.html}, abstract = {Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix Kt. To avoid storing the entire matrix Kt, Nystro?m methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed Kt . The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, [15, 1] show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for Kt. 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 Kt, 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 ?Kt?Kt?2 , and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Analysis of Nyström method with sequential ridge leverage scores %A Daniele Calandriello %A Alessandro Lazaric %A Michal Valko %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-calandriello16a %I PMLR %P 712--721 %U https://proceedings.mlr.press/r14/calandriello16a.html %V R14 %X Large-scale kernel ridge regression (KRR) is limited by the need to store a large kernel matrix Kt. To avoid storing the entire matrix Kt, Nystro?m methods subsample a subset of columns of the kernel matrix, and efficiently find an approximate KRR solution on the reconstructed Kt . The chosen subsampling distribution in turn affects the statistical and computational tradeoffs. For KRR problems, [15, 1] show that a sampling distribution proportional to the ridge leverage scores (RLSs) provides strong reconstruction guarantees for Kt. 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 Kt, 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 ?Kt?Kt?2 , and on the statistical risk of the approximate KRR solution at any time, because all our guarantees hold at any intermediate step. %Z Reissued by PMLR on 04 October 2026.
APA
Calandriello, D., Lazaric, A. & Valko, M.. (2016). Analysis of Nyström method with sequential ridge leverage scores. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:712-721 Available from https://proceedings.mlr.press/r14/calandriello16a.html. Reissued by PMLR on 04 October 2026.

Related Material