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 es- timate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel ma- trix 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 es- timate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel ma- trix 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 es- timate of the RLSs. First, our sketch update does not require access to previously seen columns, and therefore a single pass over the kernel ma- trix 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