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 boundedfunction depending on \(s\) values of \(X\) . To approximate thisfunction we consider linear combinations of a finite set offeature functions with coefficients in an \(\ell_{1}\) -ball. Thecoefficients are constructed by the constrainedVovk–Azoury–Warmuth algorithm, introduced in the framework ofonline linear regression. Using the results of Agarwal and Duchi(2012) concerning the generalization properties of online learningalgorithms for dependent data, we prove that given \(n\) samples and \(m\) features, the estimation error for the quadratic loss isbounded by \(\widetilde{O}(m/n)\) in expectation. We also considerthe case of \(m\propto\sqrt{n}\) random Fourier features and obtainan estimation error \(\widetilde{O}(n^{-1/2})\) for a subset of anappropriate reproducing kernel Hilbert space. Finally, a vectorautoregression process is considered as an example.