Efficient online learning with kernels for adversarial large scale problems

arXiv1902.09917MaRDI QIDQ6314650

Author name not available (Why is that?)

Publication date: 26 February 2019

Abstract: We are interested in a framework of online learning with kernels for low-dimensional but large-scale and potentially adversarial datasets. We study the computational and theoretical performance of online variations of kernel Ridge regression. Despite its simplicity, the algorithm we study is the first to achieve the optimal regret for a wide range of kernels with a per-round complexity of order $n^{a}lpha$ with $alpha<2$. The algorithm we consider is based on approximating the kernel with the linear span of basis functions. Our contributions is two-fold: 1) For the Gaussian kernel, we propose to build the basis beforehand (independently of the data) through Taylor expansion. For $d$-dimensional inputs, we provide a (close to) optimal regret of order $O((logn{)}^{d+1})$ with per-round time complexity and space complexity $O((logn{)}^{2d})$. This makes the algorithm a suitable choice as soon as $ngg{e}^d$ which is likely to happen in a scenario with small dimensional and large-scale dataset; 2) For general kernels with low effective dimension, the basis functions are updated sequentially in a data-adaptive fashion by sampling Nystr{"o}m points. In this case, our algorithm improves the computational trade-off known for online kernel regression.

Has companion code repository: https://github.com/Remjez/kernel-online-learning

This page was built for publication: Efficient online learning with kernels for adversarial large scale problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6314650)