NIPS Poster Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features

Poster

Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features

Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora

Room 517 AB #126

Keywords: [ Kernel Methods ] [ Learning Theory ]

[ Abstract ]

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

Live content is unavailable. Log in and register to view live content

Poster

Streaming Kernel PCA with ˜O(√n)\tilde{O}(\sqrt{n}) Random Features

Enayat Ullah · Poorya Mianjy · Teodor Vanislavov Marinov · Raman Arora

Room 517 AB #126

Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features