  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^\alpha$ 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((\log n)^{d+1})$ with per-round time complexity and space complexity
$O((\log n)^{2d})$. This makes the algorithm a suitable choice as soon as $n
\gg 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.
