NeurIPS 2018poster0 citations
Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
Enayat Ullah, Poorya Mianjy, Teodor Vanislavov Marinov, Raman Arora
Abstract
We study the statistical and computational aspects of kernel principal component analysis using random Fourier features and show that under mild assumptions, $O(\sqrt{n} \log n)$ features suffices to achieve $O(1/\epsilon^2)$ sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja's algorithm that achieves this rate
BibTeX
@inproceedings{NEURIPS2018_7ae11af2,
author = {Ullah, Enayat and Mianjy, Poorya and Marinov, Teodor Vanislavov and Arora, Raman},
booktitle = {Advances in Neural Information Processing Systems},
editor = {S. Bengio and H. Wallach and H. Larochelle and K. Grauman and N. Cesa-Bianchi and R. Garnett},
pages = {},
publisher = {Curran Associates, Inc.},
title = {Streaming Kernel PCA with \textbackslash tilde\lbrace O\rbrace (\textbackslash sqrt\lbrace n\rbrace ) Random Features},
url = {https://proceedings.neurips.cc/paper_files/paper/2018/file/7ae11af20803185120e83d3ce4fb4ed7-Paper.pdf},
volume = {31},
year = {2018}
}