Streaming Kernel PCA with \tilde{O}(\sqrt{n}) Random Features
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
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Streaming Kernel PCA with $\tilde{O}(\sqrt{n})$ Random Features
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/\epsilo…
Differential Privacy in Kernelized Contextual Bandits via Random Projections
We consider the problem of contextual kernel bandits with stochastic contexts, where the underlying reward function belongs to a known Reproducing Kernel Hilbert Space. We study this problem under an additional constrain…
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound
Exploration in reinforcement learning (RL) suffers from the curse of dimensionality when the state-action space is large. A common practice is to parameterize the high-dimensional value and policy functions using given f…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Delayed Feedback in Kernel Bandits
Black box optimisation of an unknown function from expensive and noisy evaluations is a ubiquitous problem in machine learning, academic research and industrial production. An abstraction of the problem can be formulated…
Bayesian OptimisationRecommendation SystemsSpectral Guarantees for Adversarial Streaming PCA
In streaming PCA, we see a stream of vectors $x_1, \dotsc, x_n \in \mathbb{R}^d$ and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral ratio $R = \lambda_1 / \lambda_2$ is la…