Nearly Optimal Algorithms with Sublinear Computational Complexity for
  Online Kernel Regression
Junfan Li Shizhong Liao
The trade-off between regret and computational cost is a fundamental problem
for online kernel regression, and previous algorithms worked on the trade-off
can not keep optimal regret bounds at a sublinear computational complexity. In
this paper, we propose two new algorithms, AOGD-ALD and NONS-ALD, which can
keep nearly optimal regret bounds at a sublinear computational complexity, and
give sufficient conditions under which our algorithms work. Both algorithms
dynamically maintain a group of nearly orthogonal basis used to approximate the
kernel mapping, and keep nearly optimal regret bounds by controlling the
approximate error. The number of basis depends on the approximate error and the
decay rate of eigenvalues of the kernel matrix. If the eigenvalues decay
exponentially, then AOGD-ALD and NONS-ALD separately achieves a regret of
$O(\sqrt{L(f)})$ and $O(\mathrm{d}_{\mathrm{eff}}(\mu)\ln{T})$ at a
computational complexity in $O(\ln^2{T})$. If the eigenvalues decay
polynomially with degree $p\geq 1$, then our algorithms keep the same regret
bounds at a computational complexity in $o(T)$ in the case of $p>4$ and $p\geq
10$, respectively. $L(f)$ is the cumulative losses of $f$ and
$\mathrm{d}_{\mathrm{eff}}(\mu)$ is the effective dimension of the problem. The
two regret bounds are nearly optimal and are not comparable.