Gain with no Pain: Efficiency of Kernel-PCA by Nyström Sampling

Nicholas Sterge, Bharath Sriperumbudur, Lorenzo Rosasco, Alessandro Rudi
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:3642-3652, 2020.

Abstract

In this paper, we analyze a Nyström based approach to efficient large scale kernel principal component analysis (PCA). The latter is a natural nonlinear extension of classical PCA based on considering a nonlinear feature map or the corresponding kernel. Like other kernel approaches, kernel PCA enjoys good mathematical and statistical properties but, numerically, it scales poorly with the sample size. Our analysis shows that Nyström sampling greatly improves computational efficiency without incurring any loss of statistical accuracy. While similar effects have been observed in supervised learning, this is the first such result for PCA. Our theoretical findings are based on a combination of analytic and concentration of measure techniques. Our study is more broadly motivated by the question of understanding the interplay between statistical and computational requirements for learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-sterge20a, title = {Gain with no Pain: Efficiency of Kernel-PCA by Nyström Sampling}, author = {Sterge, Nicholas and Sriperumbudur, Bharath and Rosasco, Lorenzo and Rudi, Alessandro}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {3642--3652}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/sterge20a/sterge20a.pdf}, url = {https://proceedings.mlr.press/v108/sterge20a.html}, abstract = { In this paper, we analyze a Nyström based approach to efficient large scale kernel principal component analysis (PCA). The latter is a natural nonlinear extension of classical PCA based on considering a nonlinear feature map or the corresponding kernel. Like other kernel approaches, kernel PCA enjoys good mathematical and statistical properties but, numerically, it scales poorly with the sample size. Our analysis shows that Nyström sampling greatly improves computational efficiency without incurring any loss of statistical accuracy. While similar effects have been observed in supervised learning, this is the first such result for PCA. Our theoretical findings are based on a combination of analytic and concentration of measure techniques. Our study is more broadly motivated by the question of understanding the interplay between statistical and computational requirements for learning.} }
Endnote
%0 Conference Paper %T Gain with no Pain: Efficiency of Kernel-PCA by Nyström Sampling %A Nicholas Sterge %A Bharath Sriperumbudur %A Lorenzo Rosasco %A Alessandro Rudi %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-sterge20a %I PMLR %P 3642--3652 %U https://proceedings.mlr.press/v108/sterge20a.html %V 108 %X In this paper, we analyze a Nyström based approach to efficient large scale kernel principal component analysis (PCA). The latter is a natural nonlinear extension of classical PCA based on considering a nonlinear feature map or the corresponding kernel. Like other kernel approaches, kernel PCA enjoys good mathematical and statistical properties but, numerically, it scales poorly with the sample size. Our analysis shows that Nyström sampling greatly improves computational efficiency without incurring any loss of statistical accuracy. While similar effects have been observed in supervised learning, this is the first such result for PCA. Our theoretical findings are based on a combination of analytic and concentration of measure techniques. Our study is more broadly motivated by the question of understanding the interplay between statistical and computational requirements for learning.
APA
Sterge, N., Sriperumbudur, B., Rosasco, L. & Rudi, A.. (2020). Gain with no Pain: Efficiency of Kernel-PCA by Nyström Sampling. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:3642-3652 Available from https://proceedings.mlr.press/v108/sterge20a.html.

Related Material