Timezone: »

 
Poster
Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora

Thu Dec 06 07:45 AM -- 09:45 AM (PST) @ Room 517 AB #126
in Thu Poster Session A »
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
Keywords: Kernel Methods · Learning Theory
[ Paper]  [ Poster] 

Author Information

Enayat Ullah (Johns Hopkins University)
Poorya Mianjy (Johns Hopkins University)
Teodor Vanislavov Marinov (Johns Hopkins University)
Raman Arora (Johns Hopkins University)

More from the Same Authors