Vovk–Azoury–Warmuth Algorithm and Random Fourier Features for a Regression Problem with Markovian Data

Given a trajectory of a stationary $$\beta$$ -mixing Markov process $$X$$ , we estimate the conditional expectation of a fixed bounded function depending on $$s$$ values of $$X$$ . To approximate this function we consider linear combinations of a finite set of feature functions with coefficients in an $$\ell_{1}$$ -ball. The coefficients are constructed by the constrained Vovk–Azoury–Warmuth algorithm, introduced in the framework of online linear regression. Using the results of Agarwal and Duchi (2012) concerning the generalization properties of online learning algorithms for dependent data, we prove that given $$n$$ samples and $$m$$ features, the estimation error for the quadratic loss is bounded by $$\widetilde{O}(m/n)$$ in expectation. We also consider the case of $$m\propto\sqrt{n}$$ random Fourier features and obtain an estimation error $$\widetilde{O}(n^{-1/2})$$ for a subset of an appropriate reproducing kernel Hilbert space. Finally, a vector autoregression process is considered as an example.