# Generalization Error Bounds on Deep Learning with Markov Datasets

Lan V. Truong
Department of Engineering
University of Cambridge
Cambridge, CB2 1PZ
<EMAIL_ADDRESS>
Use footnote for providing further information about author (webpage,
alternative address)— _not_ for acknowledging funding agencies.

###### Abstract

In this paper, we derive upper bounds on generalization errors for deep neural
networks with Markov datasets. These bounds are developed based on
Koltchinskii and Panchenko’s approach for bounding the generalization error of
combined classifiers with i.i.d. datasets. The development of new
symmetrization inequalities in high-dimensional probability for Markov chains
is a key element in our extension, where the absolute spectral gap of the
infinitesimal generator of the Markov chain plays a key parameter in these
inequalities. We also propose a simple method to convert these bounds and
other similar ones in traditional deep learning and machine learning to
Bayesian counterparts for both i.i.d. and Markov datasets. Extensions to
$m$-order homogeneous Markov chains such as AR and ARMA models and mixtures of
several Markov data services are given.

##  1 Introduction

In statistical learning theory, understanding generalization for neural
networks is among the most challenging tasks. The standard approach to this
problem was developed by Vapnik [1], and it is based on bounding the
difference between the prediction error and the training error. These bounds
are expressed in terms of the so called VC-dimension of the class. However,
these bounds are very loose when the VC-dimension of the class can be very
large, or even infinite. In 1998, several authors [2, 3] suggested another
class of upper bounds on generalization error that are expressed in terms of
the empirical distribution of the margin of the predictor (the classifier).
Later, Koltchinskii and Panchenko [4] proposed new probabilistic upper bounds
on generalization error of the combination of many complex classifiers such as
deep neural networks. These bounds were developed based on the general results
of the theory of Gaussian, Rademacher, and empirical processes in terms of
general functions of the margins, satisfying a Lipschitz condition. They
improved previously known bounds on generalization error of convex combination
of classifiers.

In the context of supervised classification, PAC-Bayesian bounds have proved
to be the tightest [5, 6, 7]. Several recent works have focused on gradient
descent based PAC-Bayesian algorithms, aiming to minimise a generalisation
bound for stochastic classifiers [8, 9, 10]. Most of these studies use a
surrogate loss to avoid dealing with the zero-gradient of the
misclassification loss. Several authors used other methods to estimate of the
misclassification error with a non-zero gradient by proposing new training
algorithms to evaluate the optimal output distribution in PAC-Bayesian bounds
analytically [11, 12, 13]. Recently, there have been some interesting works
which use information-theoretic approach to find PAC-bounds on generalization
errors for machine learning [14, 15] and deep learning [16].

All of the above-mentioned bounds are derived based on the assumption that the
dataset is generated by an i.i.d. process with unknown distribution. However,
in many applications in machine learning such as speech, handwriting, gesture
recognition, and bio-informatics, the samples of data are usually correlated.
Some of these datasets are time-series ones with stationary distributions such
as samples via MCMC, finite-state random walks, or random walks on graph. In
this work, we develop some upper bounds on generalization errors for deep
neural networks with Markov or hidden Markov datasets. Our bounds are derived
based on the same approach as Koltchinskii and Panchenko [4]. To deal with the
Markov structure of the datasets, we need to develop some new techniques in
this work. The development of new symmetrization inequalities in high-
dimensional probability for Markov chains is a key element in our extension,
where the absolute spectral gap of the infinitesimal generator of the Markov
chain plays as a key parameter in these inequalities. Furthermore, we also
apply our results to $m$-order Markov chains such as AR and ARMA models and
mixtures of Markov chains. Finally, a simple method to convert all our bounds
for traditional deep learning to counterparts for Bayesian deep learning is
given. Our method can be applied to convert other similar bounds for i.i.d.
datasets in the research literature as well. Bayesian deep learning was
introduced by [17, 18]. The key distinguishable property of a Bayesian
approach is marginalization, rather than using a single setting of weights in
(traditional) deep learning [19].

Bayesian marginalization can particularly improve the accuracy and calibration
of modern deep neural networks, which are typically underspecified by the
data, and can represent many compelling but different solutions. Analysis of
machine learning algorithms for Markov and Hidden Markov datasets already
appeared in research literature [20, 21, 22]. In practice, some real-world
time-series datasets are not stationary Markov chains. However, we can
approximate time-series datasets by stationary Markov chains in many
applications. There are also some other methods of approximating non-
stationary Markov chains by stationary ones via MA and ARMA models in the
statistical research literature. The i.i.d. dataset is a special case of the
Markov dataset with stationary distribution.

##  2 Preliminaries

###  2.1 Mathematical Backgrounds

Let a Markov chain $\\{X_{n}\\}_{n=1}^{\infty}$ on a state space $\mathcal{S}$
with transition kernel $Q(x,dy)$ and the initial state $X_{1}\sim\nu$, where
$\mathcal{S}$ is a Polish space in $\mathbb{R}$. In this paper, we consider
the Markov chains which are irreducible and positive-recurrent, so the
existence of a stationary distribution $\pi$ is guaranteed. An irreducible and
recurrent Markov chain on an infinite state-space is called Harris chain [23].
A Markov chain is called _reversible_ if the following detailed balance
condition is satisfied:

$\displaystyle\pi(dx)Q(x,dy)=\pi(dy)Q(y,dx),\qquad\forall x,y\in\mathcal{S}.$
(1)

Define

$\displaystyle
d(t)=\sup_{x\in\mathcal{S}}d_{\rm{TV}}(Q^{t}(x,\cdot),\pi),\qquad
t_{\rm{mix}}(\varepsilon):=\min\\{t:d(t)\leq\varepsilon\\},$ (2)

and

$\displaystyle\tau_{\min}:=\inf_{0\leq\varepsilon\leq
1}t_{\rm{mix}}(\varepsilon)\bigg{(}\frac{2-\varepsilon}{1-\varepsilon}\bigg{)}^{2},\qquad
t_{\rm{mix}}:=t_{\rm{mix}}(1/4).$ (3)

Let $L_{2}(\pi)$ be the Hilbert space of complex valued measurable functions
on $\mathcal{S}$ that are square integrable w.r.t. $\pi$. We endow
$L_{2}(\pi)$ with inner product $\langle f,g\rangle:=\int fg^{*}d\pi$, and
norm $\|f\|_{2,\pi}:=\langle f,f\rangle_{\pi}^{1/2}$. Let $E_{\pi}$ be the
associated averaging operator defined by $(E_{\pi})(x,y)=\pi(y),\forall
x,y\in\mathcal{S}$, and

$\displaystyle\lambda=\|Q-E_{\pi}\|_{L_{2}(\pi)\to L_{2}(\pi)},$ (4)

where $\|B\|_{L_{2}(\pi)\to
L_{2}(\pi)}=\max_{v:\|v\|_{2,\pi}=1}\|Bv\|_{2,\pi}.$ $Q$ can be viewed as a
linear operator (infinitesimal generator) on $L_{2}(\pi)$, denoted by
$\mathbf{Q}$, defined as $(\mathbf{Q}f)(x):=\mathbb{E}_{Q(x,\cdot)}(f)$, and
the reversibility is equivalent to the self-adjointness of $\mathbf{Q}$. The
operator $\mathbf{Q}$ acts on measures on the left, creating a measure
$\mu\mathbf{Q}$, that is, for every measurable subset $A$ of $\mathcal{S}$,
$\mu\mathbf{Q}(A):=\int_{x\in\mathcal{S}}Q(x,A)\mu(dx)$. For a Markov chain
with stationary distribution $\pi$, we define the _spectrum_ of the chain as

$\displaystyle
S_{2}:=\big{\\{}\xi\in\mathbb{C}:(\xi\mathbf{I}-\mathbf{Q})\enspace\mbox{is
not invertible on}\enspace L_{2}(\pi)\big{\\}}.$ (5)

It is known that $\lambda=1-\gamma^{*}$ [24], where

$\displaystyle\gamma^{*}$
$\displaystyle:=\begin{cases}1-\sup\\{|\xi|:\xi\in\mathcal{S}_{2},\xi\neq
1\\},\\\ \qquad\qquad\mbox{if eigenvalue $1$ has multiplicity $1$,}\\\
0,\qquad\qquad\mbox{otherwise}\end{cases}$

is the _the absolute spectral gap_ of the Markov chain. The absolute spectral
gap can be bounded by the mixing time $t_{\rm{mix}}$ of the Markov chain by
the following expression:

$\displaystyle\bigg{(}\frac{1}{\gamma^{*}}-1\bigg{)}\log 2\leq
t_{\rm{mix}}\leq\frac{\log(4/\pi_{*})}{\gamma_{*}},$ (6)

where $\pi_{*}=\min_{x\in\mathcal{S}}\pi_{x}$ is the _minimum stationary
probability_ , which is positive if $Q^{k}>0$ (entry-wise positive) for some
$k\geq 1$. See [25] for more detailed discussions. In [26, 25], the authors
provided algorithms to estimate $t_{\rm{mix}}$ and $\gamma^{*}$ from a single
trajectory.

Define

$\displaystyle\mathcal{M}_{2}:=\bigg{\\{}\nu\in\mathcal{M}(\mathcal{S}):\bigg{\|}\frac{dv}{d\pi}\bigg{\|}_{2}<\infty\bigg{\\}},$
(7)

where $\|\cdot\|_{2}$ is the standard $L_{2}$ norm in the Hilbert space of
complex valued measurable functions on $\mathcal{S}$.

###  2.2 Problem settings

In this paper, we consider a uniformly bounded class of functions:
$\mathcal{F}:=\big{\\{}f:\mathcal{S}\to\mathbb{R}\big{\\}}$ such that
$\sup_{f\in\mathcal{F}}\big{\|}f\big{\|}_{\infty}\leq M$ for some finite
constant $M$.

Define the probability measure $P(A):=\int_{A}\pi(x)dx,$ for any measurable
set $A\in\mathcal{S}$. In addition, let $P_{n}$ be the empirical measure based
on the sample $(X_{1},X_{2},\cdots,X_{n})$, i.e.,
$P_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i}}.$ We also denote
$Pf:=\int_{S}fdP$ and $P_{n}f:=\int_{S}fdP_{n}$. Then, we have

$\displaystyle Pf=\int_{\mathcal{S}}f(x)\pi(x)dx\quad\mbox{and}\quad
P_{n}f=\frac{1}{n}\sum_{i=1}^{n}f(X_{i}).$ (8)

On the Banach space of uniformly bounded functions $\mathcal{F}$, define an
infinity norm: $\|Y\|_{\mathcal{F}}=\sup_{f\in\mathcal{F}}|Y(f)|.$ Let

$\displaystyle
G_{n}(\mathcal{F}):=\mathbb{E}\bigg{[}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}\bigg{]},$
(9)

where $\\{g_{i}\\}$ is a sequence of i.i.d. standard normal variables,
independent of $\\{X_{i}\\}$. We will call $n\mapsto G_{n}(\mathcal{F})$ _the
Gaussian complexity function_ of the class $\mathcal{F}$.

Similarly, we define

$\displaystyle
R_{n}(\mathcal{F}):=\mathbb{E}\bigg{[}\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}\bigg{]},$
(10)

and

$\displaystyle P_{n}^{0}:=n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}},$
(11)

where $\\{\varepsilon_{i}\\}$ is a sequence of i.i.d. Rademacher (taking
values $+1$ and $-1$ with probability $1/2$ each) random variables,
independent of $\\{X_{i}\\}$. We will call $n\mapsto R_{n}(\mathcal{F})$ _the
Rademacher complexity function_ of the class $\mathcal{F}$.

For times-series datasets in machine learning, we can assume that feature
vectors are generated by a Markov chain $\\{X_{n}\\}_{n=1}^{\infty}$ with
stochastic matrix $Q$, and $\\{Y_{n}\\}_{n=1}^{\infty}$ is the corresponding
sequence of labels. Furthermore, $Q$ is irreducible and recurrent on some
finite set $\mathcal{S}$. An i.i.d. sequence of feature vectors can be
considered as a special Markov chain where $Q(x,x^{\prime})$ only depends on
$x^{\prime}$. In the supervised learning, the sequence of labels
$\\{Y_{n}\\}_{n=1}^{\infty}$ can be considered as being generated by a Hidden
Markov Model (HMM), where the emission probability
$P_{Y_{n}|X_{n}}(y|x)=g(x,y)$ for all $n\geq 1$ and
$g:\mathcal{S}\times\mathcal{Y}\to\mathbb{R}_{+}$. It is easy to see that
$\\{(X_{n},Y_{n})\\}_{n=1}^{\infty}$ is a Markov chain with the transition
probability

$\displaystyle
P_{X_{n+1}Y_{n+1}|X_{n}Y_{n}}(x_{n+1},y_{n+1}|x_{n},y_{n})=Q(x_{n},x_{n+1})g(x_{n+1},y_{n+1}).$
(12)

Let $\tilde{Q}(x_{1},y_{1},x_{2},y_{2}):=Q(x_{1},x_{2})g(x_{2},y_{2})$ for all
$x_{1},x_{2}\in\mathcal{S}$ and $y_{1},y_{2}\in\mathcal{Y}$, which is the
transition probability of the Markov chain
$\\{(X_{n},Y_{n})\\}_{n=1}^{\infty}$ on
$\tilde{S}:=\mathcal{S}\times\mathcal{Y}$. Then, it is not hard to see that
$\\{(X_{n},Y_{n})\\}_{n=1}^{\infty}$ is irreducible and recurrent on
$\tilde{S}$, so it has a stationary distribution, say $\tilde{\pi}$. The
associated following probability measure is defined as

$\displaystyle P(A):=\int_{\mathcal{S}\times\mathcal{Y}}\tilde{\pi}(x,y)dxdy,$
(13)

and the empirical distribution $P_{n}$ based on the observations
$\\{(X_{k},Y_{k})\\}_{k=1}^{n}$ is

$\displaystyle P_{n}:=\frac{1}{n}\sum_{k=1}^{n}\delta_{X_{k},Y_{k}}.$ (14)

###  2.3 Contributions

In this paper, we aim to develop a set of novel upper bounds on _the
generalization errors_ for deep neural networks with Markov dataset. More
specially, our target is to find a relationship between $Pf$ and $P_{n}f$
which holds for all $f\in\mathcal{F}$ in terms of Gaussian and Rademacher
complexities. Our main contributions include:

  * •

We develop general bounds on generalization errors for machine learning (and
deep learning) on Markov datasets.

  * •

Since the dataset is non-i.i.d., the standard symmetrization inequalities in
high-dimensional probability can not be applied. In this work, we extend some
symmetrization inequalities for i.i.d. random processes to Markov ones.

  * •

We propose a new method to convert all the bounds for machine learning (and
deep learning) models to Bayesian settings.

  * •

Extensions to $m$-order homogeneous Markov chains such as AR and ARMA models
and mixtures of several Markov services are given.

##  3 Main Results

###  3.1 Probabilistic Bounds for General Function Classes

In this section, we develop probabilistic bounds for general function classes
in terms of Gaussian and Rademacher complexities.

First, we prove the following key lemma, which is an extension of the
symmetrization inequality for i.i.d. sequences (for example, [27]) to a new
version for Markov sequences $\\{X_{n}\\}_{n=1}^{\infty}$ with the stationary
distribution $\pi$ and the initial distribution $\nu\in\mathcal{M}_{2}$:

######  Lemma 1.

Let $\mathcal{F}$ be a class of functions which are uniformly bounded by $M$.
For all $n\in\mathbb{Z}^{+}$, define

$\displaystyle A_{n}$
$\displaystyle:=\sqrt{\frac{2M}{n(1-\lambda)}+\frac{64M^{2}}{n^{2}(1-\lambda)^{2}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}},$
(15) $\displaystyle\tilde{A}_{n}$
$\displaystyle:=\frac{M}{2n}\bigg{[}\sqrt{2\tau_{\min}n\log
n}+\sqrt{n}+4\bigg{]}.$ (16)

Then, the following holds:

$\displaystyle\frac{1}{2}\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}-\tilde{A}_{n}\leq\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{F}}\big{]}\leq
2\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}+A_{n},$ (17)

where

$\displaystyle\|P_{n}^{0}\|_{\mathcal{F}}:=\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\bigg{|}.$
(18)

The proof of this lemma can be found in Appendix A of the supplement material.
Compared with the i.i.d. case, the symmetrization inequality for Markov chain
in Lemma 1 are different in two perspectives: (1) The expectation
$\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}$ is now is under the
joint distributions of Markov chain and Rademacher random variables and (2)
The term $A_{n}$ appears in both lower and upper bounds to compensate for the
difference between the initial distribution $\nu$ and the stationary
distribution $\pi$ of the Markov chain111This difference causes a burn-in time
[28] which is the time between the initial and first time that the Markov
chain is stationary.. Later, we will see that $A_{n}$ represents the effects
of data structures on the generalization errors in deep learning.

By applying Lemma 1, the following theorem can be proved. See a detailed proof
in Appendix C in the supplement material.

######  Theorem 2.

Denote by

$\displaystyle
B_{n}:=\sqrt{\frac{2}{n(1-\lambda)}+\frac{64}{n^{2}(1-\lambda)^{2}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}},$
(19)

Let $\varphi$ be a non-increasing function such that
$\varphi(x)\geq\mathbf{1}_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$. For any
$t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2})$
(20)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{2L(\varphi)\sqrt{2\pi}}{\delta}G_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+\frac{2}{\sqrt{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}).$
(21)

Since $B_{n}=O\big{(}1/{\sqrt{n}}\big{)}$, Theorem 2 shows that with high
probability, the generalization error can be bounded by Rademacher or Gaussian
complexity functions plus an $O(1/\sqrt{n})$ term, where $n$ is the length of
the training set. This fact also happens in i.i.d. case [4]. However, because
the dependency among samples in Markov chain, the constant in $O(1/\sqrt{n})$
term is larger than the i.i.d. case.

It follows, in particular, in the example of the voting methods of combining
classifiers [2], from Theorem 2, we achieve the following PAC-bound:

$\displaystyle P\\{\tilde{f}\leq 0\\}$
$\displaystyle\leq\inf_{\delta\in(0,1]}\bigg{[}P_{n}\\{\tilde{f}\leq\delta\\}+\frac{8C}{\delta}\sqrt{\frac{V(\mathcal{H})}{n}}$
$\displaystyle\qquad\qquad+B_{n}+\bigg{(}\sqrt{\frac{1}{2}\log\frac{\pi^{2}}{3\alpha}}+\sqrt{\log\log_{2}2\delta^{-1}}\bigg{)}\sqrt{\frac{\tau_{\min}}{n}}\bigg{]}$
(22)

with probability at least $1-\alpha$ (PAC-Bayes bound), where $V(\mathcal{H})$
is the VC-dimension of the class $\mathcal{H}$ and $C$ is some positive
constant.

###  3.2 Bounding the generalization error in deep neural networks

In this section, we consider the same example as [4, Section 6]. However, we
assume that feature vectors in the dataset are generated by a Markov chain
instead of an i.i.d. process. Let $\mathcal{H}$ be a the class of all
uniformly bounded functions $f:\mathcal{S}\to\mathbb{R}$. $\mathcal{H}$ is
called the class of _base functions_.

Consider a feed-forward neural network with $l$ layers of neurons
$V=\\{v_{i}\\}\cup\bigcup_{j=0}^{l}V_{j}$ where $V_{l}=\\{v_{o}\\}$. The
neurons $v_{i}$ and $v_{o}$ are called the input and the output neurons,
respectively. To define the network, we will assign the labels to the neurons
in the following way. Each of the base neurons is labelled by a function from
the base class $\mathcal{H}$. Each neuron of the $j$-th layer $V_{j}$, where
$j\geq 1$, is labelled by a vector
$w:=(w_{1},w_{2},\cdots,w_{m})\in\mathbb{R}^{m}$, where $m$ is the number of
inputs of the neuron. Here, $w$ will be called the vector of weights of the
neuron.

Given a Borel function $\sigma$ from $\mathbb{R}$ into $[-1,1]$ (for example,
sigmoid function) and a vector
$w:=(w_{1},w_{2},\cdots,w_{m})\in\mathbb{R}^{m}$ where $m=|\mathcal{H}|+1$,
let

$\displaystyle
N_{\sigma,w}:\mathbb{R}^{m}\to\mathbb{R},N_{\sigma,w}(u_{1},u_{2},\cdots,u_{m}):=\sigma\bigg{(}\sum_{j=1}^{m}w_{j}u_{j}\bigg{)}.$
(23)

Let $\sigma_{j}:j\geq 1$ be functions from $\mathbb{R}$ into $[-1,1]$,
satisfying the Lipschitz conditions

$\displaystyle\big{|}\sigma_{j}(u)-\sigma_{j}(v)\big{|}\leq L_{j}|u-v|,\qquad
u,v\in\mathbb{R}.$ (24)

The neural network works can be formed as the following. The input neuron
inputs an instance $x\in\mathcal{S}$. A base neuron computes the value of the
base function on this instance and outputs the value through its output edges.
A neuron in the $j$-th layer ($j\geq 1$) computes and outputs through its
output edges the value $N_{\sigma_{j},w}(u_{1},u_{2},\cdots,u_{m})$ (where
$u_{1},u_{2},\cdots,u_{m}$ are the values of the inputs of the neuron). The
network outputs the value $f(x)$ (of a function $f$ it computes) through the
output edge.

We denote by $\mathcal{N}_{l}$ the set of such networks. We call
$\mathcal{N}_{l}$ the class of feed-forward neural networks with base
$\mathcal{H}$ and $l$ layers of neurons (and with sigmoid $\sigma_{j}$). Let
$\mathcal{N}_{\infty}:=\bigcup_{j=1}^{\infty}\mathcal{N}_{j}$. Define
$\mathcal{H}_{0}:=\mathcal{H}$, and then recursively

$\displaystyle\mathcal{H}_{j}$
$\displaystyle:=\bigg{\\{}N_{\sigma_{j},w}(h_{1},h_{2},\cdots,h_{m}):m\geq
0,h_{i}\in\mathcal{H}_{j-1},w\in\mathbb{R}^{m}\bigg{\\}}\cup\mathcal{H}_{j-1}.$
(25)

Denote $\mathcal{H}_{\infty}:=\bigcup_{j=1}^{\infty}\mathcal{H}_{j}$. Clearly,
$\mathcal{H}_{\infty}$ includes all the functions computable by feed-forward
neural networks with base $\mathcal{H}$.

Let $\\{b_{j}\\}$ be a sequence of positive numbers. We also define
recursively classes of functions computable by feed-forward neural networks
with restrictions on the weights of neurons:

$\displaystyle\mathcal{H}_{j}(b_{1},b_{2},\cdots,b_{j}):=\bigg{\\{}N_{\sigma_{j},w}(h_{1},h_{2},\cdots,h_{m}):m\geq
0,$ $\displaystyle\qquad\qquad
h_{i}\in\mathcal{H}_{j-1}(b_{1},b_{2},\cdots,b_{j-1}),w\in\mathbb{R}^{m},\|w\|_{1}\leq
b_{j}\bigg{\\}}\bigcup\mathcal{H}_{j-1}(b_{1},b_{2},\cdots,b_{j-1}),$ (26)

where $\|w\|_{1}$ denotes the $1$-norm of the vector $w$.

Clearly,

$\displaystyle\mathcal{H}_{\infty}=\bigcup\bigg{\\{}\mathcal{H}_{j}(b_{1},\cdots,b_{j}):b_{1},\cdots,b_{j}<+\infty\bigg{\\}}.$
(27)

Denote by $\tilde{\mathcal{H}}$ the class of measurable functions
$\tilde{f}:\mathcal{S}\times\mathcal{Y}\to\mathbb{R}$, where $\mathcal{Y}$ is
the alphabet of labels. $\tilde{\mathcal{H}}$ is introduced for real machine
learning applications where we need to work with a new Markov chain generated
from both feature vectors and their labels
$\\{(X_{n},Y_{n})\\}_{n=1}^{\infty}$ instead of the feature-based Markov chain
$\\{X_{n}\\}_{n=1}^{\infty}$. See Subsection 2.2 for detailed discussions. For
binary classification, $\tilde{\mathcal{H}}:=\\{\tilde{f}:f\in\mathcal{H}\\}$,
where $\tilde{f}(x,y)=yf(x)$. Let $\varphi$ be a function such that
$\varphi(x)\geq I_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$ and $\varphi$
satisfies the Lipschitz condition with constant $L(\varphi)$. Then, the
following is a direct application of Theorem 2.

######  Theorem 3.

For any $t\geq 0$ and for all $l\geq 1$,

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}(b_{1},b_{2},\cdots,b_{l}):P\\{\tilde{f}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\prod_{j=1}^{l}(2L_{j}b_{j}+1)G_{n}(\mathcal{H})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}),$
(28)

where $B_{n}$ is defined in (19).

######  Remark 4.

$P\\{\tilde{f}\leq 0\\}$ represents the probability of mis-classification in
the deep neural network.

###### Proof.

Let $\mathcal{H}_{l}^{\prime}:=\mathcal{H}(b_{1},b_{2},\cdots,b_{l}).$ As the
proof of [4, Theorem 13], it holds that

$\displaystyle G_{n}(\mathcal{H}_{l}^{\prime})$
$\displaystyle\leq\prod_{j=1}^{l}(2L_{j}b_{j}+1)G_{n}(\mathcal{H}).$ (29)

Hence, (28) is a direct application of Theorem 2 and (29). ∎

Now, given a neural network $f\in\mathcal{N}_{\infty}$, let

$\displaystyle l(f):=\min\\{j\geq 1:f\in\mathcal{N}_{j}\\}.$ (30)

For any number $k$ such that $1\leq k\leq l(f)$, let $V_{k}(f)$ be the set of
all neurons of layer $k$ in the neural network which is represented by $f$.
Denote by

$\displaystyle W_{k}(f):=\max_{u\in V_{k}(f)}\|w^{(u)}\|_{1}\vee b_{k},\qquad
k=1,2,\cdots,l(f)$ (31)

where $w^{(u)}$ is the coefficient-vector associated with the neuron $u$ in
this layer. Define

$\displaystyle\Lambda(f):=\prod_{k=1}^{l(f)}(4L_{k}W_{k}(f)+1),\qquad\Gamma_{\alpha}(f):=\sum_{k=1}^{l(f)}\sqrt{\frac{\alpha}{2}\log(2+\log_{2}W_{k}(f))},$
(32)

where $\alpha>0$ is the number such that $\zeta(\alpha)<3/2$, $\zeta$ being
the Riemann zeta-function: $\zeta(\alpha):=\sum_{k=1}^{\infty}k^{-\alpha}.$
Then, by using Theorem 3 with $b_{k}\to\infty$ and the same arguments as [4,
Proof of Theorem 14], we obtain the following result. See Section 1.3 in the
supplement material for more detailed derivations.

######  Theorem 5.

For any $t\geq 0$ and for all $l\geq 1$,

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}_{\infty}:P\\{\tilde{f}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\Lambda(f)G_{n}(\mathcal{H})+\frac{2}{\sqrt{n}}$
$\displaystyle\quad+\bigg{(}t+\Gamma_{\alpha}(f)+\sqrt{\log\log_{2}2\delta^{-1}}\bigg{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}(3-2\zeta(\alpha))^{-1}\exp\big{(}-2t^{2}\big{)},$
(33)

where $B_{n}$ is defined in (19).

###  3.3 Generalization Error Bounds on Bayesian Deep Learning

For Bayesian machine learning and deep learning,
$\mathcal{F}:=\big{\\{}f:\mathcal{S}\times\mathcal{W}\to\mathbb{R}\big{\\}}$,
where $\mathcal{S}$ is the state space of the Markov chain and $\mathcal{W}$
is the domain of (random) coefficients. We assume that $\mathcal{S}$ and
$\mathcal{W}$ are Polish spaces on $\mathbb{R}$, which include both discrete
sets and $\mathbb{R}$. For example, in binary classification,
$f(X,W)=\operatorname{sgn}(W^{T}X+b)$ where the feature $X$ and the
coefficient $W$ are random vectors with specific prior distributions. In
practice, the distribution of $W$ is known which depends on our design method,
and the distribution of $X$ is unknown. For example, $W$ is assumed to be
Gaussian in Bayesian deep neural networks [19].

Since all the bounds on Subsections 3.1 and 3.2 hold for any function $f$ in
$\mathcal{F}$ at each fixed vector $W=w$, hence, they can be directly applied
to Bayesian settings where $W$ is random. However, these bounds are not
expected to be tight enough since we don’t use the prior distribution of $W$
when deriving them. In the following, we use another approach to derive new
(and tighter) bounds for Bayesian deep learning and machine learning from all
the bounds in Subsections 3.1 and 3.2. For illustration purposes, we only
derive a new bound. Other bounds can be derived in a similar fashion. We
assume that $W_{1},W_{2},\cdots,W_{n}$ are i.i.d. random variables as in [19].

Let

$\displaystyle\tilde{P}_{n}:=\frac{1}{n}\sum_{i=1}^{n}\delta_{X_{i},W_{i}},$
(34)

and define a new probability measure $\tilde{P}$ on
$\mathcal{S}\times\mathcal{W}$ such that

$\displaystyle\tilde{P}(A):=\int_{A}\tilde{\pi}(x,w)dxdw,$ (35)

for all (Borel) set $A$ on $\mathcal{S}\times\mathcal{W}$. Here, $\tilde{\pi}$
is the stationary distribution of the irreducible Markov process
$\\{(X_{n},W_{n})\\}_{n=1}^{\infty}$ with stochastic matrix
$\tilde{Q}:=\\{Q(x,w)P_{W}(w)\\}_{x\in\mathcal{S},w\in\mathcal{W}}.$ In
addition, define two new (averaging) linear functionals:

$\displaystyle\hat{P}_{n}(f)=\frac{1}{n}\sum_{i=1}^{n}\int_{\mathcal{W}}f(X_{i},w)dP_{W}(w),$
(36)

and

$\displaystyle\hat{P}(f):=\int_{\mathcal{S}}\int_{\mathcal{W}}f(x,w)\tilde{\pi}(x,w)dP_{W}(w)dP(x).$
(37)

In practice, the prior distribution of $W$ is known, so we can estimate
$\hat{P}_{n}(f)$ based on the training set
$\\{(X_{1},Y_{1}),(X_{2},Y_{2}),\cdots,(X_{n},Y_{n})\\}$, which is a Markov
chain on $\mathcal{X}\times\mathcal{Y}$ (cf. Section 2.2). The following
result can be proved.

######  Theorem 6.

Let $\varphi$ be a sequence of function such that $\varphi(x)\geq
I_{(-\infty,0]}(x)$. For any $t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:\hat{P}\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}\hat{P}_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2})$
(38)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:\hat{P}\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}\hat{P}_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{2L(\varphi)\sqrt{2\pi}}{\delta}G_{n}(\mathcal{F})+\frac{2}{\sqrt{n}}$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp\big{(}-2t^{2}\big{)}.$
(39)

###### Proof.

Let $W_{1},W_{2},\cdots,W_{n}$ be an $n$ samples of $W\sim P_{W}$ on
$\mathcal{W}$ (or samples of some set of random coefficients). For simplicity,
we assume that $\\{W_{n}\\}_{n=1}^{\infty}$ is an i.i.d. sequence. Then, it is
obvious that $\\{(X_{n},W_{n})\\}_{n=1}^{\infty}$ forms a Markov chain with
probability transition probability

$\displaystyle\tilde{Q}(x_{n},w_{n};x_{n+1},w_{n+1})$
$\displaystyle=\mathbb{P}(X_{n+1}=x_{n+1},W_{n+1}=w_{n+1}|X_{n}=x_{n},W_{n}=w_{n})$
(40) $\displaystyle=Q(x_{n},x_{n+1})P_{W}(w_{n+1}).$ (41)

From Theorem 2, it holds that

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:\tilde{P}\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}\tilde{P}_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}).$
(42)

This means that with probability at least $1-\frac{\pi^{2}}{3}\exp(-2t^{2})$,
it holds that

$\displaystyle\tilde{P}\\{f\leq
0\\}\leq\inf_{\delta\in(0,1]}\bigg{[}\tilde{P}_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}.$
(43)

From (43), it holds that with probability at least
$1-\frac{\pi^{2}}{3}\exp(-2t^{2})$,

$\displaystyle\tilde{P}\\{f\leq 0\\}$
$\displaystyle\leq\inf_{\delta\in(0,1]}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\varphi\bigg{(}\frac{f(X_{i},W_{i})}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}.$
(44)

From (44), with probability at least $1-\frac{\pi^{2}}{3}\exp(-2t^{2})$, it
holds that

$\displaystyle\mathbb{E}_{W}\big{[}\tilde{P}\\{f\leq
0\\}\big{]}\leq\mathbb{E}_{W}\bigg{[}\inf_{\delta\in(0,1]}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\varphi\bigg{(}\frac{f(X_{i},W_{i})}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}$
(45)
$\displaystyle\leq\inf_{\delta\in(0,1]}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}_{W}\bigg{[}\varphi\bigg{(}\frac{f(X_{i},W)}{\delta}\bigg{)}\bigg{]}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}.$
(46)

From (46), we obtain (38). Similarly, we can achieve (39). ∎

##  4 Extension to High-Order Markov Chains

In this subsection, we extend our results in previous sections to $m$-order
homogeneous Markov chain. The main idea is to convert $m$-order homogeneous
Markov chains to $1$-order homogeneous Markov chain and use our results in
previous sections to bound the generalization error. We start with the
following simple example.

######  Example 7.

[$m$-order moving average process without noise] Consider the following
$m$-order Markov chain

$\displaystyle X_{k}=\sum_{i=1}^{m}a_{i}X_{k-i},\qquad k\in\mathbb{Z}_{+}.$
(47)

Let $Y_{k}:=[X_{k+m-1},X_{k+m-2},\cdots,X_{k}]^{T}$. Then, from (119), we
obtain $Y_{k+1}=\mathbf{G}Y_{k},\enspace\forall k\in\mathbb{Z}_{+}$ where

$\displaystyle\mathbf{G}:=\begin{pmatrix}a_{1}&a_{2}&\cdots&a_{m-1}&a_{m}\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}.$ (48)

It is clear that $\\{\mathbf{Y}_{n}\\}_{n=1}^{\infty}$ is an order-$1$ Markov
chain. Hence, instead of directly working with the $m$-order Markov chain
$\\{\mathbf{X}_{n}\\}_{n=1}^{\infty}$, we can find an upper bound for the
Markov chain $\\{Y_{n}\\}_{n=1}^{\infty}$.

To derive generalization error bounds for the Markov chain
$\\{Y_{n}\\}_{n=1}^{\infty}$, we can use the following arguments. For all
$f\in\mathcal{F}$ and $(x_{k},x_{k+1},\cdots,x_{k+m-1})$, by setting
$\tilde{f}(x_{k},x_{k+1},\cdots,x_{k+m-1})=f(x_{k})$ where
$\tilde{f}:\mathcal{S}^{m}\to\mathbb{R}$, we obtain

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{f(X_{i})\leq 0\\}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{\tilde{f}(Y_{i})\leq
0\\}.$ (49)

Hence, by applying all the results for $1$-order Markov chain
$\\{Y_{n}\\}_{n=1}^{\infty}$, we obtain corresponding upper bounds for the
sequence of $m$-order Markov chain $\\{X_{n}\\}_{n=1}^{\infty}$.

This approach can be extended to more general Markov chain. See Section 4 in
the Supplementary Material for details.

##  5 Conclusions

In this paper, we derive upper bounds on generalization errors for machine
learning and deep neural networks based on a new assumption that the dataset
has Markov or hidden Markov structure. We also propose a new method to convert
all these bounds to Bayesian deep learning and machine learning. Extension to
$m$-order Markov chains and a mixture of Markov chains are also given. An
interesting future research topic is to develop some new algorithms to
evaluate performance of these bounds on real Markov datasets.

## References

  * Vapnik [1998] V. N. Vapnik.  _Statistical Learning Theory_.  Wiley, New York, 1998.
  * Bartlett et al. [1998] Peter Bartlett, Yoav Freund, Wee Sun Lee, and Robert E. Schapire.  Boosting the margin: a new explanation for the effectiveness of voting methods.  _The Annals of Statistics_ , 26(5):1651 – 1686, 1998.
  * Bartlett and Shawe-Taylor [1999] Peter Bartlett and John Shawe-Taylor.  _Generalization Performance of Support Vector Machines and Other Pattern Classifiers_ , page 43–54.  MIT Press, 1999.
  * Koltchinskii and Panchenko [2002] V. Koltchinskii and D. Panchenko.  Empirical Margin Distributions and Bounding the Generalization Error of Combined Classifiers.  _The Annals of Statistics_ , 30(1):1 – 50, 2002\.
  * Langford and Shawe-Taylor [2003] J. Langford and J. Shawe-Taylor.  PAC-Bayes and Margins.  In _Advances of Neural Information Processing Systems (NIPS)_ , 2003\.
  * McAllester [2004] D. A. McAllester.  Pac-bayesian stochastic model selection.  _Machine Learning_ , 51, 2004.
  * A. Ambroladze and ShaweTaylor [2007] E. Parrado-Hern”andez A. Ambroladze and J. ShaweTaylor.  Tighter PAC-Bayes bounds.  In _NIPS_ , 2007.
  * Dziugaite and Roy. [2017] G. K. Dziugaite and D. M. Roy.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  In _Uncertainty in Artificial Intelligence (UAI)_ , 2017.
  * W. Zhou and Orbanz. [2019] M. Austern R. P. Adams W. Zhou, V. Veitch and P. Orbanz.  Non-vacuous generalization bounds at the imagenet scale: a PAC-Bayesian compression approach.  In _The International Conference on Learning Representations (ICLR)_ , 2019.
  * Biggs and Guedj [2021] F. Biggs and B. Guedj.  Differentiable PAC-Bayes objectives with partially aggregated neural networks.  _Entropy_ , 23, 2021.
  * McAllester [1998] A. McAllester.  Some PAC-Bayesian theorems.  In _Conference on Learning Theory (COLT)_ , 1998.
  * Clerico et al. [2021a] Eugenio Clerico, George Deligiannidis, and Arnaud Doucet.  Wide stochastic networks: Gaussian limit and PACBayesian training.  _Arxiv: 2106.09798_ , 2021a.
  * Clerico et al. [2021b] Eugenio Clerico, George Deligiannidis, and Arnaud Doucet.  Conditional Gaussian PAC-Bayes.  _Arxiv: 2110.1188_ , 2021b.
  * Xu and Raginsky [2017] A. Xu and M. Raginsky.  Information-theoretic analysis of generalization capability of learning algorithms.  In _Advances of Neural Information Processing Systems (NIPS)_ , 2017\.
  * Esposito et al. [2021] Amedeo Roberto Esposito, Michael Gastpar, and Ibrahim Issa.  Generalization error bounds via Rényi-f-divergences and maximal leakage.  _IEEE Transactions on Information Theory_ , 67(8):4986–5004, 2021.
  * Jakubovitz et al. [2018] D. Jakubovitz, R. Giryes, and M. R. D. Rodrigues.  Generalization Error in Deep Learning.  _Arxiv: 1808.01174_ , 30, 2018.
  * MacKay [1992] David J.C. MacKay.  _Bayesian methods for adaptive models_.  PhD thesis, California Institute of Technology, United States, 1992.
  * Mackay [1995] David J. C. Mackay.  Probable networks and plausible predictions - a review of practical bayesian methods for supervised neural networks.  _Network: Computation In Neural Systems_ , 6:469–505, 1995\.
  * Wilson and Izmailov [2020] A. G. Wilson and P. Izmailov.  Bayesian deep learning and a probabilistic perspective of model construction.  In _Proc. 37th ICML_. Morgan Kaufmann, 2020.
  * Duchi et al. [2011] John C. Duchi, Alekh Agarwal, Mikael Johansson, and Michael I. Jordan.  Ergodic mirror descent.  _2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 701–706, 2011.
  * Wang et al. [2019] Gang Wang, Bingcong Li, and Georgios B. Giannakis.  A multistep lyapunov approach for finite-time analysis of biased stochastic approximation.  _ArXiv_ , abs/1909.04299, 2019.
  * Truong [2022a] Lan V. Truong.  On linear model with markov signal priors.  In _AISTATS_ , 2022a.
  * Tuominen and Tweedie [1979] Pekka Tuominen and Richard L. Tweedie.  Markov Chains with Continuous Components.  _Proceedings of the London Mathematical Society_ , s3-38(1):89–114, 01 1979.
  * Paulin [2015] Daniel Paulin.  Concentration inequalities for Markov chains by Marton couplings and spectral methods.  _Electronic Journal of Probability_ , 20(79):1 – 32, 2015.
  * Wolfer and Kontorovich [2019] G. Wolfer and A. Kontorovich.  Estimating the mixing time of ergodic markov chains.  In _32nd Annual Conference on Learning Theory_ , 2019.
  * Combes and Touati [2019] R. Combes and M. Touati.  Computationally efficient estimation of the spectral gap of a markov chain.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 3:1 – 21, 2019.
  * Van Der Vaart and Wellner [1996a] A. W. Van Der Vaart and Wellner.  _Weak convergence and Empirical Processes._ Springer, New York, 1996a.
  * Rudolf [2011] D. Rudolf.  Explicit error bounds for Markov chain Monte Carlo.  _Arxiv: 1108.3201_ , 2011.
  * Lezaud [2001] Pascal Lezaud.  Chernoff and Berry-Esséen inequalities for Markov processes.  _ESAIM: Probability and Statistics, EDP Sciences_ , 5:183–201, 2001.
  * Ledoux and Talagrand [1991] M. Ledoux and M. Talagrand.  _Probability in Banach Spaces_.  Springer, New York., 1991.
  * Truong [2022b] Lan V. Truong.  On rademacher complexity-based generalization bounds for deep learning.  _ArXiv_ , abs/2208.04284, 2022b.
  * Van Der Vaart and Wellner [1996b] A. W. Van Der Vaart and J. A. Wellner.  _Weak convergence and Empirical Processes._ Springer, New York., 1996b.
  * Billingsley [1995] P. Billingsley.  _Probability and Measure_.  Wiley-Interscience, 3rd edition, 1995.
  * Kontoyiannis et al. [2005] I. Kontoyiannis, L. A. Lastras-Montaño, and S. P. Meyn.  Relative entropy and exponential deviation bounds for general Markov chains.  In _Proc. of Intl. Symp. on Inform. Th._ , 2005.

##  6 Supplemental Materials

###  6.1 Probabilistic Bounds for General Function Classes

In this section, we develop probabilistic bounds for general function classes
in terms of Gaussian and Rademacher complexities. First, we prove the
following key lemma, which is an extension of the symmetrization inequality
for i.i.d. sequences (for example, [27]) to a new version for Markov sequences
$\\{X_{n}\\}_{n=1}^{\infty}$ with the stationary distribution $\pi$ and the
initial distribution $\nu\in\mathcal{M}_{2}$:

######  Lemma 8.

Let $\mathcal{F}$ be a class of functions which are uniformly bounded by $M$.
For all $n\in\mathbb{Z}^{+}$, define

$\displaystyle A_{n}$
$\displaystyle:=\sqrt{\frac{2M}{n(1-\lambda)}+\frac{64M^{2}}{n^{2}(1-\lambda)^{2}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}},$
(50) $\displaystyle\tilde{A}_{n}$
$\displaystyle:=\frac{M}{2n}\bigg{[}\sqrt{2\tau_{\min}n\log
n}+\sqrt{n}+4\bigg{]}.$ (51)

Then, the following holds:

$\displaystyle\frac{1}{2}\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}-\tilde{A}_{n}\leq\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{F}}\big{]}\leq
2\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}+A_{n},$ (52)

where

$\displaystyle\|P_{n}^{0}\|_{\mathcal{F}}:=\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\bigg{|}.$
(53)

###### Proof.

See Appendix A. ∎

Next, we prove the following theorem.

######  Theorem 9.

Consider a countable family of Lipschitz function $\Phi=\\{\varphi_{k}:k\geq
1\\}$, where $\varphi_{k}:\mathbb{R}\to\mathbb{R}$ satisfies
$\mathbf{1}_{(-\infty,0]}(x)\leq\varphi_{k}(x)$ for all $k$. For each
$\varphi\in\Phi$, denote by $L(\varphi)$ its Lipschitz constant. Define

$\displaystyle
B_{n}:=\sqrt{\frac{2}{n(1-\lambda)}+\frac{64}{n^{2}(1-\lambda)^{2}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}}.$
(54)

Then, for any $t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{k>0}\bigg{[}P_{n}\varphi_{k}(f)+4L(\varphi_{k})R_{n}(\mathcal{F})+\big{(}t+\sqrt{\log
k}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}$
$\displaystyle\quad\leq\frac{\pi^{2}}{3}\exp(-2t^{2})$ (55)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{k>0}\bigg{[}P_{n}\varphi_{k}(f)+\sqrt{2\pi}L(\varphi_{k})G_{n}(\mathcal{F})$
$\displaystyle\qquad\qquad\qquad+\frac{2}{\sqrt{n}}+\big{(}t+\sqrt{\log
k}\big{)}\sqrt{\frac{\tau_{\min}}{n}}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}).$
(56)

###### Proof.

See Appendix B. ∎

######  Theorem 10.

Let $\varphi$ is a non-increasing function such that
$\varphi(x)\geq\mathbf{1}_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$. For any
$t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}$
$\displaystyle\qquad\qquad\leq\frac{\pi^{2}}{3}\exp(-2t^{2})$ (57)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{2L(\varphi)\sqrt{2\pi}}{\delta}G_{n}(\mathcal{F})$
$\displaystyle\qquad\qquad+\frac{2}{\sqrt{n}}+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}),$
(58)

where $B_{n}$ is defined in (54).

###### Proof.

See Appendix C. ∎

In the next statements, we use Rademacher complexities, but Gaussian
complexities can be used similarly. Now, assume that $\varphi$ is a function
from $\mathbb{R}$ to $\mathbb{R}$ such that $\varphi(x)\leq
I_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$ and $\varphi$ satisfies the
Lipschitz with constant $L(\varphi)$. Then, the following theorems can be
proved by using similar arguments as the proof of Theorem 10.

######  Theorem 11.

Let $\varphi$ is a nonincreasing function such that
$\varphi(x)\leq\mathbf{1}_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$. For any
$t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}<\sup_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{F})$
$\displaystyle\qquad\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2})$
(59)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}<\sup_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}G_{n}(\mathcal{F})+\frac{2}{\sqrt{n}}\bigg{]}\bigg{)}$
$\displaystyle\qquad\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}),$
(60)

where $B_{n}$ is defined in (54).

By combining Theorem 10 and Theorem 11, we obtain the following result.

######  Theorem 12.

Let

$\displaystyle\Delta_{n}(\mathcal{F};\delta)$
$\displaystyle:=\frac{8}{\delta}R_{n}(\mathcal{F})+\sqrt{\frac{\tau_{\min}\log\log_{2}2\delta^{-1}}{n}}+B_{n}.$
(61)

Then, for all $t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:\big{|}P_{n}\\{f\leq
0\\}-P\\{f\leq
0\\}\big{|}>\inf_{\delta\in(0,1]}\bigg{(}P_{n}\\{|f|\leq\delta\\}+\Delta_{n}(\mathcal{F};\delta)+t\sqrt{\frac{\tau_{\min}}{n}}\bigg{)}\bigg{)}$
$\displaystyle\qquad\qquad\leq\frac{2\pi^{2}}{3}\exp(-2t^{2})$ (62)

and

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:\big{|}P_{n}\\{f\leq
0\\}-P\\{f\leq
0\\}\big{|}>\inf_{\delta\in(0,1]}\bigg{(}P\\{|f|\leq\delta\\}+\Delta_{n}(\mathcal{F};\delta)+t\sqrt{\frac{\tau_{\min}}{n}}\bigg{)}$
$\displaystyle\qquad\qquad\leq\frac{2\pi^{2}}{3}\exp(-2t^{2}).$ (63)

###### Proof.

Equation (62) is drawn by setting $\varphi(x)=\mathbf{1}\\{x\leq
0\\}+(1-x)\mathbf{1}\\{0\leq x\leq 1\\}$ in Theorem 10 and Theorem 11.
Equation (63) is drawn by setting
$\varphi(x)=\mathbf{1}\\{x\leq-1\\}-x\mathbf{1}\\{-1\leq x\leq 0\\}$ in these
theorems. ∎

###  6.2 Conditions on Random Entropies and $\gamma$-Margins

As [4], given a metric space $(T,d)$, we denote by $H_{d}(T;\varepsilon)$ the
$\varepsilon$-entropy of $T$ with respect to $d$, that is

$\displaystyle H_{d}(T;\varepsilon):=\log N_{d}(T;\varepsilon),$ (64)

where $N_{d}(T;\varepsilon)$ is the minimal number of balls of radius
$\varepsilon$ covering $T$. Let $d_{P_{n},2}$ denote the metric of the space
$L_{2}(\mathcal{S};dP_{n})$:

$\displaystyle d_{P_{n},2}(f,g):=\big{(}P_{n}|f-g|^{2}\big{)}^{1/2}.$ (65)

For each $\gamma\in(0,1]$, define

$\displaystyle\delta_{n}(\gamma;f):=\sup\bigg{\\{}\delta\in(0,1):\delta^{\frac{\gamma}{2}}P(f\leq\delta)\leq
n^{-\frac{1}{2}+\frac{\gamma}{4}}\bigg{\\}}$ (66)

and

$\displaystyle\hat{\delta}_{n}(\gamma;f):=\sup\bigg{\\{}\delta\in(0,1):\delta^{\frac{\gamma}{2}}P_{n}(f\leq\delta)\leq
n^{-\frac{1}{2}+\frac{\gamma}{4}}\bigg{\\}}.$ (67)

We call $\delta_{n}(\gamma;f)$ and $\hat{\delta}_{n}(\gamma;f)$, respectively,
the _$\gamma$ -margin_ and _empirical $\gamma$-margin_ of $f$.

######  Theorem 13.

Suppose that for some $\alpha\in(0,2)$ and some constant $D>0$,

$\displaystyle H_{d_{P_{n}},2}(\mathcal{F};u)\leq Du^{-\alpha},\qquad
u>0\qquad a.s.,$ (68)

Then, for any $\gamma\geq\frac{2\alpha}{2+\alpha}$, there exists some
constants $\zeta,\upsilon>0$ such that when $n$ is large enough,

$\displaystyle\mathbb{P}\bigg{[}\forall
f\in\mathcal{F}:\zeta^{-1}\hat{\delta}_{n}(\gamma;f)\leq\delta_{n}(\gamma;f)\leq\zeta\hat{\delta}_{n}(\gamma;f)\bigg{]}\geq
1-2\upsilon\big{(}\log_{2}\log_{2}n\big{)}\exp\big{\\{}-n^{\frac{\gamma}{2}}/2\big{\\}}.$
(69)

###### Proof.

See Appendix D for a detailed proof. ∎

###  6.3 Convergence rates of empirical margin distributions

First, we prove the following lemmas.

######  Lemma 14.

For any class $\mathcal{F}$ of bounded measurable functions from
$\mathcal{S}\to\mathbb{R}$, with probability at least
$1-2\exp\big{(}-2t^{2}\big{)}$, the following holds:

$\displaystyle\sup_{f\in\mathcal{F}}\sup_{y\in\mathbb{R}}\big{|}P_{n}(f\leq
y)-P(f\leq y)\big{|}\leq\sqrt{B_{n}}+t\sqrt{\frac{\tau_{\min}}{n}},$ (70)

where $B_{n}$ is defined in (54).

######  Remark 15.

By setting $t=\sqrt{2\log n}$, (70) shows that
$\sup_{f\in\mathcal{F}}\sup_{y\in\mathbb{R}}\big{|}P_{n}(f\leq y)-P(f\leq
y)\big{|}\to 0$ as $n\to\infty$.

###### Proof.

See Appendix E. ∎

Now, for each $f\in\mathcal{F}$, define

$\displaystyle F_{f}(y):=P\\{f\leq y\\},\qquad F_{n,f}:=P_{n}\\{f\leq
y\\},\qquad y\in\mathbb{R}.$ (71)

Let $L$ denote the Lévy distance between the distributions in $\mathbb{R}$:

$\displaystyle L(F,G):=\inf\\{\delta>0:F(t)\leq G(t+\delta)+\delta,\qquad
G(t)\leq F(t+\delta)+\delta,\qquad\forall t\in\mathbb{R}\\}.$ (72)

######  Lemma 16.

Let $M>0$ and $\mathcal{F}$ be a class of measurable functions from
$\mathcal{S}$ into $[-M,M]$. Let $\varphi$ be equal to $1$ for $x\leq 0$, $0$
for $x\geq 1$ and linear between them. Define

$\displaystyle\tilde{\mathcal{G}}_{\varphi}:=\bigg{\\{}\varphi\circ\bigg{(}\frac{f-y}{\delta}\bigg{)}-1:f\in\mathcal{F},\quad
y\in[-M,M]\bigg{\\}}$ (73)

for some $\delta>0$. Recall the definition of $B_{n}$ in (54). Then, for all
$t>0$ and $\delta>0$, the following holds:

$\displaystyle\mathbb{P}\bigg{\\{}\sup_{f\in\mathcal{F}}L(F_{f},F_{f,n})\geq\delta+\mathbb{E}\big{[}\|P_{n}^{0}\|_{\tilde{\mathcal{G}}_{\varphi}}\big{]}+B_{n}+t\sqrt{\frac{\tau_{\min}}{n}}\bigg{\\}}\leq
2\exp(-2t^{2}).$ (74)

Especially, for all $t>0$, we have

$\displaystyle\mathbb{P}\bigg{\\{}\sup_{f\in\mathcal{F}}L(F_{f},F_{f,n})\geq
4\sqrt{\mathbb{E}[\|P_{n}^{0}\|_{\mathcal{F}}]+M/\sqrt{n}}+B_{n}+t\sqrt{\frac{\tau_{\min}}{n}}\bigg{\\}}\leq
2\exp(-2t^{2}).$ (75)

###### Proof.

See Appendix F. ∎

In what follows, for a function $f$ from $\mathcal{S}$ into $\mathbb{R}$ and
$M>0$, we denote by $f_{M}$ the function that is equal to $f$ if $|f|\leq M$,
is equal to $M$ if $f>M$ and is equal to $-M$ if $f<-M$. We set

$\displaystyle\mathcal{F}_{M}:=\big{\\{}f_{M}:f\in\mathcal{F}\\}.$ (76)

As always, a function $\mathcal{F}$ from $\mathcal{S}$ into $[0,\infty)$ is
called an envelope of $\mathcal{F}$ iff $|f(x)|\leq F(x)$ for all
$f\in\mathcal{F}$ and all $x\in\mathcal{S}$.

We write $\mathcal{F}\in\rm{GC}(P)$ iff $\mathcal{F}$ is a Glivenko-Cantelli
class with respect to $P$ (i.e., $\|P_{n}-P\|_{\mathcal{F}}\to 0$ as
$n\to\infty$ a.s.). We write $\mathcal{F}\in\rm{BCLT}(P)$ and say that
$\mathcal{F}$ satisfies the Bounded Central Limit Theorem for $P$ iff

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{F}}\big{]}=O(n^{-1/2}).$
(77)

Based on Lemma and Lemma 16, we prove the following theorems.

######  Theorem 17.

Suppose that

$\displaystyle\sup_{f\in\mathcal{F}}P\\{|f|\geq M\\}\to 0\qquad\mbox{as}\qquad
M\to\infty.$ (78)

Then, the following two statements are equivalent:

  * •

(i) $\mathcal{F}_{M}\in\rm{GC}(P)$ for all $M>0$
and

  * •

(ii) $\sup_{f\in\mathcal{F}}L(F_{n,f},F_{f})\to 0$ a.s. $n\to\infty$.

###### Proof.

See Appendix G. ∎

Next, the following theorems hold.

######  Theorem 18.

[4, Theorem 7] The following two statements are equivalent:

  * •

(i) $\mathcal{F}\in\rm{GC}(P)$ for all $M>0$
and

  * •

(ii) there exists a $P$-integrable envelope for the class
$\mathcal{F}^{(c)}=\\{f-Pf:f\in\mathcal{F}\\}$ and
$\sup_{f\in\mathcal{F}}L(F_{n,f},F_{f})\to 0$ $n\to\infty$ and

$\displaystyle\sup_{f\in\mathcal{F}}L(F_{n,f},F_{f})\to 0\qquad a.s.\qquad
n\to\infty.$ (79)

Now, we prove the following theorem.

######  Theorem 19.

Suppose that the class $\mathcal{F}$ is uniformly bounded. If
$\mathcal{F}\in\rm{BCLT}(P)$, then

$\displaystyle\sup_{f\in\mathcal{F}}L(F_{n,f},F_{f})=O_{P}\bigg{(}\bigg{(}\frac{\log
n}{n}\bigg{)}^{1/4}\bigg{)}\qquad n\to\infty.$ (80)

Moreover, for some $\alpha\in(0,2)$ and for some $D>0$

$\displaystyle H_{d_{P_{n},2}}(\mathcal{F};u)\leq Du^{-\alpha}\log n,\qquad
u>0,\qquad a.s.,$ (81)

then

$\displaystyle\sup_{f\in\mathcal{F}}L(F_{n,f},F_{f})=O\big{(}n^{-\frac{1}{2+\alpha}}\log
n\big{)}\qquad n\to\infty,\qquad a.s.,$ (82)

###### Proof.

Appendix H. ∎

###  6.4 Bounding the generalization error of convex combinations of
classifiers

We start with an application of the inequalities in Subsection 6.1 to bounding
the generalization error in general classification problems. Assume that the
labels take values in a finite set $\mathcal{Y}$ with $|\mathcal{Y}|=K$.
Consider a class $\tilde{\mathcal{F}}$ of functions from
$\mathcal{S}\times\mathcal{Y}$ into $\mathbb{R}$. A function
$f\in\tilde{\mathcal{F}}$ predicts a label $y\in\mathcal{Y}$ for an example
$x\in\mathcal{S}$ iff

$\displaystyle f(x,y)>\max_{y^{\prime}\neq y}f(x,y^{\prime}).$ (83)

In practice, $f(x,y)$ can be set equal to $P(y|x)$, so $\mathcal{F}$ can be
assumed to be uniformly bounded. The margin of a labelled example $(x,y)$ is
defined as

$\displaystyle m_{f,y}(x):=f(x,y)-\max_{y^{\prime}\neq y}f(x,y^{\prime}),$
(84)

so $f$ mis-classifies the label example $(x,y)$ if and only if $m_{f,y}\leq
0$. Let

$\displaystyle\mathcal{F}:=\big{\\{}f(\cdot,y):y\in\mathcal{Y},f\in\tilde{\mathcal{F}}\big{\\}}.$
(85)

Then, we can show the following theorem.

######  Theorem 20.

For all $t>0$, it holds that

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{m_{f,y}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\\{m_{f,y}\leq\delta\\}+\frac{8}{\delta}(2K-1)R_{n}(\mathcal{F})$
$\displaystyle\qquad\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}),$
(86)

where $B_{n}$ is defined in (54). Here,

$\displaystyle P\\{m_{f,y}\leq
0\\}:=\sum_{x\in\mathcal{S}}\pi(x)\mathbf{1}\\{m_{f,y}(x)\leq 0\\},$ (87)

and

$\displaystyle
P_{n}\\{m_{f,y}\leq\delta\\}=\frac{1}{n}\sum_{k=1}^{n}\mathbf{1}\\{m_{f,y}(X_{k})\leq\delta\\}$
(88)

is the empirical distribution of the Markov process
$\\{m_{f,y}(X_{n})\\}_{n=1}^{\infty}$ given $f$.

###### Proof.

First, we need to bound the Rademacher’s complexity for the class of functions
$\big{\\{}m_{f,y}:f\in\tilde{\mathcal{F}}\big{\\}}$. Observe that

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\tilde{\mathcal{F}}}\bigg{|}n^{-1}\sum_{j=1}^{n}\varepsilon_{j}m_{f,y}(X_{j})\bigg{|}\bigg{]}.$
(89)

By [4, Proof of Theorem 11], we have

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\tilde{\mathcal{F}}}\bigg{|}n^{-1}\sum_{j=1}^{n}\varepsilon_{j}m_{f,y}(X_{j})\bigg{|}\bigg{]}\leq(2K-1)R_{n}(\mathcal{F}),$
(90)

where $R_{n}(\mathcal{F})$ is _the Rademacher complexity function_ of the
class $\mathcal{F}$. Now, assume that this class of function is uniformly
bounded as in practice. Hence, by Theorem 10 for $\varphi$ that is equal to
$1$ on $(-\infty,0]$, is equal to $0$ on $[1,+\infty)$ and is linear in
between, we obtain (86). ∎

In addition, by using the fact that
$(X_{1},Y_{1})-(X_{2},Y_{2})\cdots-(X_{n},Y_{n})$ forms a Markov chain with
stationary distribution $\tilde{\pi}$ (see the discussion on Section 2.2 in
the main document), by applying Theorem 10, we obtain the following result:

######  Theorem 21.

Let $\varphi$ is a nonincreasing function such that
$\varphi(x)\geq\mathbf{1}_{(-\infty,0]}(x)$ for all $x\in\mathbb{R}$. For any
$t>0$,

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\tilde{\mathcal{F}}:P\\{\tilde{f}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{8L(\varphi)}{\delta}R_{n}(\mathcal{H})$
$\displaystyle\qquad\qquad+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp(-2t^{2}),$
(91)

where $B_{n}$ is defined in (54).

As in [4], in the voting methods of combining classifiers, a classifier
produced at each iteration is a convex combination $\tilde{f}$ of simple base
classifiers from the class $\mathcal{H}$. In addition, the Rademacher
complexity can be bounded above by

$\displaystyle R_{n}(\mathcal{H})\leq C\sqrt{\frac{V(\mathcal{H})}{n}}$ (92)

for some constant $C>0$, where $V(\mathcal{H})$ is the VC-dimesion of
$\mathcal{H}$. Let $\varphi$ be equal to $1$ on $(-\infty,0]$, is equal to $0$
on $[1,+\infty)$ and is linear in between. By setting
$t_{\alpha}=\sqrt{\frac{1}{2}\log\frac{\pi^{2}}{3\alpha}}$, from Theorem 21,
with probability at least $1-\alpha$, it holds that

$\displaystyle P\\{\tilde{f}\leq 0\\}$
$\displaystyle\leq\inf_{\delta\in(0,1]}\bigg{[}P_{n}\\{\tilde{f}\leq\delta\\}+\frac{8C}{\delta}\sqrt{\frac{V(\mathcal{H})}{n}}+\big{(}t_{\alpha}+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]},$
(93)

which extends the result of Bartlett et al. [2] to Markov dataset (PAC-bound).

###  6.5 Bounding the generalization error in neural network learning

In this section, we consider the same example as [4, Section 6]. However, we
assume that feature vectors in this dataset is generated by a Markov chain
instead of an i.i.d. process. Let $\mathcal{H}$ be a class of measurable
functions from $\mathcal{S}\to\mathbb{R}$ (base functions). Let
$\tilde{\mathcal{H}}$ be the set of function
$\tilde{f}:\mathcal{S}\times\mathcal{Y}\to\mathbb{R}$. The introduction of
$\tilde{\mathcal{H}}$ is to deal with the new Markov chain
$\\{(X_{n},Y_{n})\\}_{n=1}^{\infty}$ which is generated by both feature
vectors and their labels instead of the feature-based Markov chain
$\\{X_{n}\\}_{n=1}^{\infty}$.

Consider a feed-forward neural network where the set $V$ of all the neurons is
divided into layers

$\displaystyle V=\\{v_{i}\\}\cup\bigcup_{j=0}^{l}V_{j}$ (94)

where $V_{l}=\\{v_{o}\\}$. The neurons $v_{i}$ and $v_{o}$ are called the
input and the output neurons, respectively. To define the network, we will
assign the labels to the neurons in the following way. Each of the base
neurons is labelled by a function from the base class $\mathcal{H}$. Each
neuron of the $j$-th layer $V_{j}$, where $j\geq 1$, is labelled by a vector
$w:=(w_{1},w_{2},\cdots,w_{m})\in\mathbb{R}^{m}$, where $m$ is the number of
inputs of the neuron, i.e. $m=|\mathcal{H}|+1$. Here, $w$ will be called the
vector of weights of the neuron.

Given a Borel function $\sigma$ from $\mathbb{R}$ into $[-1,1]$ (for example,
sigmoid function) and a vector
$w:=(w_{1},w_{2},\cdots,w_{m})\in\mathbb{R}^{m}$, let

$\displaystyle N_{\sigma,w}:\mathbb{R}^{m}\to\mathbb{R},\qquad
N_{\sigma,w}(u_{1},u_{2},\cdots,u_{m}):=\sigma\bigg{(}\sum_{j=1}^{m}w_{j}u_{j}\bigg{)}.$
(95)

For $w\in\mathbb{R}^{m}$,

$\displaystyle\|w\|_{1}:=\sum_{i=1}^{m}|w_{i}|.$ (96)

Let $\sigma_{j}:j\geq 1$ be functions from $\mathbb{R}$ into $[-1,1]$,
satisfying the Lipschitz conditions

$\displaystyle\big{|}\sigma_{j}(u)-\sigma_{j}(v)\big{|}\leq L_{j}|u-v|,\qquad
u,v\in\mathbb{R}.$ (97)

The network works the following way. The input neuron inputs an instance
$x\in\mathcal{S}$. A base neuron computes the value of the base function on
this instance and outputs the value through its output edges. A neuron in the
$j$-th layer ($j\geq 1$) computes and outputs through its output edges the
value $N_{\sigma_{j},w}(u_{1},u_{2},\cdots,u_{m})$ (where
$u_{1},u_{2},\cdots,u_{m}$ are the values of the inputs of the neuron). The
network outputs the value $f(x)$ (of a function $f$ it computes) through the
output edge.

We denote by $\mathcal{N}_{l}$ the set of such networks. We call
$\mathcal{N}_{l}$ the class of feed-forward neural networks with base
$\mathcal{H}$ and $l$ layers of neurons (and with sigmoid $\sigma_{j}$). Let
$\mathcal{N}_{\infty}:=\bigcup_{j=1}^{\infty}\mathcal{N}_{j}$. Define
$\mathcal{H}_{0}:=\mathcal{H}$, and then recursively

$\displaystyle\mathcal{H}_{j}:=\bigg{\\{}N_{\sigma_{j},w}(h_{1},h_{2},\cdots,h_{m}):m\geq
0,h_{i}\in\mathcal{H}_{j-1},w\in\mathbb{R}^{m}\bigg{\\}}\cup\mathcal{H}_{j-1}.$
(98)

Denote $\mathcal{H}_{\infty}:=\bigcup_{j=1}^{\infty}\mathcal{H}_{j}$. Clearly,
$\mathcal{H}_{\infty}$ includes all the functions computable by feed-forward
neural networks with base $\mathcal{H}$.

Let $\\{b_{j}\\}$ be a sequence of positive numbers. We also define
recursively classes of functions computable by feed-forward neural networks
with restrictions on the weights of neurons:

$\displaystyle\mathcal{H}_{j}(b_{1},b_{2},\cdots,b_{j})$ (99)
$\displaystyle\qquad:=\bigg{\\{}N_{\sigma_{j},w}(h_{1},h_{2},\cdots,h_{m}):n\geq
0,h_{i}\in\mathcal{H}_{j-1}(b_{1},b_{2},\cdots,b_{j-1}),w\in\mathbb{R}^{m},\|w\|_{1}\leq
b_{j}\bigg{\\}}$
$\displaystyle\qquad\qquad\qquad\bigcup\mathcal{H}_{j-1}(b_{1},b_{2},\cdots,b_{j-1}).$
(100)

Clearly,

$\displaystyle\mathcal{H}_{\infty}=\bigcup\bigg{\\{}\mathcal{H}_{j}(b_{1},b_{2},\cdots,b_{j}):b_{1},b_{2},\cdots,b_{j}<+\infty\bigg{\\}}.$
(101)

As in the previous section, let $\varphi$ be a function such that
$\varphi(x)\geq I_{(-\infty,0]}$ for all $x\in\mathbb{R}$ and $\varphi$
satisfies the Lipschitz condition with constant $L(\varphi)$. Then, the
following is a direct application of Theorem 10.

######  Theorem 22.

For any $t\geq 0$ and for all $l\geq 1$,

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}(b_{1},b_{2},\cdots,b_{l}):P\\{\tilde{f}\leq 0\\}$
$\displaystyle\qquad>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\prod_{j=1}^{l}(2L_{j}b_{j}+1)G_{n}(\mathcal{H})$
$\displaystyle\qquad\qquad+\frac{2}{\sqrt{n}}+\big{(}t+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}\leq\frac{\pi^{2}}{3}\exp\big{(}-2t^{2}\big{)},$
(102)

where $B_{n}$ is defined in (54).

###### Proof.

Let

$\displaystyle\mathcal{H}_{l}^{\prime}:=\mathcal{H}(b_{1},b_{2},\cdots,b_{l}).$
(103)

As the proof of [4, Theorem 13], it holds that

$\displaystyle G_{n}(\mathcal{H}_{l}^{\prime})$
$\displaystyle:=\mathbb{E}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{H}_{l}^{\prime}}\leq\prod_{j=1}^{l}(2L_{j}b_{j}+1)G_{n}(\mathcal{H}).$
(104)

Hence, (102) is a direct application of Theorem 10 and (104). ∎

Now, given a neural network $f\in\mathcal{N}_{\infty}$, let

$\displaystyle l(f):=\min\\{j\geq 1:f\in\mathcal{N}_{j}\\}.$ (105)

For a number $k$, $1\leq k\leq l(f)$, let $V_{k}(f)$ denote the set of all
neurons of layer $k$ in the graph representing $f$. Denote

$\displaystyle W_{k}(f):=\max_{u\in V_{k}(f)}\|w^{(u)}\|_{1}\vee b_{k},\qquad
k=1,2,\cdots,l(f)$ (106)

where $w^{(u)}$ is the coefficient vector associated with the neuron $u$ of
the layer $k$, and let

$\displaystyle\Lambda(f)$
$\displaystyle:=\prod_{k=1}^{l(f)}(4L_{k}W_{k}(f)+1),$ (107)
$\displaystyle\Gamma_{\alpha}(f)$
$\displaystyle:=\sum_{k=1}^{l(f)}\sqrt{\frac{\alpha}{2}\log(2+\log_{2}W_{k}(f))},$
(108)

where $\alpha>0$ is the number such that $\zeta(\alpha)<3/2$, $\zeta$ being
the Riemann zeta-function:

$\displaystyle\zeta(\alpha):=\sum_{k=1}^{\infty}k^{-\alpha}.$ (109)

Then, by using the same arguments as [4, Proof of Theorem 14], we obtain the
following result.

######  Theorem 23.

For any $t\geq 0$ and for all $l\geq 1$,

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}_{\infty}:P\\{\tilde{f}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\Lambda(f)G_{n}(\mathcal{H})$
$\displaystyle\qquad+\frac{2}{\sqrt{n}}+\big{(}t+\Gamma_{\alpha}(f)+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}$
$\displaystyle\qquad\qquad\leq\frac{\pi^{2}}{3}\big{(}3-2\zeta(\alpha)\big{)}^{-1}\exp\big{(}-2t^{2}\big{)},$
(110)

where $B_{n}$ is defined in (54).

###### Proof.

Let

$\displaystyle\Delta_{k}:=\begin{cases}[2^{k-1},2^{k})\quad\mbox{for}\quad
k\in\mathbb{Z},k\neq 0,1\\\ [1/2,2)\quad\mbox{for}k=1.\end{cases}$ (111)

Then, using the following partition:

$\displaystyle\\{f\in\mathcal{H}_{\infty}\\}=\bigcup_{l=0}^{\infty}\bigcup_{k_{1}\in\mathbb{Z}\setminus\\{0\\}}\bigcup_{k_{2}\in\mathbb{Z}\setminus\\{0\\}}\cdots\bigcup_{k_{l}\in\mathbb{Z}\setminus\\{0\\}}\bigg{\\{}f\in\mathcal{H}_{\infty}:l(f)=l,W_{j}(f)\in\Delta_{k_{j}},\enspace\forall
j\in[l]\bigg{\\}}.$ (112)

On each subset
$\bigg{\\{}f\in\mathcal{H}_{\infty}:l(f)=l,W_{j}(f)\in\Delta_{k_{j}},\enspace\forall
j\in[l]\bigg{\\}}$, we can lower bound $\Lambda(f)$ and $\Gamma_{\alpha}(f)$
by

$\displaystyle\Lambda(f)$
$\displaystyle\geq\prod_{j=1}^{l}(2L_{j}2^{k_{j}}+1),$ (113)
$\displaystyle\Gamma_{\alpha}(f)$
$\displaystyle\geq\sum_{j=1}^{l}\sqrt{\frac{\alpha}{2}\log(|k_{j}|+1)}.$ (114)

By replacing $t$ by $t+\sum_{j=1}^{l}\sqrt{\frac{\alpha}{2}\log(k_{j}+1)}$ and
using Theorem 10 to bound the probability of each event and then using the
union bound, we can show that

$\displaystyle\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}_{\infty}:P\\{\tilde{f}\leq
0\\}>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\Lambda(f)G_{n}(\mathcal{H})$
$\displaystyle\qquad+\frac{2}{\sqrt{n}}+\big{(}t+\Gamma_{\alpha}(f)+\sqrt{\log\log_{2}2\delta^{-1}}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}$
(115) $\displaystyle\leq\mathbb{P}\bigg{(}\exists
f\in\mathcal{H}_{\infty}:P\\{\tilde{f}\leq 0\\}$
$\displaystyle\qquad>\inf_{\delta\in(0,1]}\bigg{[}P_{n}\varphi\bigg{(}\frac{\tilde{f}}{\delta}\bigg{)}+\frac{2\sqrt{2\pi}L(\varphi)}{\delta}\Lambda(f)G_{n}(\mathcal{H})$
$\displaystyle\qquad\qquad+\bigg{(}t+\sum_{j=1}^{l}\sqrt{\frac{\alpha}{2}\log(k_{j}+1)}+\sqrt{\log\log_{2}2\delta^{-1}}\bigg{)}\sqrt{\frac{\tau_{\min}}{n}}+\frac{2}{\sqrt{n}}+B_{n}\bigg{]}\bigg{)}$
(116)
$\displaystyle\qquad\leq\sum_{l=0}^{\infty}\sum_{k_{1}\in\mathbb{Z}\setminus\\{0\\}}\cdots\sum_{k_{l}\in\mathbb{Z}\setminus\\{0\\}}2\exp\bigg{(}-2\bigg{(}t+\sum_{j=1}^{l}\sqrt{\frac{\alpha}{2}\log(k_{j}+1)}\bigg{)}^{2}\bigg{)}$
(117)
$\displaystyle\qquad\leq\frac{\pi^{2}}{3}\big{(}3-2\zeta(\alpha)\big{)}^{-1}\exp\big{(}-2t^{2}\big{)},$
(118)

where the last equation is followed by using some algebraic manipulations. ∎

##  7 Extension to High-Order Markov Chains

In this section, we extend our results in previous sections to $m$-order
Markov chains and a mixture of $m$ independent Markov services.

###  7.1 Extend to $m$-order Markov chain

In this subsection, we extend our results in previous sections to $m$-order
homogeneous Markov chain. The main idea is to convert $m$-order homogeneous
Markov chains to $1$-order homogeneous Markov chain and use our results in
previous sections to bound the generalization error.

We start with the following simple example.

######  Example 24.

[$m$-order moving average process without noise] Consider the following
$m$-order Markov chain

$\displaystyle X_{k}=\sum_{i=1}^{m}a_{i}X_{k-i},\qquad k\in\mathbb{Z}_{+}.$
(119)

Let $Y_{k}:=[X_{k+m-1},X_{k+m-2},\cdots,X_{k}]^{T}$. Then, from (119), we
obtain

$\displaystyle Y_{k+1}=\mathbf{G}Y_{k},\qquad\forall k\in\mathbb{Z}_{+}$ (120)

where

$\displaystyle\mathbf{G}:=\begin{pmatrix}a_{1}&a_{2}&\cdots&a_{m-1}&a_{m}\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}.$ (121)

It is clear that $\\{\mathbf{Y}_{n}\\}_{n=1}^{\infty}$ is an order-$1$ Markov
chain. Hence, instead of directly working with the $m$-order Markov chain
$\\{\mathbf{X}_{n}\\}_{n=1}^{\infty}$, we can find an upper bound for the
Markov chain $\\{Y_{n}\\}_{n=1}^{\infty}$.

To derive generalization error bounds for the Markov chain
$\\{Y_{n}\\}_{n=1}^{\infty}$, we can use the following arguments. For all
$f\in\mathcal{F}$ and $(x_{k},x_{k+1},\cdots,x_{k+m-1})\in\mathcal{S}^{m}$, by
setting $\tilde{f}(x_{k},x_{k+1},\cdots,x_{k+m-1})=f(x_{k})$ where
$\tilde{f}:\mathcal{S}^{m}\to\mathbb{R}$, we obtain

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{f(X_{i})\leq 0\\}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{\tilde{f}(Y_{i})\leq
0\\}.$ (122)

Hence, by applying all the results for $1$-order Markov chain
$\\{Y_{n}\\}_{n=1}^{\infty}$, we obtain corresponding upper bounds for the
sequence of $m$-order Markov chain $\\{X_{n}\\}_{n=1}^{\infty}$.

This approach can be extended to more general $m$-order Markov chain
$X_{k}=g(X_{k-1},X_{k-2}\cdots,X_{k-m})$ where
$g:\mathcal{S}^{m}\to\mathbb{R}$. More specifically, for any tuple
$(x_{1},x_{2},\cdots,x_{m})\in\mathcal{S}^{m}$, observe that

$\displaystyle dg=\frac{\partial g}{\partial x_{1}}dx_{1}+\frac{\partial
g}{\partial x_{2}}dx_{2}+\cdots+\frac{\partial g}{\partial x_{m}}dx_{m}.$
(123)

Hence, if $\frac{\partial g}{\partial x_{i}}=\alpha_{i}$ for some constant
$\alpha_{i}$ and for each $i\in[m]$, from (123), we have

$\displaystyle
g(x_{1},x_{2},\cdots,x_{m})=g(c_{1},c_{2},\cdots,c_{m})+\sum_{i=1}^{m}a_{i}x_{i}+\sum_{i=1}^{m}a_{i}\nu_{i},$
(124)

where $\nu_{i}$’s are constants. One specific example where the function
$g:\mathcal{S}^{m}\to\mathbb{R}$ satisfies this property is
$g(x_{1},x_{2},\cdots,x_{m})=a_{1}x_{1}+a_{2}x_{2}+\cdots a_{m}x_{m}$, where
$a_{1},a_{2},\cdots,a_{m}$ are constants as in Example 24.

Now, by choosing
$u=(g(c_{1},c_{2},\cdots,c_{m})+\sum_{i=1}^{m}\alpha_{i}\nu_{i}\big{)}/(1-\sum_{i=1}^{m}a_{i}\nu_{i})$,
from (124), we have

$\displaystyle
g(x_{1},x_{2},\cdots,x_{m})+u=\sum_{i=1}^{m}a_{i}\big{(}x_{i}+u\big{)}.$ (125)

By setting
$Y_{k}=\begin{bmatrix}X_{k+m-1}+u&X_{k+m-2}+u&\cdots&X_{k}+u\end{bmatrix}^{T}$,
from (125), we have:

$\displaystyle Y_{k+1}=\begin{pmatrix}a_{1}&a_{2}&\cdots&a_{m-1}&a_{m}\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}\begin{bmatrix}\end{bmatrix}Y_{k}.$ (126)

In a more general setting, if $X_{k}=g(X_{k-1},\cdots,X_{k-m},V_{k})$ for some
random variable $V_{k}$ which is independent of $\\{X_{k-i}\\}_{i=1}^{m}$ such
as the Autoregressive model (AR), where

$\displaystyle X_{k}=c+\sum_{i=1}^{m}a_{i}X_{t-i}+V_{k},$ (127)

we can use the following conversion procedure. First, by using Taylor’s
approximation (to the first-order), we obtain

$\displaystyle g(x_{1},x_{2},\cdots,x_{m},\xi)$ $\displaystyle\approx
g(c_{1},c_{2},\cdots,c_{m},\xi_{0})+\sum_{i=1}^{m}\frac{\partial g}{\partial
x_{i}}\bigg{|}_{(c_{1},c_{2},\cdots,c_{m},\zeta_{0})}(x_{i}-c_{i})$
$\displaystyle\qquad+\frac{\partial g}{\partial
v}\bigg{|}_{(c_{1},c_{2},\cdots,c_{m},\xi_{0})}(\xi-\xi_{0})$ (128)

for some good choice of
$(c_{1},c_{2},\cdots,c_{m},\xi_{0})\in\mathcal{S}^{m}\times\mathcal{V}$, where
$\mathcal{V}$ is the alphabet of $V_{k}$. Using the above trick with
$Y_{k}=\begin{bmatrix}X_{k+m-1}+u&X_{k+m-2}+u&\cdots&X_{k}+u\end{bmatrix}^{T}$,
$a_{i}=\frac{\partial g}{\partial
x_{i}}\big{|}_{(c_{1},c_{2},\cdots,c_{m},\xi_{0})}$, we can replace the
recursion $X_{k}=g(X_{k-1},\cdots,X_{k-m},V_{k})$ by the following equivalent
recursion:

$\displaystyle Y_{k+1}=\begin{pmatrix}a_{1}&a_{2}&\cdots&a_{m-1}&a_{m}\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}Y_{k}+\begin{pmatrix}\frac{\partial g}{\partial
v}\big{|}_{(c_{1},c_{2},\cdots,c_{m},\xi_{0})}V_{k}\\\ 0\\\ 0\\\ \vdots\\\
0\end{pmatrix}.$ (129)

Since $V_{k}$ is independent of $\\{X_{k+m-i}\\}_{i=2}^{m+1}$ or $Y_{k}$,
(129) models a new $1$-order Markov chain $\\{Y_{k}\\}_{k=1}^{\infty}$. Then,
by using the the same arguments to obtain (122), we can derive bounds on
generalization error for this model.

For a general $m$-order homogeneous Markov chain, it holds that

$\displaystyle P_{X_{k}|X_{k-1}=x_{1},X_{k-2}=x_{2},\cdots,X_{k-m}=x_{m}}\sim
T_{(x_{1},x_{2},\cdots,x_{m})}$ (130)

for all $(x_{1},x_{2},\cdots,x_{m})\in\mathcal{S}^{m}$, where
$T_{(x_{1},x_{2},\cdots,x_{m})}$ is a random variable which depends only on
$x_{1},x_{2},\cdots,x_{m}$ and does not depend on $k$. Hence, we can represent
the

$\displaystyle
X_{k}=\tilde{g}(X_{k-1},X_{k-2},\cdots,X_{k-m},T_{(X_{k-1},X_{k-2},\cdots,X_{k-m})}),$
(131)

where
$T_{(X_{k-1},X_{k-2},\cdots,X_{k-m})}=f(\varepsilon_{k},V_{k},V_{k-1},\cdots,V_{k-q},X_{k-1},X_{k-2},\cdots,X_{k-m})$.
Here, $\varepsilon_{k}$ represents new noise at time $k$ which is independent
of the past. Hence, in a general $m$-order homogeneous Markov chain, we can
represent the $m$-order homogeneous Markov chain by the following recursion:

$\displaystyle
X_{k}=g(X_{k-1},X_{k-2},\cdots,X_{k-m},\varepsilon_{k},V_{k},V_{k-1},\cdots,V_{k-q}\big{)},$
(132)

where $\varepsilon_{k}$ represents new noise at time $k$ and
$q\in\mathbb{Z}_{+}$. By using Taylor expansion to the first order, we can
approximate the Markov chain in (132) by an Autoregressive Moving-Average
Model (ARMA$(m,q)$) model as following:

$\displaystyle
X_{k}=c+\varepsilon_{k}+\sum_{i=1}^{m}a_{i}X_{k-i}+\sum_{i=1}^{q}\theta_{i}\varepsilon_{k-i},$
(133)

where $c$ and $a_{i}$’s are constants, and
$\\{\varepsilon_{k}\\}_{k=1}^{\infty}$ are i. i. d. Gaussian random variables
$\mathcal{N}(0,\sigma^{2})$. For this model, let

$\displaystyle V_{k}:=\sum_{i=1}^{k}\varepsilon_{i}$ (134)

and

$\displaystyle Y_{k}:=\begin{pmatrix}X_{k+m-1}+u\\\ X_{k+m-2}+u\\\ \vdots\\\
X_{k}+u\\\ V_{k+m-1}\\\ V_{k+m-2}\\\ \vdots\\\ V_{k+m-q}\\\
V_{k+m-q-1}\end{pmatrix},$ (135)

where

$\displaystyle u:=\frac{c}{1-\sum_{i=1}^{m}a_{i}}.$ (136)

Let $V_{k}:=\sum_{i=1}^{k}\varepsilon_{i}$ for all $k\geq 1$. Observe that

$\displaystyle V_{k+m}=\varepsilon_{k+m}+V_{k+m-1}.$ (137)

On the other hand, we have

$\displaystyle X_{k+m}$
$\displaystyle=c+\varepsilon_{k+m}+\sum_{i=1}^{m}a_{i}X_{k+m-i}+\sum_{i=1}^{q}\theta_{i}\varepsilon_{k+m-i}$
(138)
$\displaystyle=c+\varepsilon_{k+m}+\sum_{i=1}^{m}a_{i}X_{k+m-i}+\sum_{i=1}^{q}\theta_{i}\big{(}V_{k+m-i}-V_{k+m-1-i}\big{)}$
(139)
$\displaystyle=c+\varepsilon_{k+m}+\sum_{i=1}^{m}a_{i}X_{k+m-i}+\theta_{1}V_{k+m-1}+\sum_{i=1}^{q-1}\big{(}\theta_{i+1}-\theta_{i}\big{)}V_{k+m-1-i}-\theta_{q}V_{k+m-q-1}.$
(140)

Then, we have

$\displaystyle Y_{k+1}=\mathbf{G}Y_{k}+\begin{pmatrix}\varepsilon_{k+m}\\\
0\\\ \vdots\\\ 0\\\ \varepsilon_{k+m}\\\ 0\\\ \vdots\\\ 0\end{pmatrix},$ (141)

where

$\displaystyle\mathbf{G}:=\begin{pmatrix}\mathbf{G}_{11}&\mathbf{G}_{12}\\\
\mathbf{G}_{21}&\mathbf{G}_{22}\end{pmatrix}.$ (142)

Here,

$\displaystyle\mathbf{G}_{11}:=\begin{pmatrix}a_{1}&a_{2}&\cdots&a_{m-1}&a_{m}\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}_{m\times q+1},$ (143)
$\displaystyle\mathbf{G}_{12}:=\begin{pmatrix}\theta_{1}&\theta_{2}-\theta_{1}&\cdots&\theta_{q}-\theta_{q-1}&-\theta_{q}\\\
0&0&\cdots&0&0\\\ 0&0&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&0&0\end{pmatrix}_{m\times q+1},$ (144)
$\displaystyle\mathbf{G}_{21}:=\begin{pmatrix}0&0&\cdots&0&0\\\
0&0&\cdots&0&0\\\ 0&0&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&0&0\end{pmatrix}_{q+1\times m},$ (145)

and

$\displaystyle\mathbf{G}_{22}:=\begin{pmatrix}1&0&\cdots&0&0\\\
1&0&\cdots&0&0\\\ 0&1&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&1&0\end{pmatrix}_{q+1\times q+1}.$ (146)

Since $\varepsilon_{k+m}$ is independent of $Y_{k}$, (141) models a $1$-order
Markov chain. Hence, we can use the above arguments to derive new
generalization error bounds for the $m$-order homogeneous Markov chain where
ARMA model is a special case.

###  7.2 Mixture of $m$ Services

In this section, we consider the case that
$Y_{k}=\sum_{l=1}^{m}\alpha_{l}X_{k}^{(l)}$ for all $k=1,2,\cdots$, where
$\\{X_{k}^{(l)}\\}_{k=1}^{\infty}$ are independent Markov chains on
$\mathcal{S}$ with stationary distribution for all $l\in[m]$. This setting
usually happens in practice, for example, video is a mixture of voice, image,
and text, where each service can be modelled as a high-order Markov chain and
the order of the Markov chain depends on the type of service.

Let

$\displaystyle
Z_{k}:=\begin{pmatrix}\alpha_{1}X_{k}^{(1)}+\alpha_{2}X_{k}^{(2)}+\cdots\alpha_{m}X_{k}^{(m)}\\\
\alpha_{2}X_{k}^{(2)}+\cdots\alpha_{m}X_{k}^{(m)}\\\ \vdots\\\
\alpha_{m}X_{k}^{(m)}\end{pmatrix}=\begin{pmatrix}Y_{k}\\\
\alpha_{2}X_{k}^{(2)}+\cdots\alpha_{m}X_{k}^{(m)}\\\ \vdots\\\
\alpha_{m}X_{k}^{(m)}\end{pmatrix}.$ (147)

Then, it holds that

$\displaystyle Z_{k}=\mathbf{G}X_{k}$ (148)

where

$\displaystyle\mathbf{G}:=\begin{pmatrix}\alpha_{1}&\alpha_{2}&\cdots&\alpha_{m-1}&\alpha_{m}\\\
0&\alpha_{2}&\cdots&\alpha_{m-1}&\alpha_{m}\\\
\vdots&\vdots&\vdots&\vdots&\vdots\\\ 0&0&\cdots&0&\alpha_{m}\end{pmatrix},$
(149)

and

$\displaystyle X_{k}:=\begin{pmatrix}X_{k}^{(1)}\\\ X_{k}^{(2)}\\\ \vdots\\\
X_{k}^{(m)}\end{pmatrix}.$ (150)

It is obvious that $\mathbf{G}$ is non-singular since
$\det(\mathbf{G})=\prod_{l=1}^{m}\alpha_{l}\neq 0$. Therefore, for fixed pair
$(x,y)\in\mathcal{S}^{m}\times\mathcal{S}^{m}$, we have

$\displaystyle\mathbb{P}\big{(}Z_{k+1}=y\big{|}Z_{k}=x\big{)}$
$\displaystyle=\mathbb{P}(X_{k+1}=\mathbf{G}^{-1}y\big{|}X_{k}=\mathbf{G}^{-1}x).$
(151)

Now, assume that
$\mathbf{G}^{-1}x=\begin{pmatrix}\beta_{x}^{(1)},\beta_{x}^{(2)},\cdots\beta_{x}^{(m)})\end{pmatrix}$
and
$\mathbf{G}^{-1}y=\begin{pmatrix}\beta_{y}^{(1)},\beta_{y}^{(2)},\cdots\beta_{y}^{(m)})\end{pmatrix}$.
Then, from (150) and (151), we have

$\displaystyle\mathbb{P}\big{(}Z_{k+1}=y\big{|}Z_{k}=x\big{)}$
$\displaystyle=\mathbb{P}\bigg{(}\bigcap_{l=1}^{m}\big{\\{}X_{k+1}^{(l)}=\beta_{y}^{(l)}\big{\\}}\bigg{|}\bigcap_{l=1}^{m}\big{\\{}X_{k}^{(l)}=\beta_{x}^{(l)}\big{\\}}\bigg{)}$
(152)
$\displaystyle=\prod_{l=1}^{m}\mathbb{P}\big{(}X_{k+1}^{(l)}=\beta_{y}^{(l)}\big{|}X_{k}^{(l)}=\beta_{x}^{(l)}\big{)}$
(153) $\displaystyle=\prod_{l=1}^{m}Q_{l}(\beta_{x}^{(l)},\beta_{y}^{(l)}),$
(154)

where $Q_{l}$ is the transition probability of the Markov chain $l$. It
follows that $\\{Z_{k}\\}_{k=1}^{\infty}$ is a $1$-order Markov chain. It is
easy to see that $\\{Z_{k}\\}_{k=1}^{\infty}$ has stationary distribution if
all the Markov chains $\\{X_{k}^{(l)}\\}_{l=1}^{m}$ have stationary
distributions.

Now, as Subsection 7.1, to derive generalization error bounds for the Markov
chain $\\{X_{n}\\}_{n=1}^{\infty}$, we can use the following arguments. For
all $f\in\mathcal{F}$ and by setting
$\tilde{f}(z_{1},z_{2},\cdots,z_{m}):=f(z_{1})$ where
$\tilde{f}:\mathcal{S}^{m}\to\mathbb{R}$, we obtain
$\tilde{f}(GX_{k})=f(Y_{k})$ and

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{f(Y_{i})\leq 0\\}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{\tilde{f}(\mathbf{G}X_{i})\leq
0\\}.$ (155)

Hence, by applying all the results for $1$-order Markov chain
$\\{Z_{n}\\}_{n=1}^{\infty}$ where $Z_{n}=\mathbf{G}X_{n}$, we obtain
corresponding upper bounds for the sequence of $m$-order Markov chain
$\\{X_{n}\\}_{n=1}^{\infty}$.

##  Appendix A Proof of Lemma 8

Before going to prove Lemma 8, we observe the following interesting fact.

######  Lemma 25.

Let $\\{X_{n}\\}_{n=1}^{\infty}$ be an arbitrary process on a Polish space
$\mathcal{S}$, and let $\\{Y_{n}\\}_{n=1}^{\infty}$ be a independent copy
(replica) of $\\{X_{n}\\}_{n=1}^{\infty}$. Denote by
$\mathbf{X}=(X_{1},X_{2},\cdots,X_{n}),\mathbf{Y}=(Y_{1},Y_{2},\cdots,Y_{n})$,
and $\mathcal{F}$ a class of uniformly bounded functions from
$\mathcal{S}\to\mathbb{R}$. Let
$\bm{\epsilon}:=(\varepsilon_{1},\varepsilon_{2},\cdots,\varepsilon_{n})$ be a
vector of i.i.d. Rademacher’s random variables. Then, the following holds:

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\bigg{[}\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}(f(X_{i})-f(Y_{i}))\bigg{|}\bigg{]}\bigg{]}=\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\sum_{i=1}^{n}(f(X_{i})-f(Y_{i}))\bigg{|}\bigg{]}.$
(156)

######  Remark 26.

Our lemma generalizes a similar fact for i.i.d. processes. In the case that
$\\{X_{n}\\}_{n=1}^{\infty}$ is an i.i.d. random process, (156) holds with
equality since
$P_{X^{n},Y^{n}}(x_{1},x_{2},\cdots,x_{n},y_{1},y_{2},\cdots,y_{n})$ is
invariant under permutation. However, for the Markov case, this fact does not
hold in general. Hence, in the following, we provide a new proof for (156),
which works for any process $\\{X_{n}\\}_{n=1}^{\infty}$ by making use of the
properties of Rademacher’s process.

###### Proof.

Let $g(x,y):=f(x)-f(y)$ and
$\mathcal{G}:=\\{g:\mathcal{S}\times\mathcal{S}\to\mathbb{R}:g(x,y):=f(x)-f(y)\enspace\mbox{for
some}\enspace f\in\mathcal{F}\\}$. Then, it holds that

$\displaystyle\mathbb{E}_{\bm{\epsilon}}\bigg{[}\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}(f(X_{i})-f(Y_{i}))\bigg{|}\bigg{]}\bigg{]}$
$\displaystyle=\mathbb{E}_{\bm{\epsilon}}\bigg{[}\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}\bigg{]}.$
(157)

Observe that $g(X_{i},Y_{i})=-g(Y_{i},X_{i})$ for all $i\in[n]$.

For all $j\in[n]$, denote by

$\displaystyle\mathcal{N}_{j}:=[n]\setminus\\{j\\},$ (158)

and

$\displaystyle\varepsilon_{\mathcal{N}_{j}}:=\\{\varepsilon_{i}:i\in\mathcal{N}_{j}\\}.$
(159)

Now, for each $j\in[n]$, observe that $\varepsilon_{j}$ is independent of
$X_{1}^{n},Y_{1}^{n},\varepsilon_{\mathcal{N}_{j}}$. Hence, we have

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}$
$\displaystyle\qquad=\frac{1}{2}\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{j},Y_{j})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad+\frac{1}{2}\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})-g(X_{j},Y_{j})\bigg{|}\bigg{]}$
(160)
$\displaystyle\qquad=\frac{1}{2}\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{j},Y_{j})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad+\frac{1}{2}\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(Y_{j},X_{j})\bigg{|}\bigg{]}$
(161)

where (161) follows from $g(X_{j},Y_{j})=-g(Y_{j},X_{j})$.

Now, by setting $\tilde{\epsilon}_{i}:=-\varepsilon_{i}$ for all $i\in n$.
Then, we obtain

$\displaystyle\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(Y_{j},X_{j})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad=\mathbb{E}_{\tilde{\varepsilon}_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\tilde{\epsilon}_{i}g(X_{i},Y_{i})+g(Y_{j},X_{j})\bigg{|}\bigg{]}$
(162)
$\displaystyle\qquad\qquad=\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(Y_{i},X_{i})+g(Y_{j},X_{j})\bigg{|}\bigg{]}$
(163)
$\displaystyle\qquad\qquad=\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{j},Y_{j})\bigg{|}\bigg{]},$
(164)

where (162) follows from $(\tilde{\epsilon}_{i}:i\in\mathcal{N}_{j})$ has the
same distribution as $(\varepsilon_{i}:i\in\mathcal{N}_{j})$, (163) follows
from $g(X_{i},Y_{i})=-g(Y_{i},X_{i})$ and
$\tilde{\epsilon}_{i}=-\varepsilon_{i}$, and (164) follows from
$g(X_{i},Y_{i})=-g(Y_{i},X_{i})$ for all $i\in[n]$.

From (161) and (164), we have

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}=\mathbb{E}_{\varepsilon_{\mathcal{N}_{j}},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i\in\mathcal{N}_{j}}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{j},Y_{j})\bigg{|}\bigg{]}\quad\forall
j\in[n].$ (165)

It follows that

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\varepsilon_{1}^{n-1},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-1}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{n},Y_{n})\bigg{|}\bigg{]}$
(166)
$\displaystyle\qquad=\frac{1}{2}\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{n-1},Y_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad+\frac{1}{2}\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})-g(X_{n-1},Y_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}$
(167)
$\displaystyle\qquad=\frac{1}{2}\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{n-1},Y_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad+\frac{1}{2}\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(Y_{n-1},X_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]},$
(168)

where (166) follows from setting $j=n$ in (165), and (168) follows from
$g(Y_{n-1},X_{n-1})=-g(X_{n-1},Y_{n-1})$.

Now, for any fixed tuple
$(x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-1})\in\mathcal{S}^{n-1}\times\mathcal{S}^{n-1}\times\\{-1,1\\}^{n-1}$,
observe that

$\displaystyle
P_{X_{n},Y_{n}|X_{1}^{n-1},Y_{1}^{n-1},\varepsilon_{1}^{n-2}}(x_{n},y_{n}|x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2})$
$\displaystyle\qquad\qquad=P_{X_{n}|X_{1}^{n-1}}(x_{n}|x_{1}^{n-1})P_{Y_{n}|Y_{1}^{n-1}}(y_{n}|y_{1}^{n-1})$
(169)
$\displaystyle\qquad\qquad=P_{Y_{n}|Y_{1}^{n-1}}(x_{n}|x_{1}^{n-1})P_{X_{n}|X_{1}^{n-1}}(y_{n}|y_{1}^{n-1})$
(170)
$\displaystyle\qquad\qquad=P_{Y_{n},X_{n}|Y_{1}^{n-1},X_{1}^{n-1},\varepsilon_{1}^{n-2}}(x_{n},y_{n}|x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2}).$
(171)

On the other hand, we also have

$\displaystyle
P_{X_{1}^{n-1},Y_{1}^{n-1},\varepsilon_{1}^{n-2}}(x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2})$
$\displaystyle\qquad=P_{\varepsilon_{1}^{n-2}}(\varepsilon_{1}^{n-2})P_{X_{1}^{n-1}}(x_{1}^{n-1})P_{Y_{1}^{n-1}}(y_{1}^{n-1})$
(172)
$\displaystyle\qquad=P_{\varepsilon_{1}^{n-2}}(\varepsilon_{1}^{n-2})P_{Y_{1}^{n-1}}(x_{1}^{n-1})P_{X_{1}^{n-1}}(y_{1}^{n-1})$
(173)
$\displaystyle\qquad=P_{Y_{1}^{n-1},X_{1}^{n-1},\varepsilon_{1}^{n-2}}(x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2}).$
(174)

Hence, from (171) and (174), we obtain

$\displaystyle
P_{X_{1}^{n},Y_{1}^{n},\varepsilon_{1}^{n-2}}\big{(}x_{1}^{n},y_{1}^{n},\varepsilon_{1}^{n-2}\big{)}$
$\displaystyle\qquad=P_{X_{1}^{n-1}Y_{1}^{n-1}\varepsilon_{1}^{n-2}}(x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2})P_{X_{n}Y_{n}|X_{1}^{n-1}Y_{1}^{n-1}\varepsilon_{1}^{n-2}}\big{(}x_{n},y_{n}|x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2}\big{)}$
(175)
$\displaystyle\qquad=P_{Y_{1}^{n-1},X_{1}^{n-1},\varepsilon_{1}^{n-2}}(x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2})P_{Y_{n},X_{n}|Y_{1}^{n-1},X_{1}^{n-1},\varepsilon_{1}^{n-2}}\big{(}x_{n},y_{n}|x_{1}^{n-1},y_{1}^{n-1},\varepsilon_{1}^{n-2}\big{)}$
(176)
$\displaystyle\qquad=P_{Y_{1}^{n},X_{1}^{n},\varepsilon_{1}^{n-2}}\big{(}x_{1}^{n},y_{1}^{n},\varepsilon_{1}^{n-2}\big{)}.$
(177)

Now, from (177), we also have

$\displaystyle
P_{X_{1}^{n},Y_{1}^{n}}(x_{1}^{n},y_{1}^{n})=P_{Y_{1}^{n}X_{1}^{n}}(x_{1}^{n},y_{1}^{n}).$
(178)

It follows from (178) that

$\displaystyle P_{X_{n-1},Y_{n-1}}(x_{n-1},y_{n-1})$
$\displaystyle=\sum_{x_{1}^{n-2},y_{1}^{n-2},x_{n},y_{n}}P_{X_{1}^{n},Y_{1}^{n}}(x_{1}^{n},y_{1}^{n})$
(179)
$\displaystyle=\sum_{x_{1}^{n-2},y_{1}^{n-2},x_{n},y_{n}}P_{Y_{1}^{n}X_{1}^{n}}(x_{1}^{n},y_{1}^{n})$
(180) $\displaystyle=P_{Y_{n-1}X_{n-1}}(x_{n-1},y_{n-1}).$ (181)

Hence, from (177) and (181), we have

$\displaystyle
P_{X_{n},Y_{n},X_{1}^{n-2},Y_{1}^{n-2},\varepsilon_{1}^{n-2}|X_{n-1},Y_{n-1}}\big{(}x_{n},y_{n},x_{1}^{n-2},y_{1}^{n-2},\varepsilon_{1}^{n-2}|x_{n-1},y_{n-1}\big{)}$
(182)
$\displaystyle\qquad=\frac{P_{X_{1}^{n},Y_{1}^{n},\varepsilon_{1}^{n-2}}(x_{1}^{n},y_{1}^{n},\varepsilon_{1}^{n-2})}{P_{X_{n-1}Y_{n-1}}(x_{n-1},y_{n-1})}$
(183)
$\displaystyle\qquad=\frac{P_{Y_{1}^{n},X_{1}^{n},\varepsilon_{1}^{n-2}}\big{(}x_{1}^{n},y_{1}^{n},\varepsilon_{1}^{n-2}\big{)}}{P_{Y_{n-1}X_{n-1}}(x_{n-1},y_{n-1})}$
(184)
$\displaystyle\qquad=P_{X_{n},Y_{n},X_{1}^{n-2},Y_{1}^{n-2},\varepsilon_{1}^{n-2}|X_{n-1},Y_{n-1}}\big{(}y_{n},x_{n},y_{1}^{n-2},x_{1}^{n-2},\varepsilon_{1}^{n-2}|y_{n-1},x_{n-1}\big{)}.$
(185)

From (185), for each fixed $(x_{n-1},y_{n-1})\in\mathcal{S}\times\mathcal{S}$,
we have

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n-2},Y_{1}^{n-2},X_{n},Y_{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(Y_{n-1},X_{n-1})$
$\displaystyle\qquad\qquad+g(X_{n},Y_{n})\bigg{|}\bigg{|}X_{n-1}=x_{n-1},Y_{n-1}=y_{n-1}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n-2},Y_{1}^{n-2},X_{n},Y_{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(y_{n-1},x_{n-1})$
$\displaystyle\qquad\qquad+g(X_{n},Y_{n})\bigg{|}\bigg{|}X_{n-1}=x_{n-1},Y_{n-1}=y_{n-1}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n-2},Y_{1}^{n-2},X_{n},Y_{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(Y_{i},X_{i})+g(y_{n-1},x_{n-1})$
$\displaystyle\qquad\qquad+g(Y_{n},X_{n})\bigg{|}\bigg{|}Y_{n-1}=x_{n-1},X_{n-1}=y_{n-1}\bigg{]}$
(186)
$\displaystyle\qquad=\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n-2},Y_{1}^{n-2},X_{n},Y_{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(x_{n-1},y_{n-1})$
$\displaystyle\qquad\qquad+g(X_{n},Y_{n})\bigg{|}\bigg{|}Y_{n-1}=x_{n-1},X_{n-1}=y_{n-1}\bigg{]}$
(187)

where (186) follows from (185), and (187) follows from the fact that
$g(x,y)=-g(y,x)$ for all $x,y\in\mathcal{S}\times\mathcal{S}$.

From (187) and (181), we obtain

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(Y_{n-1},X_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{n-1},Y_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}.$
(188)

From (168) and (188), we obtain

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}$
$\displaystyle\qquad\qquad=\mathbb{E}_{\varepsilon_{1}^{n-2},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n-2}\varepsilon_{i}g(X_{i},Y_{i})+g(X_{n-1},Y_{n-1})+g(X_{n},Y_{n})\bigg{|}\bigg{]}.$
(189)

By using induction, we finally obtain

$\displaystyle\mathbb{E}_{\varepsilon_{1}^{n},X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}g(X_{i},Y_{i})\bigg{|}\bigg{]}=\mathbb{E}_{X_{1}^{n},Y_{1}^{n}}\bigg{[}\sup_{g\in\mathcal{G}}\bigg{|}\sum_{i=1}^{n}g(X_{i},Y_{i})\bigg{|}\bigg{]},$
(190)

or equation (156) holds. ∎

Next, recall the following result which was developed base on the spectral
method [29]:

######  Lemma 27.

[28, Theorems 3.41] Let $X_{1},X_{2},\cdots,X_{n}$ be a stationary Markov
chain on some Polish space with $L_{2}$ spectral gap $\lambda$ defined in
Section 2.1 in the main document and the initial distribution
$\nu\in\mathcal{M}_{2}$. Let $f\in\mathcal{F}$ and define

$\displaystyle S_{n,n_{0}}(f)=\frac{1}{n}\sum_{j=1}^{n}f(X_{j+n_{0}})$ (191)

for all $n_{0}\geq 0$. Then, it holds that

$\displaystyle\mathbb{E}\bigg{[}\bigg{|}S_{n,n_{0}}(f)-\mathbb{E}_{\pi}[f(X)]\bigg{|}^{2}\bigg{]}\leq\frac{2M}{n(1-\lambda)}+\frac{64M^{2}}{n^{2}(1-\lambda)^{2}}\lambda^{n_{0}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}.$
(192)

In addition, we recall the following McDiarmid’s inequality for Markov chain:

######  Lemma 28.

[24, Cor. 2.10] Let $\mathbf{X}:=(X_{1},X_{2},\cdots,X_{n})$ be a homogeneous
Markov chain, taking values in a Polish state space
$\Lambda=\underbrace{\mathcal{S}\times\mathcal{S}\times\cdots\times\mathcal{S}}_{n\enspace\rm{times}}$,
with mixing time $t_{\rm{mix}}(\varepsilon)$ (for $0\leq\varepsilon\leq 1$).
Recall the definition of $\tau_{\min}$ in Eq. (3) in the main document.
Suppose that $f:\Lambda\to\mathbb{R}$ satisfies

$\displaystyle
f(\mathbf{x})-f(\mathbf{y})\leq\sum_{i=1}^{n}c_{i}\mathbf{1}\\{x_{i}\neq
y_{i}\\}$ (193)

for every $\mathbf{x},\mathbf{y}\in\Lambda$, for some
$c\in\mathbb{R}_{+}^{n}$. Then, for any $t\geq 0$,

$\displaystyle\mathbb{P}_{\mathbf{X}}\big{[}\big{|}f(\mathbf{X})-\mathbb{E}[f(\mathbf{X})]\big{|}\geq
t\big{]}\leq 2\exp\bigg{(}-\frac{2t^{2}}{\|c\|_{2}^{2}\tau_{\min}}\bigg{)}.$
(194)

Now, we return to the proof of Lemma 8.

###### Proof of Lemma 8.

For each $f\in\mathcal{F}$, observe that

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-\int_{\mathcal{S}}\pi(x)f(x)dx$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-\mathbb{E}[f(X_{i})]+\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[f(X_{i})]-\int_{\mathcal{S}}\pi(x)f(x)dx.$
(195)

On the other hand, we have

$\displaystyle\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}[f(X_{i})]-\int_{\mathcal{S}}\pi(x)f(x)dx\bigg{|}$
$\displaystyle\qquad=\mathbb{E}\bigg{[}\bigg{|}S_{n,0}(f)-\mathbb{E}_{\pi}[f(X)]\bigg{|}\bigg{]}$
(196)
$\displaystyle\qquad\leq\sqrt{\mathbb{E}\bigg{[}\bigg{|}S_{n,0}(f)-\mathbb{E}_{\pi}[f(X)]\bigg{|}^{2}\bigg{]}}$
(197)
$\displaystyle\qquad\leq\sqrt{\frac{2M}{n(1-\lambda)}+\frac{64M^{2}}{n^{2}(1-\lambda)^{2}}\bigg{\|}\frac{dv}{d\pi}-1\bigg{\|}_{2}}$
(198) $\displaystyle\qquad=A_{n},$ (199)

where (199) follows from Lemma 27 with $n_{0}=0$.

By using $|a+b|\leq|a|+|b$, from (195) and (199), we obtain

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{F}}\big{]}$
$\displaystyle\qquad\leq\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-\mathbb{E}[f(X_{i})]\bigg{|}\bigg{]}+A_{n}.$
(200)

On the other hand, let $Y_{1},Y_{2},\cdots,Y_{n}$ is a replica of
$X_{1},X_{2},\cdots,X_{n}$. It holds that

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-\mathbb{E}[f(X_{i})]\bigg{|}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\mathbf{X}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-\mathbb{E}[f(Y_{i})]\bigg{|}\bigg{]}$
(201)
$\displaystyle\qquad=\mathbb{E}_{\mathbf{X}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\mathbb{E}_{\mathbf{Y}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-f(Y_{i})\bigg{]}\bigg{|}\bigg{]}$
(202)
$\displaystyle\qquad\leq\mathbb{E}_{\mathbf{X}}\bigg{[}\mathbb{E}_{\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-f(Y_{i})\bigg{|}\bigg{]}\bigg{]}.$
(203)

Now, by Lemma 25 and the triangle inequality for infinity norm, we have

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-f(Y_{i})\bigg{|}\bigg{]}=\mathbb{E}_{\varepsilon}\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\bigg{\|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(X_{i})-f(Y_{i})\big{)}\bigg{\|}_{\mathcal{F}}\bigg{]}$
(204)
$\displaystyle\qquad\leq\mathbb{E}_{\varepsilon}\mathbb{E}_{\mathbf{X}}\bigg{[}\bigg{\|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(X_{i})\big{)}\bigg{\|}_{\mathcal{F}}\bigg{]}+\mathbb{E}_{\varepsilon}\mathbb{E}_{\mathbf{Y}}\bigg{[}\bigg{\|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(Y_{i})\big{)}\bigg{\|}_{\mathcal{F}}\bigg{]}$
(205)
$\displaystyle\qquad=2\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]},$
(206)

where (206) follows from the fact that $\mathbf{Y}$ is a replica of
$\mathbf{X}$.

From (200) and (206), we finally obtain

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{F}}\big{]}\leq
2\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{F}}\big{]}+A_{n}.$ (207)

Now, by using the triangle inequality, we have

$\displaystyle\mathbb{E}[\|P_{n}^{0}\|_{\mathcal{F}}]$
$\displaystyle=\mathbb{E}_{\mathbf{X},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}f(X_{i})\bigg{|}\bigg{]}$
(208)
$\displaystyle\leq\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(X_{i})-\mathbb{E}_{\mathbf{Y}}\big{[}f(Y_{i})\big{]}\big{)}\bigg{|}+\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]}$
(209)
$\displaystyle=\mathbb{E}_{\mathbf{X},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\mathbb{E}_{\mathbf{Y}}\bigg{[}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(X_{i})-f(Y_{i})\big{)}\bigg{]}\bigg{|}\bigg{]}+\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]}$
(210)
$\displaystyle\leq\mathbb{E}_{\mathbf{X},\mathbf{Y},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(X_{i})-f(Y_{i})\big{)}\bigg{|}\bigg{]}+\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]}$
(211)
$\displaystyle=\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\big{(}f(X_{i})-f(Y_{i})\big{)}\bigg{|}\bigg{]}+\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]},$
(212)

where (212) follows from Lemma 25.

Now, we have

$\displaystyle\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\big{(}f(X_{i})-f(Y_{i})\big{)}\bigg{|}\bigg{]}$
$\displaystyle\qquad=\mathbb{E}_{\mathbf{X},\mathbf{Y}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\big{(}f(X_{i})-Pf\big{)}-\big{(}f(Y_{i})-Pf\big{)}\big{)}\bigg{|}\bigg{]}$
(213)
$\displaystyle\qquad\leq\mathbb{E}_{\mathbf{X},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-Pf\bigg{|}\bigg{]}+\mathbb{E}_{\mathbf{Y},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(Y_{i})-Pf\bigg{|}\bigg{]}$
(214)
$\displaystyle\qquad=2\mathbb{E}_{\mathbf{X},\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(X_{i})-Pf\bigg{|}\bigg{]}$
(215)
$\displaystyle\qquad=2\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{F}}\big{]}.$
(216)

On the other hand, by using the triangle inequality, we also have

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]}$
$\displaystyle\qquad\leq\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]-\mathbb{E}_{\pi}[f(Y)]\big{)}\bigg{|}\bigg{]}+\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\pi}[f(Y)]\bigg{|}\bigg{]}.$
(217)

Now, observe that

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\pi}[f(Y)]\bigg{|}\bigg{]}$
$\displaystyle\leq\bigg{(}\sup_{f\in\mathcal{F}}\big{|}\mathbb{E}_{\pi}[f(Y)]\big{|}\bigg{)}\mathbb{E}_{\bm{\varepsilon}}\bigg{[}\sum_{i=1}^{n}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\bigg{]}$
(218) $\displaystyle\leq
M\mathbb{E}_{\bm{\varepsilon}}\bigg{[}\sum_{i=1}^{n}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\bigg{]}$
(219) $\displaystyle\leq
M\sqrt{\mathbb{E}_{\bm{\varepsilon}}\bigg{[}\bigg{(}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\bigg{)}^{2}\bigg{]}}$
(220) $\displaystyle=\frac{M}{\sqrt{n}}.$ (221)

In addition, for each fixed
$(\varepsilon_{1},\varepsilon_{2},\cdots,\varepsilon_{n})\in\\{-1,+1\\}^{n}$
and $f\in\mathcal{F}$, we have

$\displaystyle\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]-\mathbb{E}_{\pi}[f(Y)]\big{)}\bigg{|}$
$\displaystyle\qquad\leq\frac{1}{n}\mathbb{E}_{\mathbf{Y}}\bigg{|}\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(Y_{i})-\mathbb{E}_{\pi}[f(Y)]\big{)}\bigg{|}$
(222)
$\displaystyle\qquad=\frac{1}{n}\mathbb{E}_{\mathbf{Y}}\big{[}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}\big{]},$
(223)

where

$\displaystyle
g_{\varepsilon}(\mathbf{y}):=\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(y_{i})-\mathbb{E}_{\pi}[f(Y)]\big{)},\qquad\forall\mathbf{y}\in\mathbb{R}^{n}.$
(224)

Now, for all $\mathbf{x},\mathbf{y}\in\mathbf{b}^{n}$, we have

$\displaystyle g_{\varepsilon}(\mathbf{x})-g_{\varepsilon}(\mathbf{y})$
$\displaystyle=\sum_{i=1}^{n}\varepsilon_{i}\big{(}f(x_{i})-f(y_{i})\big{)}$
(225) $\displaystyle\leq\sum_{i=1}^{n}|f(x_{i})-f(y_{i})|$ (226)
$\displaystyle\leq\sum_{i=1}^{n}2M\mathbf{1}\\{x_{i}\neq y_{i}\\}.$ (227)

Hence, by Lemma 28, we have

$\displaystyle\mathbb{P}_{\mathbf{Y}}\big{[}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}\geq
M\sqrt{2\tau_{\min}n\log n}\big{]}\leq\frac{2}{n}.$ (228)

It follows that

$\displaystyle\mathbb{E}_{\mathbf{Y}}\big{[}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}\big{]}$
$\displaystyle\leq\mathbb{E}_{\mathbf{Y}}\big{[}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}\big{|}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}<M\sqrt{2\tau_{\min}n\log
n}\big{]}$
$\displaystyle\qquad+2nM\mathbb{P}_{\mathbf{Y}}\big{[}\big{|}g_{\varepsilon}(\mathbf{Y})\big{|}\geq
M\sqrt{2\tau_{\min}n\log n}\big{]}$ (229) $\displaystyle\leq
M\sqrt{2\tau_{\min}n\log n}+2nM\bigg{(}\frac{2}{n}\bigg{)}$ (230)
$\displaystyle=M\sqrt{2\tau_{\min}n\log n}+4M,$ (231)

where (229) follows from the total law of expectation and
$|g_{\varepsilon}(\mathbf{y})|\leq\sum_{i=1}^{n}\big{|}f(y_{i})-\mathbb{E}_{\pi}[f(Y)]\big{|}\leq
2nM$ for all $\mathbf{y}\in\mathbb{R}^{n}$.

From (223) and (231), we have

$\displaystyle\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]-\mathbb{E}_{\pi}[f(Y)]\big{)}\bigg{|}\leq\frac{1}{n}\bigg{(}M\sqrt{2\tau_{\min}n\log
n}+4M\bigg{)}$ (232)

for all
$f\in\mathcal{F},(\varepsilon_{1},\varepsilon_{2},\cdots,\varepsilon_{n})\in\\{-1,+1\\}^{n}$.

From (232), we obtain

$\displaystyle\mathbb{E}_{\bm{\varepsilon}}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\big{(}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]-\mathbb{E}_{\pi}[f(Y)]\big{)}\bigg{|}\bigg{]}\leq\frac{1}{n}\bigg{(}M\sqrt{2\tau_{\min}n\log
n}+4M\bigg{)}.$ (233)

From (217), (221), and (233), we have

$\displaystyle\mathbb{E}\bigg{[}\sup_{f\in\mathcal{F}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}\varepsilon_{i}\mathbb{E}_{\mathbf{Y}}[f(Y_{i})]\bigg{|}\bigg{]}$
$\displaystyle\qquad\leq\frac{1}{n}\bigg{(}M\sqrt{2\tau_{\min}n\log
n}+4M\bigg{)}+\frac{M}{\sqrt{n}}.$ (234)

From (212), (216), and (234), we obtain

$\displaystyle\mathbb{E}[\|P_{n}^{0}\|_{\mathcal{F}}]\leq
2\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{F}}\big{]}+\frac{1}{n}\bigg{(}M\sqrt{2\tau_{\min}n\log
n}+4M\bigg{)}+\frac{M}{\sqrt{n}},$ (235)

and we finally have

$\displaystyle\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{F}}\big{]}\geq\frac{1}{2}\mathbb{E}[\|P_{n}^{0}\|_{\mathcal{F}}]-\tilde{A}_{n}.$
(236)

∎

##  Appendix B Proof of Theorem 9

The proof of Theorem 9 is based on [4]. First, we prove (55). Without loss of
generality, we can assume that each $\varphi\in\Phi$ takes its values in
$[0,1]$ (otherwise, it can be redefined as $\varphi\wedge 1$). Then, it is
clear that $\varphi(x)=1$ for $x\leq 0$. Hence, for each fixed
$\varphi\in\Phi$ and $f\in\mathcal{F}$, we obtain

$\displaystyle P\\{f\leq 0\\}$ $\displaystyle\leq P\varphi(f)$ (237)
$\displaystyle\leq P_{n}\varphi(f)+\|P_{n}-P\|_{\mathcal{G}_{\varphi}},$ (238)

where

$\displaystyle\mathcal{G}_{\varphi}:=\big{\\{}\varphi\cdot
f:f\in\mathcal{F}\big{\\}}.$ (239)

Now, let
$g(\mathbf{x})=\sup_{f\in\mathcal{G}_{\varphi}}\big{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-Pf\big{|}$.
Then, for all $\mathbf{x}\neq\mathbf{y}$, we have

$\displaystyle\big{|}g(\mathbf{x})-g(\mathbf{y})\big{|}$
$\displaystyle=\bigg{|}\sup_{f\in\mathcal{G}_{\varphi}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-Pf\bigg{|}-\sup_{f\in\mathcal{G}_{\varphi}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(y_{i})-Pf\bigg{|}\bigg{|}$
(240)
$\displaystyle\leq\sup_{f\in\mathcal{G}_{\varphi}}\bigg{|}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-Pf\bigg{|}-\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(y_{i})-Pf\bigg{|}\bigg{|}$
(241)
$\displaystyle\leq\sup_{f\in\mathcal{G}_{\varphi}}\bigg{|}\bigg{(}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-Pf\bigg{)}-\bigg{(}\frac{1}{n}\sum_{i=1}^{n}f(y_{i})-Pf\bigg{)}\bigg{|}$
(242)
$\displaystyle\leq\sup_{f\in\mathcal{G}_{\varphi}}\bigg{|}\frac{1}{n}\sum_{i=1}^{n}f(x_{i})-f(y_{i})\bigg{|}$
(243)
$\displaystyle\leq\sup_{f\in\mathcal{G}_{\varphi}}\frac{1}{n}\sum_{i=1}^{n}\big{|}f(x_{i})-f(y_{i})\big{|}$
(244) $\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\mathbf{1}\\{x_{i}\neq
y_{i}\\}.$ (245)

Hence, for $t>0$, by Lemma 28 with we have

$\displaystyle\mathbb{P}\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}_{\varphi}}\geq\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{G}_{\varphi}}\big{]}+t\sqrt{\frac{\tau_{\min}}{n}}\bigg{\\}}\leq
2\exp\big{(}-2t^{2}\big{)}.$ (246)

Hence, with probability at least $1-2\exp\big{(}-2t^{2}\big{)}$ for all
$f\in\mathcal{F}$

$\displaystyle P\\{f\leq 0\\}\leq
P_{n}\varphi(f)+\mathbb{E}[\|P_{n}-P\|_{\mathcal{G}_{\varphi}}]+t\sqrt{\frac{\tau_{\min}}{n}}.$
(247)

Now, by Lemma 8 with $M=1$ (since
$\sup_{f\in\mathcal{G}_{\varphi}}\|f\|_{\infty}=1$), it holds that

$\displaystyle\mathbb{E}\bigg{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{\varphi}}\bigg{]}$
$\displaystyle\leq
2\mathbb{E}\big{[}\|P_{n}^{0}\big{\|}_{\mathcal{G}_{\varphi}}\big{]}+A_{n}\big{|}_{M=1}$
(248)
$\displaystyle=2\mathbb{E}\bigg{[}\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}\bigg{]}+B_{n}.$
(249)

Since $(\varphi-1)/L(\varphi)$ is contractive and $\varphi(0)-1=0$, by using
Talagrand’s contraction lemma [30, 31], we obtain

$\displaystyle\mathbb{E}_{\varepsilon}\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}$
$\displaystyle\leq
2L(\varphi)\mathbb{E}_{\varepsilon}\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}$
(250) $\displaystyle=2L(\varphi)R_{n}(\mathcal{F}).$ (251)

From (246), (247), (249), and (251), with probability
$1-2\exp\big{(}-2t^{2}\big{)}$, we have for all $f\in\mathcal{F}$,

$\displaystyle P\\{f\leq 0\\}\leq
P_{n}\varphi(f)+4L(\varphi)R_{n}(\mathcal{F})+t\sqrt{\frac{\tau_{\min}}{n}}+B_{n}.$
(252)

Now, we use (252) with $\varphi=\varphi_{k}$ and $t$ is replaced by
$t+\sqrt{\log k}$ to obtain

$\displaystyle\mathbb{P}\bigg{(}\exists f\in\mathcal{F}:P\\{f\leq
0\\}>\inf_{k>0}\bigg{[}P_{n}\varphi_{k}(f)+4L(\varphi_{k})R_{n}(\mathcal{F})+\big{(}t+\sqrt{\log
k}\big{)}\sqrt{\frac{\tau_{\min}}{n}}+B_{n}\bigg{]}\bigg{)}$
$\displaystyle\qquad\leq 2\sum_{k=1}^{\infty}\exp\big{(}-2\big{(}t+\sqrt{\log
k}\big{)}^{2}\big{)}$ (253) $\displaystyle\qquad\leq
2\sum_{k=1}^{\infty}k^{-2}\exp\big{(}-2t^{2}\big{)}$ (254)
$\displaystyle\qquad=\frac{\pi^{2}}{3}\exp\big{(}-2t^{2}\big{)},$ (255)

where (255) follows from

$\displaystyle\frac{\pi^{2}}{6}=\sum_{k=1}^{\infty}k^{-2}.$ (256)

Next, we prove (56). By the equivalence of Rademacher and Gaussian complexity
[32], we have

$\displaystyle\mathbb{E}\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}\leq\sqrt{\frac{\pi}{2}}\mathbb{E}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}.$
(257)

Hence, from (249) and (257), we obtain

$\displaystyle\mathbb{E}\bigg{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{\varphi}}\bigg{]}$
$\displaystyle\leq\sqrt{2\pi}\mathbb{E}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}+B_{n}.$
(258)

Now, define Gaussian processes

$\displaystyle Z_{1}(f,\sigma):=\sigma
n^{-1/2}\sum_{i=1}^{n}g_{i}(\varphi\circ f)(X_{i}),$ (259)

and

$\displaystyle
Z_{2}(f,\sigma):=L(\varphi)n^{-1/2}\sum_{i=1}^{n}g_{i}f(X_{i})+\sigma g,$
(260)

where $\sigma=\pm 1$ and $g$ is standard normal independent of the sequence
$\\{g_{i}\\}$. Let $\mathbb{E}_{g}$ be the expectation on the probability
space $(\Omega_{g},\Sigma_{g},\mathbb{P}_{g})$ on which the sequence
$\\{g_{i}\\}$ and $g$ are defined, then by [30, 4], we have

$\displaystyle\mathbb{E}_{g}\bigg{[}\sup\\{Z_{1}(f,\sigma):f\in\mathcal{F},\sigma=\pm
1\\}\bigg{]}\leq\mathbb{E}_{g}\bigg{[}\sup\\{Z_{2}(f,\sigma):f\in\mathcal{F},\sigma=\pm
1\\}\bigg{]}.$ (261)

On the other hand, it holds that

$\displaystyle\mathbb{E}_{g}\bigg{\|}n^{-1/2}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}$
$\displaystyle=\mathbb{E}_{g}\bigg{[}n^{-1/2}\sup_{h\in\bar{\mathcal{G}}_{\varphi}}\sum_{i=1}^{n}g_{i}h(X_{i})\bigg{]}$
(262)
$\displaystyle=\mathbb{E}_{g}\bigg{[}\sup\\{Z_{1}(f,\sigma):f\in\mathcal{F},\sigma=\pm
1\\}\bigg{]},$ (263)

where
$\bar{\mathcal{G}}_{\varphi}:=\\{\varphi(f),-\varphi(f):f\in\mathcal{F}\\}$,
and similarly

$\displaystyle
L(\varphi)\mathbb{E}_{g}\bigg{\|}n^{-1/2}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}+\mathbb{E}|g|\geq\mathbb{E}_{g}\bigg{[}\sup\\{Z_{2}(f,\sigma):f\in\mathcal{F},\sigma=\pm
1\\}\bigg{]}.$ (264)

From (261), (263), and (264), we have

$\displaystyle\mathbb{E}_{g}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{\varphi}}\leq
L(\varphi)\mathbb{E}_{g}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}+n^{-1/2}\mathbb{E}|g|.$
(265)

By combining (258) and (265), we obtain

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{\varphi}}\big{]}$
$\displaystyle\qquad\leq\sqrt{2\pi}\bigg{(}L(\varphi)\mathbb{E}\bigg{[}\bigg{\|}n^{-1}\sum_{i=1}^{n}g_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{F}}\bigg{]}+n^{-1/2}\mathbb{E}|g|\bigg{)}+B_{n}.$
(266)

Hence, from (247), (258), and (266), we finally obtain (56).

##  Appendix C Proof of Theorem 10

We can assume, without loss of generality, that the range of $\varphi$ is
$[0,1]$ (otherwise, we can replace $\varphi$ by $\varphi\wedge 1$). Let
$\delta_{k}=2^{-k}$ for all $k\geq 0$. In addition, set
$\Phi=\\{\varphi_{k}:k\geq 1\\}$, where

$\displaystyle\varphi_{k}(x):=\begin{cases}\varphi(x/\delta_{k}),&x\geq 0,\\\
\varphi(x/\delta_{k-1}),&x<0\end{cases}.$ (267)

Now, for any $\delta\in(0,1]$, there exists $k$ such that
$\delta\in(\delta_{k},\delta_{k-1}]$. Hence, if $f(X_{i})\geq 0$, it holds
that $f(X_{i})/\delta_{k}\geq f(X_{i})/\delta$, so we have

$\displaystyle\varphi_{k}(f(X_{i}))$
$\displaystyle=\varphi\bigg{(}\frac{f(X_{i})}{\delta_{k}}\bigg{)}$ (268)
$\displaystyle\leq\varphi\bigg{(}\frac{f(X_{i})}{\delta}\bigg{)},$ (269)

where (269) follows from the fact that $\varphi(\cdot)$ is non-increasing.

On the other hand, if $f(X_{i})<0$, then $f(X_{i})/\delta_{k-1}\geq
f(X_{i})/\delta$. Hence, we have

$\displaystyle\varphi_{k}(f(X_{i}))$
$\displaystyle=\varphi\bigg{(}\frac{f(X_{i})}{\delta_{k-1}}\bigg{)}$ (270)
$\displaystyle\leq\varphi\bigg{(}\frac{f(X_{i})}{\delta}\bigg{)},$ (271)

where (269) follows from the fact that $\varphi(\cdot)$ is non-increasing.

From (269) and (271), we have

$\displaystyle P_{n}\varphi_{k}\big{(}f\big{)}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\varphi_{k}(f(X_{i}))$ (272)
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\varphi\bigg{(}\frac{f(X_{i})}{\delta}\bigg{)}$
(273) $\displaystyle=P_{n}\varphi\bigg{(}\frac{f}{\delta}\bigg{)}.$ (274)

Moreover, we also have

$\displaystyle\frac{1}{\delta_{k}}$ $\displaystyle\leq\frac{2}{\delta},$ (275)

and

$\displaystyle\log
k=\log\log_{2}\frac{1}{\delta_{k}}\leq\log\log_{2}2\delta^{-1}.$ (276)

Furthermore, observe that

$\displaystyle L(\varphi_{k})$
$\displaystyle=\sup_{x\in\mathbb{R}}\bigg{|}\frac{d\varphi_{k}(x)}{dx}\bigg{|}$
(277)
$\displaystyle=\sup_{x\in\mathbb{R}}\bigg{|}\frac{d\varphi(x/\delta_{k})}{dx}\bigg{|}\mathbf{1}\\{x\geq
0\\}+\bigg{|}\frac{d\varphi(x/\delta_{k-1})}{dx}\bigg{|}\mathbf{1}\\{x<0\\}$
(278) $\displaystyle\leq\frac{L(\varphi)}{\min\\{\delta_{k},\delta_{k-1}\\}}$
(279) $\displaystyle=\frac{L(\varphi)}{\delta_{k}}$ (280)
$\displaystyle\leq\frac{2}{\delta}L(\varphi).$ (281)

By combining the above facts and using Theorem 9, we obtain (57) and (58).

##  Appendix D Proof of Theorem 13

Let $\varepsilon>0$ and $\delta>0$. Define recursively

$\displaystyle r_{0}:=1,\qquad r_{k+1}=C\sqrt{r_{k}\varepsilon}\wedge
1,\qquad\gamma_{k}:=\sqrt{\frac{\varepsilon}{r_{k}}}$ (282)

some sufficiently large constant $C>1$ (to be determined later) such that
$\varepsilon<C^{-4}$. Denote by

$\displaystyle\delta_{0}$ $\displaystyle:=\delta,$ (283)
$\displaystyle\delta_{k}$
$\displaystyle:=\delta(1-\gamma_{0}-\cdots-\gamma_{k-1}),$ (284)
$\displaystyle\delta_{k,\frac{1}{2}}$
$\displaystyle:=\frac{1}{2}\big{(}\delta_{k}+\delta_{k+1}\big{)},\qquad k\geq
1.$ (285)

For $k\geq 0$, let $\varphi_{k}$ be a continuous function from $\mathbb{R}$
into $[0,1]$ such that $\varphi_{k}(u)=1$ for
$u\leq\delta_{k,\frac{1}{2}},\varphi_{k}(u)=0$ for $u\geq\delta_{k}$, and
linear $\delta_{k,\frac{1}{2}}\leq u\leq\delta_{k}$. For $k\geq 1$ let
$\varphi^{\prime}_{k}$ be a continuous function from $\mathbb{R}$ into $[0,1]$
such that $\varphi^{\prime}_{k}(u)=1$ for $u\leq\delta_{k}$,
$\varphi^{\prime}_{k}(u)=0$ for $u\geq\delta_{k-1,\frac{1}{2}}$, and linear
for $\delta_{k}\leq u\leq\delta_{k-1,\frac{1}{2}}$.

To begin with, we prove the following lemma.

######  Lemma 29.

Define $\mathcal{F}_{0}:=\mathcal{F}$, and further recursively

$\displaystyle\mathcal{F}_{k+1}:=\bigg{\\{}f\in\mathcal{F}_{k}:P\\{f\leq\delta_{k,\frac{1}{2}}\\}\leq\frac{r_{k+1}}{2}\bigg{\\}}.$
(286)

For all $k\geq 1$, define

$\displaystyle\mathcal{G}_{k}:=\big{\\{}\varphi_{k}\circ
f:f\in\mathcal{F}_{k}\big{\\}},\qquad k\geq 0$ (287)

and

$\displaystyle\mathcal{G}^{\prime}_{k}:=\big{\\{}\varphi^{\prime}_{k}\circ
f:f\in\mathcal{F}_{k}\big{\\}},\qquad k\geq 1.$ (288)

Assume that

$\displaystyle E^{(k)}$
$\displaystyle:=\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\leq\mathbb{E}\|P_{n}-P\|_{\mathcal{G}_{k-1}}+\big{(}K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}\bigg{\\}}$
$\displaystyle\qquad\cap\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k}}\leq\mathbb{E}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k}}+\big{(}K_{2}\sqrt{r_{k}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}\bigg{\\}},\qquad
k\geq 1,$ (289)

and

$\displaystyle E_{N}:=\bigcap_{k=1}^{N}E^{(k)},\qquad N\geq 1.$ (290)

Then, it holds that

$\displaystyle\mathbb{P}\big{[}E_{N}^{c}\big{]}\leq
4N\exp\bigg{(}-\frac{n\varepsilon^{2}}{2}\bigg{)}.$ (291)

###### Proof.

The proof is based on [4, Proof of Theorem 5].

For the case $C\sqrt{\varepsilon}\geq 1$, by a simple induction argument, we
have $r_{k}=1$. Now, without loss of generality, we assume that
$C\sqrt{\varepsilon}<1$. For this case, we have

$\displaystyle r_{k}$
$\displaystyle=C^{1+2^{-1}+\cdots+2^{-(k-1)}}\varepsilon^{2^{-1}+\cdots+2^{-(k-1)}}$
(292) $\displaystyle=C^{2(1-2^{-k})}\varepsilon^{1-2^{-k}}$ (293)
$\displaystyle=(C\sqrt{\varepsilon})^{2(1-2^{-k})}.$ (294)

From (294), it is easy to see that $r_{k+1}<r_{k}$ for any $k\geq 0$.

Now, observe that

$\displaystyle\sum_{i=0}^{k}\gamma_{i}$
$\displaystyle=C^{-1}\bigg{[}C\sqrt{\varepsilon}+(C\sqrt{\varepsilon})^{2^{-1}}+\cdots+(C\sqrt{\varepsilon})^{2^{-k}}\bigg{]}$
(295)
$\displaystyle=C^{-1}\bigg{[}(C\sqrt{\varepsilon})^{2^{-k}}+((C\sqrt{\varepsilon})^{2^{-k}})^{2}+((C\sqrt{\varepsilon})^{2^{-k}})^{2^{2}}\cdots+((C\sqrt{\varepsilon})^{2^{-k}})^{2^{k}}\bigg{]}$
(296) $\displaystyle\leq
C^{-1}\bigg{[}(C\sqrt{\varepsilon})^{2^{-k}}+((C\sqrt{\varepsilon})^{2^{-k}})^{2}+((C\sqrt{\varepsilon})^{2^{-k}})^{3}\cdots+((C\sqrt{\varepsilon})^{2^{-k}})^{k}\bigg{]}$
(297) $\displaystyle\leq
C^{-1}\sum_{i=1}^{\infty}\big{(}(C\sqrt{\varepsilon})^{2^{-k}}\big{)}^{i}$
(298) $\displaystyle\leq
C^{-1}(C\sqrt{\varepsilon})^{2^{-k}}\big{(}1-(C\sqrt{\varepsilon})^{2^{-k}}\big{)}^{-1}\leq\frac{1}{2},$
(299)

for $\varepsilon\leq C^{-4},C>2(2^{\frac{1}{4}}-1)^{-1}$ and
$k\leq\log_{2}\log_{2}\varepsilon^{-1}$, where (297) follows from $i+1\leq
2^{i}$ for all $i\geq 1$ and $C\sqrt{\varepsilon}<1$. Hence, for small enough
$\varepsilon$ (note that our choice of $\varepsilon\leq C^{-4}$ implies
$C\sqrt{\varepsilon}<1$), we have

$\displaystyle\gamma_{0}+\gamma_{1}+\cdots+\gamma_{k}\leq\frac{1}{2},\qquad
k\geq 1.$ (300)

Therefore, for all $k\geq 1$, we get $\delta_{k}\in(\delta/2,\delta)$. Note
also that below our choice of $k$ will be such that the restriction
$k\leq\log_{2}\log_{2}\varepsilon^{-1}$ for any fixed $\varepsilon>0$ will
always be fulfilled.

From the definitions of (287) and (288), for $k\geq 1$, we have

$\displaystyle\sup_{g\in\mathcal{G}_{k}}Pg^{2}\leq\sup_{f\in\mathcal{F}_{k}}P\\{f\leq\delta_{k}\\}\leq\sup_{f\in\mathcal{F}_{k}}P\\{f\leq\delta_{k-1,\frac{1}{2}}\\}\leq\frac{r_{k}}{2}\leq
r_{k},$ (301)

and

$\displaystyle\sup_{g\in\mathcal{G}^{\prime}_{k}}Pg^{2}\leq\sup_{f\in\mathcal{F}_{k}}P\\{f\leq\delta_{k-1,\frac{1}{2}}\\}\leq\frac{r_{k}}{2}\leq
r_{k}.$ (302)

Since $r_{0}=1$, it is easy to see that (301) and (302) trivially holds at
$k=0$.

Now, by the union bound, from (289), we have

$\displaystyle\mathbb{P}\big{[}\big{(}E^{(k)}\big{)}^{c}\big{]}$
$\displaystyle\leq\mathbb{P}\bigg{[}\|P_{n}-P\|_{\mathcal{G}_{k-1}}>\mathbb{E}\|P_{n}-P\|_{\mathcal{G}_{k-1}}+K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\bigg{]}$
$\displaystyle\qquad+\mathbb{P}\bigg{[}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k-1}}>\mathbb{E}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k-1}}+K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\bigg{]}.$
(303)

In addition, by similar arguments which leads to (246), we have

$\displaystyle\mathbb{P}\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\geq\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\big{]}+u\sqrt{\frac{\tau_{\min}}{n}}\bigg{\\}}\leq
2\exp\big{(}-2u^{2}\big{)}.$ (304)

and

$\displaystyle\mathbb{P}\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k-1}}\geq\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k-1}}\big{]}+u\sqrt{\frac{\tau_{\min}}{n}}\bigg{\\}}\leq
2\exp\big{(}-2u^{2}\big{)}.$ (305)

By replacing
$u=\big{(}K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{n}$ to
(304) and (305) for $K_{2}>0$ and $K_{3}>0$, we obtain

$\displaystyle\mathbb{P}\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\geq\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\big{]}+\big{(}K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}\bigg{\\}}$
$\displaystyle\qquad\leq
2\exp\bigg{(}-2n(K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3})^{2}\bigg{)}$ (306)

and

$\displaystyle\mathbb{P}\bigg{\\{}\|P_{n}-P\|_{\mathcal{G}_{k-1}}\geq\mathbb{E}\big{[}\|P_{n}-P\|_{\mathcal{G}^{\prime}_{k-1}}\big{]}+\big{(}K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}\bigg{\\}}$
$\displaystyle\qquad\leq
2\exp\bigg{(}-2n(K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon)^{2}\bigg{)}.$
(307)

Now, since $0<C\sqrt{\varepsilon}\leq 1$, by (294), we have

$\displaystyle r_{k-1}=(C\sqrt{\varepsilon})^{2(1-2^{-(k-1)})}\geq
C^{2}\varepsilon.$ (308)

Hence, from (303), (306), (307), and (308), that

$\displaystyle\mathbb{P}\big{[}\big{(}E^{(k)}\big{)}^{c}\big{]}$
$\displaystyle\leq
4\exp\bigg{(}-2n(K_{2}\sqrt{r_{k-1}\varepsilon}+K_{3}\varepsilon)^{2}\bigg{)}$
(309) $\displaystyle\qquad\leq
4\exp\bigg{(}-2n(K_{2}C+K_{3})^{2}\varepsilon^{2}\bigg{)}$ (310)
$\displaystyle\qquad\leq
4\exp\bigg{(}-\frac{n\varepsilon^{2}}{2}\bigg{)},\qquad\forall k\geq 1$ (311)

if we choose $K_{2}$ and $K_{3}$ such that

$\displaystyle K_{2}C+K_{3}\geq\frac{1}{2}.$ (312)

Then, by the union bound and (311), we have

$\displaystyle\mathbb{P}\big{[}E_{N}^{c}\big{]}\leq
4N\exp\bigg{(}-\frac{n\varepsilon^{2}}{2}\bigg{)}.$ (313)

∎

######  Lemma 30.

Let $\varepsilon>0$ and $0<\alpha<2$ such that

$\displaystyle\varepsilon\geq\bigg{(}\frac{1}{n\delta^{\alpha}}\bigg{)}^{\frac{2}{2+\alpha}}\vee\sqrt{\frac{2\log
n}{n}}\vee B_{n}$ (314)

for all large enough $n$, where $B_{n}$ is defined in (54). Denote by
$\mathcal{L}:=\big{\\{}f\in\mathcal{F}:P_{n}\\{f\leq\delta\\}\leq\varepsilon\\}$.
Then, on the event $E_{N}\cap\mathcal{L}$, we have:

  * •

(i) $\sup_{f\in\mathcal{F}_{k}}P_{n}\\{f\leq\delta_{k}\\}\leq r_{k}$, $0\leq
k\leq N$

and

  * •

(ii) $\forall f\in\mathcal{L}$
$P_{n}\\{f\leq\delta\\}\leq\varepsilon\qquad\Rightarrow f\in\mathcal{F}_{N}$

for all positive integer $N$ satisfying

$\displaystyle
N\leq\frac{1}{\eta}\log_{2}\log_{2}\varepsilon^{-1}\qquad\mbox{and}\qquad
r_{N}\geq\varepsilon,$ (315)

and $\eta$ is some implicit positive constant.

###### Proof.

We will use induction with respect to $N$. For $N=0$, the statement is
obvious. Suppose it holds for some $N\geq 0$, such that $N+1$ still satisfies
condition (315) of the lemma. Then, on the event $E_{N}\cap\mathcal{L}$ we
have

$\displaystyle(i)\qquad\sup_{f\in\mathcal{F}_{k}}P_{n}\\{f\leq\delta_{k}\\}\leq
r_{k},\qquad 0\leq k\leq N$ (316)

and

$\displaystyle(ii)\qquad\forall f\in\mathcal{F}\quad
P_{n}\\{f\leq\delta\\}\leq\varepsilon\quad\Rightarrow f\in\mathcal{F}_{N}.$
(317)

Suppose now that $f\in\mathcal{F}$ is such that
$P_{n}\\{f\leq\delta\\}\leq\varepsilon$. By the induction assumptions, on the
event $E_{N}$ defined in (290), we have $f\in\mathcal{F}_{N}$. Because of
this, we obtain on the event $E_{N+1}$

$\displaystyle P\\{f\leq\delta_{N,\frac{1}{2}}\\}$
$\displaystyle=P_{n}\\{f\leq\delta_{N,\frac{1}{2}}\\}+(P-P_{n})\\{f\leq\delta_{N,\frac{1}{2}}\\}$
(318) $\displaystyle\leq
P_{n}\\{f\leq\delta_{N}\\}+(P-P_{n})\\{f\leq\delta_{N,\frac{1}{2}}\\}$ (319)
$\displaystyle\leq P_{n}\\{f\leq\delta_{N}\\}+(P-P_{n})(\varphi_{N}(f))$ (320)
$\displaystyle\leq P_{n}\\{f\leq\delta_{N}\\}+\|P-P_{n}\|_{\mathcal{G}_{N}}$
(321)
$\displaystyle\leq\varepsilon+\mathbb{E}\|P_{n}-P\|_{\mathcal{G}_{N}}+\big{(}K_{2}\sqrt{r_{N}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}.$
(322)

For the class $\mathcal{G}_{N}$, define

$\displaystyle\hat{R}_{n}(\mathcal{G}_{N}):=\bigg{\|}n^{-1}\sum_{i=1}^{n}\varepsilon_{i}\delta_{X_{i}}\bigg{\|}_{\mathcal{G}_{N}},$
(323)

where $\varepsilon_{i}$ is a sequence of i.i.d. Rademacher random variables.
By Lemma 8, it holds that

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{N}}\big{]}$
$\displaystyle\leq
2\mathbb{E}\big{[}\|P_{n}^{0}\|_{\mathcal{G}_{N}}\big{]}+B_{n}$ (324)
$\displaystyle=2\mathbb{E}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}+B_{n}.$
(325)

From (325), we have

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{N}}\big{]}$
$\displaystyle\qquad\leq
2\mathbb{E}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}+B_{n}$ (326)
$\displaystyle\qquad=2\mathbb{E}\big{[}\mathbf{1}\\{E_{N}\\}\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\big{]}+2\mathbb{E}\big{[}\mathbf{1}\\{E_{N}^{c}\\}\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\big{]}+B_{n}.$
(327)

Next, by the well-known entropy inequalities for subgaussian process [32], we
have

$\displaystyle\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}$
$\displaystyle\leq\inf_{g\in\mathcal{G}_{N}}\mathbb{E}_{\varepsilon}\bigg{|}n^{-1}\sum_{j=1}^{n}\varepsilon_{j}g(X_{j})\bigg{|}$
$\displaystyle\qquad+\frac{\eta}{\sqrt{n}}\int_{0}^{(2\sup_{g\in\mathcal{G}_{N}}P_{n}g^{2})^{1/2}}H_{d_{P_{n},2}}^{1/2}(\mathcal{G}_{N};u)du$
(328)

for some implicit positive constant $\eta>0$.

By the induction assumption, on the event $E_{N}\cap\mathcal{L}$,

$\displaystyle\inf_{g\in\mathcal{G}_{N}}\mathbb{E}_{\varepsilon}\bigg{|}n^{-1}\sum_{j=1}^{n}\varepsilon_{j}g(X_{j})\bigg{|}$
$\displaystyle\leq\inf_{g\in\mathcal{G}_{N}}\sqrt{\mathbb{E}_{\varepsilon}\bigg{|}n^{-1}\sum_{j=1}^{n}\varepsilon_{j}g(X_{j})\bigg{|}^{2}}$
(329)
$\displaystyle\leq\frac{1}{\sqrt{n}}\inf_{g\in\mathcal{G}_{N}}\sqrt{P_{n}g^{2}}$
(330)
$\displaystyle\leq\frac{1}{\sqrt{n}}\inf_{f\in\mathcal{F}_{N}}\sqrt{P_{n}\\{f\leq\delta_{N}\\}}$
(331) $\displaystyle\leq\sqrt{\frac{\varepsilon}{n}}$ (332)
$\displaystyle\leq\varepsilon,$ (333)

where (332) follows from
$\inf_{f\in\mathcal{F}_{N}}P_{n}\\{f\leq\delta_{N}\\}\leq\inf_{f\in\mathcal{F}_{N}}P_{n}\\{f\leq\delta\\}\leq
P_{n}\\{f\leq\delta\\}\leq\varepsilon$ by the induction assumption with
$f\in\mathcal{F}_{N}$.

We also have on the event $E_{N}\cap\mathcal{L}$, by (301), it holds that

$\displaystyle\sup_{g\in\mathcal{G}_{N}}P_{n}g^{2}\leq\sup_{f\in\mathcal{F}_{N}}P_{n}\\{f\leq\delta_{N}\\}\leq
r_{N}.$ (334)

The Lipschitz norm of $\varphi_{k-1}$ and $\varphi^{\prime}_{k}$ is bounded by

$\displaystyle
L=2(\delta_{k-1}-\delta_{k})^{-1}=2\delta^{-1}\gamma_{k-1}^{-1}=\frac{2}{\delta}\sqrt{\frac{r_{k-1}}{\varepsilon}}$
(335)

which implies the following bound on the distance:

$\displaystyle d_{P_{n},2}^{2}(\varphi_{N}\circ f;\varphi_{N}\circ g)$
$\displaystyle=n^{-1}\sum_{j=1}^{n}\big{|}\varphi_{N}(f(X_{j}))-\varphi_{N}(g(X_{j}))\big{|}^{2}$
(336)
$\displaystyle\leq\bigg{(}\frac{2}{\delta}\sqrt{\frac{r_{N}}{\varepsilon}}\bigg{)}^{2}d_{P_{n},2}^{2}(f,g).$
(337)

Therefore, on the event $\mathcal{E}_{N}\cap\mathcal{L}$,

$\displaystyle\frac{1}{\sqrt{n}}\int_{0}^{(2\sup_{g\in\mathcal{G}_{N}}P_{n}g^{2})^{1/2}}H_{d_{P_{n}},2}^{1/2}\big{(}\mathcal{G}_{N};u\big{)}du$
$\displaystyle\qquad\leq\frac{1}{\sqrt{n}}\int_{0}^{(2r_{N})^{1/2}}H_{d_{P_{n}},2}^{1/2}\bigg{(}\mathcal{F};\frac{\delta\sqrt{\varepsilon}u}{2\sqrt{r_{N}}}\bigg{)}du$
(338)
$\displaystyle\qquad\leq\bigg{(}\frac{2\sqrt{D}}{1-\alpha/2}\bigg{)}\bigg{(}\frac{r_{N}}{\varepsilon}\bigg{)}^{\alpha/4}\frac{r_{N}^{1/2-\alpha/4}}{\sqrt{n}\delta^{\alpha/2}}$
(339)
$\displaystyle\qquad\leq\bigg{(}\frac{2^{1/2+\alpha/4}\sqrt{D}}{1-\alpha/2}\bigg{)}\frac{r_{N}^{1/2}}{\varepsilon^{\alpha/4}}\varepsilon^{\frac{2+\alpha}{4}}$
(340)
$\displaystyle\qquad=\bigg{(}\frac{2^{1/2+\alpha/4}\sqrt{D}}{1-\alpha/2}\bigg{)}\sqrt{r_{N}\varepsilon},$
(341)

where (341) follows from the condition (314), which implies that

$\displaystyle\frac{1}{n^{1/2}\delta^{\alpha/2}}\leq\varepsilon^{\frac{2+\alpha}{4}}.$
(342)

From (328) and (341), we obtain that on the event $E_{N}\cap\mathcal{L}$,

$\displaystyle\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\leq\varepsilon+\frac{2^{1/2+\alpha/4}\eta\sqrt{D}}{1-\alpha/2}\sqrt{r_{N}\varepsilon}.$
(343)

On the other hand, we also have

$\displaystyle\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\leq
1.$ (344)

Hence, by combining with (343) and (344), from (327), we obtain

$\displaystyle\mathbb{E}\big{[}\big{(}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{N}}\big{)}\big{]}$
$\displaystyle=2\mathbb{E}\big{[}\mathbf{1}\\{E_{N}\\}\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\big{]}+2\mathbb{E}\big{[}\mathbf{1}\\{E_{N}^{c}\\}\mathbb{E}_{\varepsilon}\big{[}\hat{R}_{n}(\mathcal{G}_{N})\big{]}\big{]}+B_{n}$
(345) $\displaystyle\qquad\leq
2\bigg{[}\varepsilon+\eta\bigg{(}\frac{2^{1/2+\alpha/4}\eta\sqrt{D}}{1-\alpha/2}\bigg{)}\sqrt{r_{N}\varepsilon}\bigg{]}+8N\exp\bigg{(}-\frac{n\varepsilon^{2}}{2}\bigg{)}+B_{n}.$
(346)

Now, by the condition (314), it holds that

$\displaystyle\varepsilon\geq B_{n},$ (347)

and

$\displaystyle 8\eta N\exp\bigg{(}-\frac{n\varepsilon^{2}}{2}\bigg{)}$
$\displaystyle\leq\frac{8\eta N}{n}$ (348)
$\displaystyle\leq\frac{8\log_{2}\log_{2}\varepsilon^{-1}}{n}$ (349)
$\displaystyle\leq\frac{8\log_{2}\log_{2}\sqrt{\frac{n}{2\log n}}}{n}$ (350)
$\displaystyle\leq\eta\sqrt{\frac{2\log n}{n}}$ (351)
$\displaystyle\leq\eta\varepsilon,$ (352)

for $n$ sufficiently large, where (348) and (350) follows from
$\varepsilon\geq\sqrt{\frac{2\log n}{n}}$, (349) follows from (315), and (351)
holds for $n$ sufficiently large.

From (346), (347), and (352), it holds that

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{N}}\big{]}$
$\displaystyle\leq
2\bigg{[}\varepsilon+\eta\bigg{(}\frac{2^{1/2+\alpha/4}\sqrt{D}}{1-\alpha/2}\bigg{)}\sqrt{r_{N}\varepsilon}\bigg{]}+2\varepsilon$
(353)
$\displaystyle=4\varepsilon+2\eta\bigg{(}\frac{2^{1/2+\alpha/4}\sqrt{D}}{1-\alpha/2}\bigg{)}\sqrt{r_{N}\varepsilon}.$
(354)

In addition, we have

$\displaystyle r_{N}=(C\sqrt{\varepsilon})^{2(1-2^{-N})}\geq
C^{2}\varepsilon,$ (355)

or

$\displaystyle\varepsilon\leq\frac{r_{N}}{C^{2}}.$ (356)

Hence, from (354) and (356), we conclude that with some constant
$\tilde{\eta}>0$,

$\displaystyle\mathbb{E}\big{[}\big{\|}P_{n}-P\big{\|}_{\mathcal{G}_{N}}\big{]}\leq\tilde{\eta}\sqrt{r_{N}\varepsilon}.$
(357)

From (322) and (357), on the event $E_{N+1}\cap\mathcal{L}$, we have

$\displaystyle P\\{f\leq\delta_{N,\frac{1}{2}}\\}$
$\displaystyle\leq\varepsilon+\tilde{\eta}\sqrt{r_{N}\varepsilon}+\big{(}K_{2}\sqrt{r_{N}\varepsilon}+K_{3}\varepsilon\big{)}\sqrt{\tau_{\min}}$
(358) $\displaystyle\leq\frac{1}{2}C\sqrt{r_{N}\varepsilon}$ (359)
$\displaystyle=r_{N+1}/2,$ (360)

by a proper choice of the constant $C>0$, where (360) follows from (356). This
means that $f\in\mathcal{F}_{N+1}$ and the induction step for (ii) is proved.

Now, we prove (i). We have on the event $E_{N+1}$,