Our work contributes to the understanding of statistical properties of supervised learning problems. Most of the existing literature focuses on the case when the training data set is drawn from an i.i.d. sample, see the classical monographs [1]} and [2]}. However, many practical supervised learning problems (e.g. speech recognition, object tracking, market prediction, etc.) are characterized by temporal dependence and strong correlation between the marginals of the data-generating process, suggesting that the i.i.d. assumption is not always justified.
This problem has been first addressed in [3]}, [4]} and [5]} in the context of stationary \(\beta \) -mixing sequences, and in [6]} in the case of stationary \(m\) -dependent \(\alpha \) -mixing sequences. In [7]} the authors relax the stationarity assumption and require that the
data-generating process satisfies a certain law of large numbers only. This, for example, includes (not necessarily stationary) \(\alpha \) -mixing sequences and Markov chains satisfying the Doeblin condition. Recall that the Doeblin condition implies irreducibility, aperiodicity and uniform exponential ergodicity of the chain (see [8]}). The learning problem of the later model was further investigated in a series of articles [9]}, [10]}, [11]}, [12]} and [13]}.
We remark that a crucial step in all these works is the Hoeffding's inequality for uniformly ergodic Markov chains, obtained in [14]}.
Generalization of these results to irreducible aperiodic \(\mathcal {V}\) -ergodic Markov chains has been obtained in [13]}. Actually the proof of the main results of this article (Theorems 1 and 2) is taken from [5]}. We also remark that these results do not give generalization bounds in the full sense. Namely, a crucial assumption in the article is that the data-generating process starts from its invariant measure, which is unrealistic. A way to partly fix this gap is presented below.
