Non-stationary Online Regression
  Online forecasting under a changing environment has been a problem of
increasing importance in many real-world applications. In this paper, we
consider the meta-algorithm presented in \citet{zhang2017dynamic} combined with
different subroutines. We show that an expected cumulative error of order
$\tilde{O}(n^{1/3} C_n^{2/3})$ can be obtained for non-stationary online linear
regression where the total variation of parameter sequence is bounded by $C_n$.
Our paper extends the result of online forecasting of one-dimensional
time-series as proposed in \cite{baby2019online} to general $d$-dimensional
non-stationary linear regression. We improve the rate $O(\sqrt{n C_n})$
obtained by Zhang et al. 2017 and Besbes et al. 2015. We further extend our
analysis to non-stationary online kernel regression. Similar to the
non-stationary online regression case, we use the meta-procedure of Zhang et
al. 2017 combined with Kernel-AWV (Jezequel et al. 2020) to achieve an expected
cumulative controlled by the effective dimension of the RKHS and the total
variation of the sequence. To the best of our knowledge, this work is the first
extension of non-stationary online regression to non-stationary kernel
regression. Lastly, we evaluate our method empirically with several existing
benchmarks and also compare it with the theoretical bound obtained in this
paper.
