Online nonparametric regression with Sobolev kernels
This work provides theoretical regret bounds for online nonparametric regression, which is important for researchers working on online learning algorithms.
This paper investigates online kernelized ridge regression for d-dimensional adversarial nonparametric regression, deriving regret upper bounds for Sobolev spaces. It shows these rates are essentially optimal for specific conditions (β > d/2 or p=∞).
In this work we investigate the variation of the online kernelized ridge regression algorithm in the setting of $d-$dimensional adversarial nonparametric regression. We derive the regret upper bounds on the classes of Sobolev spaces $W_{p}^β(\mathcal{X})$, $p\geq 2, β>\frac{d}{p}$. The upper bounds are supported by the minimax regret analysis, which reveals that in the cases $β> \frac{d}{2}$ or $p=\infty$ these rates are (essentially) optimal. Finally, we compare the performance of the kernelized ridge regression forecaster to the known non-parametric forecasters in terms of the regret rates and their computational complexity as well as to the excess risk rates in the setting of statistical (i.i.d.) nonparametric regression.