A Generalization Bound of Deep Neural Networks for Dependent Data
Existing generalization bounds for deep neural networks require data to be
independent and identically distributed (iid). This assumption may not hold in
real-life applications such as evolutionary biology, infectious disease
epidemiology, and stock price prediction. This work establishes a
generalization bound of feed-forward neural networks for non-stationary
$\phi$-mixing data.
Quan Huu Do, Binh T. Nguyen, Lam Si Tung Ho
# A Generalization Bound of Deep Neural Networks for Dependent Data

###### Abstract

Existing generalization bounds for deep neural networks require data to be independent and identically distributed (iid). This assumption may not hold in real-life applications such as evolutionary biology, infectious disease epidemiology, and stock price prediction. This work establishes a generalization bound of feed-forward neural networks for non-stationary \(\varphi\)-mixing data.

**Keywords:** neural networks, generalization bound, non-stationary process, mixing stochastic process

## 1 Introduction

Explaining the generalization ability of machine learning methods (that is, they can provide a close fit to new, unseen data) lies at the heart of theoretical machine learning. The main direction for this research topic is to bound the difference between the expected loss (population loss) and the empirical loss (training loss). This is known as generalization bound, which has been studied extensively in various settings (Freund et al., 2004; Zou et al., 2009; Agarwal and Duchi, 2012; Cuong et al., 2013; Bartlett et al., 2017; Golowich et al., 2018; Lugosi and Neu, 2022).

In the last decade, deep neural networks have become the central attention of the machine learning community due to their remarkable success in solving complex tasks that are considered to be challenging for existing machine learning methods. For example, in computer vision, tasks like image classification, facial recognition, and object detection have significant progress by applying deep neural networks (Krizhevsky et al., 2012). In natural language processing, deep learning models have become state-of-the-art in language translation, sentiment analysis, and chatbots (Vaswani et al., 2017). Additionally,
they have made undeniable contributions to fields beyond computer sciences, including autonomous vehicles, healthcare (Esteva et al., 2019), and finance (Heaton et al., 2017).

Effort has been made to derive the generalization bound for neural networks (Bartlett et al., 2017; Golowich et al., 2018; Dinh and Ho, 2020; Ho and Dinh, 2022). However, these results assume that data are independent and identically distributed (iid). Unfortunately, this assumption is not often satisfied in many applications, including evolutionary biology, infectious disease epidemiology, and stock price prediction. Therefore, it is crucial to study the generalization ability of deep neural networks when data are not iid. In this paper, we will bridge this gap by establishing a generalization bound of feed-forward neural networks for non-stationary \(\varphi\)-mixing data. It is worth noticing that mixing data is the most common alternative to iid data (e.g. White and Domowitz, 1984; Modha and Masry, 1996; Mohri and Rostamizadeh, 2010; Dinh et al., 2015; Ho et al., 2020). In this paper, we consider on the popular \(\varphi\)-mixing sequences: data are dependent, but the dependency of two data points decreases as their distance increases. Furthermore, we do not require data to be identically distributed. Instead, we allow the marginal distribution of data to converge to an unknown target distribution. Under this setting, we establish a new generalization bound for feed-forward neural networks.

## 2 Setting and main results

**Setting:** We consider a classification problem setting where the input-output pairs \(\{(X_{i},Y_{i})\}_{i=1}^{n}\subset\mathbb{R}^{d}\times\{1,2,\ldots,K\}\) are not i.i.d. Specifically, we relax the independence assumption by assuming that the data \(\mathcal{Z}=\{(X_{i},Y_{i})\}_{i=1}^{n}\) are generated from a \(\varphi\)-mixing sequence:

**Definition 1**.: _Let the \(\{Z_{k}\}_{k=0}^{\infty}\) be a sequence of random variables. For any \(i,j\in\mathbb{Z}\), let \(\sigma_{i}^{j}\) denote the \(\sigma\)-algebra generated by the random variables \(\{Z_{k}\}_{k=i}^{j}\). Then, for any positive integer \(k\), the \(\varphi\)-mixing coefficients of the stochastic process \(Z\) is defined as_

\[\varphi(k)=\sup_{\begin{subarray}{c}A\in\sigma_{n+k}^{\infty}\\ B\in\sigma_{0}^{n}\end{subarray}}\big{|}\mathbb{P}\,[A|B]-\mathbb{P}[A]\big{|}.\]

_The sequence of variables \(\{Z_{k}\}_{k=0}^{\infty}\) is said to be \(\varphi\)-mixing if \(\varphi(k)\to 0\) as \(k\to\infty\)._

Additionally, we assume that the data \(\mathcal{Z}=\{(X_{i},Y_{i})\}_{i=1}^{n}\) are not identically distributed. Instead, the marginal distribution of \((X_{i},Y_{i})\) converges to the target distribution \(\Pi\), which is the marginal distribution of the test data. More precisely,

\[\mu_{n}:=\big{|}\big{|}\mathbb{P}_{n}-\Pi\big{|}\big{|}_{\mathrm{TV}}\to 0\]

where \(\mathbb{P}_{n}\) is the marginal distribution of \((X_{i},Y_{i})\) and \(\|\cdot\|_{\mathrm{TV}}\) is the total variation distance.
This paper will focus on feed-forward neural networks with \(L\) hidden layers where the \(i\)-th layer has a weight matrix \(A_{i}\) and an activation function \(\sigma_{i}\). Throughout the paper, we assume that each weight matrix has a dimension at most \(W\) along each axis. Moreover, the activation functions \(\sigma_{i}\) is \(p_{i}\)-Lipschitz (i.e. \(|\sigma_{i}(x)-\sigma_{i}(y)|\leq p_{i}|x-y|\) for all \(x,y\in\mathbb{R}\)) and \(\sigma_{i}(0)=0\).

Denote \(\mathcal{A}=(A_{1},\ldots,A_{L})\) and \(\boldsymbol{\sigma}=(\sigma_{1},\ldots,\sigma_{L})\). The corresponding feed-forward neural network \(F_{\mathcal{A},\boldsymbol{\sigma}}\) is

\[F_{\mathcal{A},\boldsymbol{\sigma}}(x)=\sigma_{L}(A_{L}(\sigma_{L-1}(A_{L-1} \ldots\sigma_{1}(A_{1}x)\ldots)).\]

The network output \(F_{\mathcal{A},\boldsymbol{\sigma}}(x)\in\mathbb{R}^{K}\) is converted to a class label in \(\{1,\ldots,K\}\) by taking the \(\arg\max\) over components, with an arbitrary rule for breaking ties. We will work with the popular ramp loss \(\ell_{\gamma}:\mathbb{R}\rightarrow\mathbb{R}^{+}\): \(\ell_{\gamma}(r):=(1+r^{-}/\gamma)^{+}\) where \(a^{+}=\max\{a,0\}\) and \(a^{-}=\min\{a,0\}\). The empirical loss \(\mathcal{L}_{\mathcal{Z}}(F_{\mathcal{A},\boldsymbol{\sigma}})\) and expected loss \(\mathcal{L}(F_{\mathcal{A},\boldsymbol{\sigma}})\) are defined as

\[\mathcal{L}_{\mathcal{Z}}(F_{\mathcal{A},\boldsymbol{\sigma}}) =\frac{1}{n}\sum_{i=1}^{n}\ell_{\gamma}(-\mathcal{M}(F_{\mathcal{ A},\boldsymbol{\sigma}}(X_{i}),Y_{i}))\] \[\mathcal{L}(F_{\mathcal{A},\boldsymbol{\sigma}}) =\underset{(X,Y)\sim\Pi}{\mathbb{E}}\left[\ell_{\gamma}(-\mathcal{ M}(F_{\mathcal{A},\boldsymbol{\sigma}}(X),Y))\right]\]

where \(\mathcal{M}(v,j):=v_{j}-\max_{i\neq j}v_{i}\) is the margin operator.

**Main results:** First, we will derive a uniform bound of the gap between expected loss and empirical loss for a general hypothesis space \(\mathcal{H}\) and a bounded loss \(\ell\) using Rademacher complexity.

**Definition 2**.: _Given a class of function \(\mathcal{F}\) and a data set \(\mathcal{Z}=(Z_{i})_{i=1}^{n}\), the empirical Rademacher complexity is defined as_

\[\mathcal{R}_{\mathcal{Z}}(\mathcal{F})=\underset{\theta_{1},\theta_{2},\ldots,\theta_{n}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left(\sum_{i=1}^{n}\theta _{i}f(Z_{i})\right)\right]\]

_where \(\{\theta_{i}\}_{i=1}^{n}\) are independent Rademacher random variables. The Rademacher complexity is defined as_

\[\mathcal{R}_{n}(\mathcal{F})=\underset{Z_{1},\ldots,Z_{n}}{\mathbb{E}}\left[R _{\mathcal{Z}}(\mathcal{F})\right].\]

**Theorem 1**.: _Suppose \(\mathcal{H}\) is a hypothesis space and \(\ell\) is a loss function bounded in \([0,1]\). Let \(\delta\) be a positive number. Under our setting, with probability at least \(1-\delta\), for all \(h\in\mathcal{H}\), we have_

\[\underset{(X,Y)\sim\Pi}{\mathbb{E}}\left[\ell(h(X),Y)\right]\leq\frac{1}{n} \sum_{i=1}^{n}\ell(h(X_{i}),Y_{i})+2\mathcal{R}_{\mathcal{Z}}(\mathcal{F}_{ \ell})+\frac{1}{n}\sum_{i=1}^{n}\mu_{i}+3\sqrt{||\Delta_{n}||_{\infty}^{2} \frac{\log(2/\delta)}{2n}}\]

_where \(\mathcal{F}_{\ell}=\{(X,Y)\rightarrow\ell(h(X),Y)|h\in\mathcal{H}\}\) and \(||\Delta_{n}||_{\infty}=1+2\sum_{k=1}^{n}\varphi(k)\)._
**Remark 2.1**.: _Kuznetsov and Mohri (2017) establish a generalization bound for asymptotically stationary processes. However, their setting is different from ours. They consider the scenario where data include \(m\) independent blocks of mixing sequences of size \(a\). That is, the number of data points is \(n=ma\). They assume that the mixing sequences are asymptotically stationary. More precisely, for a sequence \(\{Z_{i}\}_{i=1}^{\infty}\), they define_

\[\beta(a):=\sup_{t}\mathbb{E}\|\mathbb{P}_{t+a}(.|Z_{1},...,Z_{t})-\Pi\|_{\text {TV}}.\]

_The sequence \(\{Z_{i}\}_{i=1}^{\infty}\) is asymptotically stationary if \(\beta(a)\to 0\). It is ready to see that \(\mu_{i}\leq\beta(i)\) for any integer \(i\). Therefore, the marginal distribution of an asymptotically stationary sequence converges to the target distribution \(\Pi\). In other words, their condition is more restricted compared to our condition. Moreover, the convergence rate of their bound is \(\mathcal{O}(1/\sqrt{m}\,)\), which depends on the number of independent sequences. So, their result is not applicable to the scenario we are considering in this paper, where data consists of only one mixing sequence. On the other hand, they also require \(\lim_{i\to\infty}i\beta(i)=0\) while we only require \(\lim_{i\to\infty}\mu_{i}=0\). Thus, their result requires the marginal distribution to converge to the target distribution at a faster rate than ours._

Based on Theorem 1, we can derive the following generalization bound for feed-forward neural networks:

**Theorem 2**.: _Assume that \(\mu_{n}=\mathcal{O}\left(1/\sqrt{n}\right)\) and \(\varphi(n)=\mathcal{O}\left(1/n\right)\). Under our setting, with probability at least \(1-\delta\), for all margin \(\gamma>0\) and network \(F_{\mathcal{A},\boldsymbol{\sigma}}\), we have_

\[\mathbb{P}_{(X,Y)\sim\Pi}\left\{\arg\max_{j}[F_{\mathcal{A}, \boldsymbol{\sigma}}(X)]_{j}\neq Y\right\} \leq\mathcal{L}_{\mathcal{Z}}(F_{\mathcal{A},\boldsymbol{\sigma}})\] \[\quad+\tilde{\mathcal{O}}\left(\frac{\sqrt{\sum_{i}||X_{i}||_{2} ^{2}}}{n\gamma}T_{\mathcal{A}}\log(W)+\sqrt{\frac{log(2/\delta)}{n}}\right)\]

_where \(T_{\mathcal{A}}=\left(\prod_{i=1}^{L}p_{i}\|A_{i}\|_{S}\right)\left(\sum_{i=1} ^{L}\left(\frac{\|A_{i}^{T}\|_{2,1}}{\|A_{i}\|_{S}}\right)^{2/3}\right)^{3/2}\). Here, \(f(x)=\tilde{\mathcal{O}}(g(x))\) means there exists \(C,x_{0}>0\) such that \(|f(x)|\leq C\log(x)g(x)\) for all \(x\geq x_{0}\), \(||.||_{S}\) is the spectral norm, and \(||.||_{p,q}\) is \((p,q)\)-matrix norm, defined by \(||A||_{p,q}=||(||A_{:,1}||_{p},...,||A_{:,m}||_{p})||_{q}\)._

**Remark 2.2**.: _The generalization bound in Bartlett et al. (2017) is a special case of Theorem 2 when data are iid._

## 3 Proofs of main theorems

In this section, we will provide proof of our main theorems.
### Proof of Theorem 1

We first introduce some supporting Lemmas.

**Lemma 1**.: _Let \(P\) be the distribution of a \(\varphi\)-mixing sequence and \(\mathcal{F}\) be any class of functions. Then_

\[\mathop{\mathbb{E}}_{(Z_{1},Z_{2},\ldots,Z_{n})\sim P}\left[\sup_{f\in\mathcal{F }}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})-\mathop{\mathbb{E}}_{(Z_{1}^{\prime}, Z_{2}^{\prime},\ldots,Z_{n}^{\prime})\sim P}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^{ \prime})\right]\right]\right]\leq 2\mathcal{R}_{n}(\mathcal{F}).\]

Proof.: We first rewrite the term inside of the first expectation:

\[\sup_{f\in\mathcal{F}}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})-\mathop{\mathbb{ E}}_{Z_{1}^{\prime},\ldots,Z_{n}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^ {\prime})\right]\right]\leq\frac{1}{n}\mathop{\mathbb{E}}_{Z_{1}^{\prime}, \ldots,Z_{n}^{\prime}}\left[\sup_{f\in\mathcal{F}}\left(\sum_{i=1}^{n}f(Z_{i} )-\sum_{i=1}^{n}f(Z_{i}^{\prime})\right)\right].\]

Let \(\{\theta_{i}\}_{i=1}^{n}\) be independent Rademacher random variables. Taking the expectation with respect to \(\{Z_{i}\}_{i=1}^{n}\) for both sides, we have

\[\mathop{\mathbb{E}}_{Z_{1},\ldots,Z_{n}}\left[\sup_{f\in\mathcal{ F}}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})-\mathop{\mathbb{E}}_{Z_{1}^{\prime}, \ldots,Z_{n}^{\prime}}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^{\prime})\right] \right]\right]\] \[\leq\frac{1}{n}\mathop{\mathbb{E}}_{Z_{1},\ldots,Z_{n}}\left[ \mathop{\mathbb{E}}_{Z_{1}^{\prime},\ldots,Z_{n}^{\prime}}\left[\sup_{f\in \mathcal{F}}\left(\sum_{i=1}^{n}f(Z_{i})-\sum_{i=1}^{n}f(Z_{i}^{\prime}) \right)\right]\right]\] \[\leq\mathop{\mathbb{E}}_{Z_{1},\ldots,Z_{n},Z_{1}^{\prime}, \ldots,Z_{n}^{\prime}}\left[\mathop{\mathbb{E}}_{\theta_{j}\times\{1;-1;-1\}} \left[\sup_{f\in\mathcal{F}}\left(\sum_{i=1}^{n}\theta_{i}f(Z_{i})-\sum_{i=1}^ {n}\theta_{i}f(Z_{i}^{\prime})\right)\right]\right]\] \[\leq\mathop{\mathbb{E}}_{Z_{1},\ldots,Z_{n},Z_{1}^{\prime}, \ldots,Z_{n}^{\prime},\theta_{1},\ldots,\theta_{n}}\left[\sup_{f\in\mathcal{ F}}\left(\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i})\right)+\sup_{f\in \mathcal{F}}\left(\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i}^{\prime})\right)\right]\] \[=2\mathcal{R}_{n}(\mathcal{F}).\]

**Lemma 2**.: _(Mohri and Rostamizadeh, 2010) Let \(\Phi:Z^{n}\to\mathbb{R}\) be a measurable function that is \(c\)-Lipschitz with respect to the Hamming metric for some \(c>0\) and let \(\{Z_{i}\}_{i=1}^{n}\) be a \(\varphi\)-mixing sequence. Then, for any \(\epsilon>0\), the following inequality holds:_

\[\mathbb{P}\left[\left|\Phi(Z_{1},\ldots,Z_{n})-\mathbb{E}[\Phi(Z_{1},\ldots,Z_{ n})]\right|\geq\epsilon\right]\leq 2\exp\left(\frac{-2\epsilon^{2}}{nc^{2}\|\Delta_{n}\|_{ \infty}^{2}}\right),\]

_where \(\|\Delta_{n}\|_{\infty}^{2}=1+2\sum_{k=1}^{n}\varphi(k)\)._
**Lemma 3**.: _Let \(\mathcal{Z}=\{Z_{i}\}_{i=1}^{n}\) be a \(\varphi\)-mixing sequence and \(\mathcal{F}\) be any class of functions bounded in \([0,1]\). Then, with probability at least \(1-\delta\), we have_

\[\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})\right]-\frac{1}{n}\sum_{i=1} ^{n}f(Z_{i})\leq 2\mathcal{R}_{\mathcal{Z}}(\mathcal{F})+3\sqrt{||\Delta_{n}||_{ \infty}^{2}\frac{\log(2/\delta)}{2n}},\quad\forall f\in\mathcal{F}.\]

Proof.: Define

\[g(Z_{1},\ldots,Z_{n})\triangleq\sup_{f\in\mathcal{F}}\left[\mathbb{E}\left[ \frac{1}{n}\sum_{i=1}^{n}f(Z_{i})\right]-\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}) \right].\]

We first show that \(g\) is \(\frac{1}{n}\)-Lipschitz with respect to the Hamming distance. For any \(\mathcal{Z}=(Z_{1},\ldots,Z_{n})\) and \(\mathcal{Z}^{\prime}=(Z_{1}^{\prime},\ldots,Z_{n}^{\prime})\), we have

\[|g(\mathcal{Z})-g(\mathcal{Z}^{\prime})|\] \[=\left|\sup_{f\in\mathcal{F}}\left[\mathbb{E}\left[\frac{1}{n} \sum_{i=1}^{n}f(Z_{i})\right]-\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})\right]-\sup_{f \in\mathcal{F}}\left[\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^{\prime })\right]-\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^{\prime})\right]\right|\] \[\leq\sup_{f\in\mathcal{F}}\left|\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}) -\frac{1}{n}\sum_{i=1}^{n}f(Z_{i}^{\prime})\right|\leq\frac{\|\mathcal{Z}- \mathcal{Z}^{\prime}\|_{H}}{n}\]

where \(\|\cdot\|_{H}\) is the Hamming distance. The last inequality holds since \(f\) bound in \([0,1]\). Since \(g\) is \(\frac{1}{n}\)-Lipschitz with respect to the Hamming distance, we apply Lemma 2 to obtain:

\[\mathbb{P}\left[g(\mathcal{Z})\geq\underset{Z_{1},Z_{2},\ldots,Z_{n}}{\mathbb{ E}}[g]+\epsilon\right]\leq\exp\left(\frac{-2n\epsilon^{2}}{\|\Delta_{n}\|_{ \infty}^{2}}\right).\]

Applying Lemma 1, we get \(\mathbb{E}_{Z_{1},Z_{2},\ldots,Z_{n}}[g]\leq 2\mathcal{R}_{n}(\mathcal{F}).\) We will show that \(\mathcal{R}_{\mathcal{Z}}(\mathcal{F})\) is also \(\frac{1}{n}\)-Lipschitz with respect to the Hamming distance. Indeed, using similar arguments, we have

\[\left|\underset{\theta_{i}}{\mathbb{E}}\left[\sup_{f\in\mathcal{ F}}\left[\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i})\right]\right]-\underset{ \theta_{i}}{\mathbb{E}}\left[\sup_{f\in\mathcal{F}}\left[\frac{1}{n}\sum_{i=1 }^{n}\theta_{i}f(Z_{i}^{\prime})\right]\right]\right|\] \[\leq\underset{\theta_{i}}{\mathbb{E}}\left|\sup_{f\in\mathcal{F}} \left[\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i})\right]-\sup_{f\in\mathcal{F}} \left[\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i}^{\prime})\right]\right|\] \[\leq\underset{\mu_{i}}{\mathbb{E}}\left|\sup_{f\in\mathcal{F}} \left[\frac{1}{n}\sum_{i=1}^{n}\theta_{i}f(Z_{i})-\frac{1}{n}\sum_{i=1}^{n} \theta_{i}f(Z_{i}^{\prime})\right]\right|\leq\frac{\|\mathcal{Z}-\mathcal{Z}^ {\prime}\|_{H}}{n}.\]

We can thus apply Lemma 2:

\[\mathbb{P}\left[\underset{Z_{1},Z_{2},\ldots,Z_{n}}{\mathbb{E}}[\mathcal{R}_{ \mathcal{Z}}(\mathcal{F})]\geq\mathcal{R}_{\mathcal{Z}}(\mathcal{F})+\epsilon \right]\leq\exp\left(\frac{-2n\epsilon^{2}}{||\Delta_{n}||_{\infty}^{2}}\right).\]
We set \(\epsilon=\sqrt{||\Delta_{n}||_{\infty}^{2}\frac{\log(2/\delta)}{2n}}\). Then with probability at least \(1-\delta\),

\[g\leq\mathbb{E}[g]+\epsilon\leq 2\mathcal{R}_{n}(\mathcal{F})+\epsilon\leq 2( \mathcal{R}_{\mathcal{Z}}(\mathcal{F})+\epsilon)+\epsilon=2\mathcal{R}_{ \mathcal{Z}}(\mathcal{F})+3\epsilon.\]

**Lemma 4**.: _Let \(f\) is bounded function in \([0;1]\). Let \(\{Z_{i}\}_{i=0}^{n}\) be a non-stationary \(\varphi\)-mixing sequence such that the marginal distributions converge to a target distribution \(\Pi\) with rate \(\mu_{n}\). Then_

\[\left|\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})\right]- \underset{Z\sim\Pi}{\mathbb{E}}\left[f(Z)\right]\right|\leq\frac{1}{n}\sum_{i =1}^{n}\mu_{i}.\]

Proof.: For any \(i\),

\[\mathbb{E}\left[f(Z_{i})\right]-\mathbb{E}\left[f(Z)\right]=\int_{\Omega}f(z).(f_{\mathbb{P}_{i}}(z)-f_{\Pi}(z))dz. \tag{1}\]

Define \(A=\{z\in\Omega|f_{\mathbb{P}_{i}}(z)<f_{\Pi}(z)\}\) and \(B=\{z\in\Omega|f_{\mathbb{P}_{i}}(z)>f_{\Pi}(z)\}\). We rewrite Eq.(1)

\[\mathbb{E}\left[f(Z_{i})\right]-\mathbb{E}\left[f(Z)\right]=\int_{A}f(z).(f_{ \mathbb{P}_{i}}(z)-f_{\Pi}(z))dz+\int_{B}f(z).(f_{\mathbb{P}_{i}}(z)-f_{\Pi}( z))dz.\]

For the first term,

\[0\geq\int_{A}f(z).(f_{\mathbb{P}_{i}}(z)-f_{\Pi}(z))dz\geq\int_{A}(f_{\mathbb{ P}_{i}}(z)-f_{\Pi}(z))dz\geq-\mu_{i}.\]

For the second term,

\[0\leq\int_{B}f(z).(f_{\mathbb{P}_{i}}(z)-f_{\Pi}(z))dz\leq\int_{B}(f_{\mathbb{ P}_{i}}(z)-f_{\Pi}(z))dz\leq\mu_{i}.\]

Then

\[-\mu_{i}\leq\mathbb{E}\left[f(Z_{i})\right]-\mathbb{E}\left[f(Z)\right]\leq \mu_{i}.\]

we have

\[\left|\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}f(Z_{i})\right]- \underset{Z\sim\Pi}{\mathbb{E}}\left[f(Z)\right]\right|\leq\frac{1}{n}\sum_{i =1}^{n}\left|\mathbb{E}\left[f(Z_{i})\right]-\underset{Z\sim\Pi}{\mathbb{E}} \left[f(Z)\right]\right|\leq\frac{1}{n}\sum_{i=1}^{n}\mu_{i}.\]

Theorem 1 is a direct consequence of Lemmas 3 and 4.
### Proof of Theorem 2

Theorem 2 can be achieved by combining Theorem 1 and the proof technique of Bartlett et al. (2017). Denote \(\mathcal{F}_{\mathcal{A},\boldsymbol{\sigma},\gamma}=\{(x,y)\to\ell_{\gamma}( \mathcal{M}(F_{\mathcal{A},\boldsymbol{\sigma}}(x),y))\}\). Applying Theorem 1, we have

\[\mathcal{L}(F_{A,\sigma})\leq\mathcal{L}_{\mathcal{Z}}(F_{\mathcal{A}, \boldsymbol{\sigma}})+2\mathcal{R}_{\mathcal{Z}}(\mathcal{F}_{\mathcal{A}, \boldsymbol{\sigma},\gamma})+\frac{1}{n}\sum_{i=1}^{n}\mu_{i}+3\sqrt{|| \Delta_{n}||_{\infty}^{2}\frac{\log(2/\delta)}{2n}} \tag{2}\]

with probability at least \(1-\delta\).

Next, we introduce some supporting Lemmas.

**Lemma 5** (Lemma A.4 in Bartlett et al. (2017)).: _For any \(f:\mathbb{R}^{d}\to\mathbb{R}^{k}\) and every \(\gamma>0\), we have_

\[\mathbb{P}_{(X,Y)\sim\Pi}\left\{\arg\max_{j}[F_{\mathcal{A},\boldsymbol{ \sigma}}(X)]_{j}\neq Y\right\}\leq\mathcal{L}(F_{A,\sigma}).\]

**Lemma 6**.: _Assume that \(\sqrt{\sum_{i}||X_{i}||_{2}^{2}}\leq B\). For all feed-forward neural network \(F_{\mathcal{A},\boldsymbol{\sigma}}:\mathbb{R}^{d}\to\mathbb{R}^{k}\) such that \(||A_{i}||_{\sigma}\leq s_{i}\) and \(||A_{i}^{T}||_{2,1}\leq b_{i}\), we have_

\[\mathcal{R}_{\mathcal{Z}}(F_{\mathcal{A},\boldsymbol{\sigma},\gamma})\leq \frac{4}{\sqrt{n^{3}}}+\frac{36B\ln(2W)\ln(n)}{\gamma n}\left(\sum_{i=1}^{L} \left(\frac{b_{i}}{s_{i}}\right)^{2/3}\right)^{3/2}\left(\prod_{i=1}^{L}s_{i} p_{i}\right).\]

Proof.: Using the same argument of the proof of Lemma A.8 in Bartlett et al. (2017), we obtain:

\[\mathcal{R}_{\mathcal{Z}}(F_{\mathcal{A},\boldsymbol{\sigma},\gamma})\leq \inf_{a>0}\left(\frac{4\alpha}{\sqrt{n}}+\frac{12}{n}\int_{\alpha}^{\sqrt{n}} \sqrt{\frac{R}{\epsilon^{2}}}d\epsilon\right)=\inf_{a>0}\left(\frac{4\alpha}{ \sqrt{n}}+\ln(\sqrt{n}/\alpha)\frac{12\sqrt{R}}{n}\right);\]

where

\[R=\frac{4B^{2}\ln(2W^{2})}{\gamma^{2}}\left(\sum_{i=1}^{L}\left(\frac{b_{i}}{ s_{i}}\right)^{2/3}\right)^{3}\left(\prod_{i=1}^{L}s_{i}p_{i}\right)^{2}.\]

The desired bound may be obtained by setting \(\alpha=1/n\). 

Combining equation (2), Lemma 5, and Lemma 6, we get the following Lemma

**Lemma 7**.: _With probability at least \(1-\delta\) over a non-stationary \(\varphi\)-mixing sequence \(\mathcal{Z}=((X_{i},Y_{i}))_{i=1}^{n}\) with \(\sqrt{\sum_{i}||X_{i}||_{2}^{2}}\leq B\), for all feed-forward neural network \(F_{\mathcal{A},\boldsymbol{\sigma}}:\mathbb{R}^{d}\to\mathbb{R}^{k}\) such that \(||A_{i}||_{\sigma}\leq s_{i}\) and \(||A_{i}^{T}||_{2,1}\leq b_{i}\), we have_

\[\mathbb{P}_{(X,Y)\sim\Pi}\left\{\arg\max_{j}[F_{\mathcal{A}, \boldsymbol{\sigma}}(X)]_{j}\neq Y\right\}\leq\mathcal{L}_{\mathcal{Z}}(F_{ \mathcal{A},\boldsymbol{\sigma}})+\frac{1}{n}\sum_{i=1}^{n}\mu_{i}+3\sqrt{|| \Delta_{n}||_{\infty}^{2}\frac{\log(2/\delta)}{2n}}\\ +\frac{8}{\sqrt{n^{3}}}+\frac{72B\ln(2W)\ln(n)}{\gamma n}\left( \sum_{i=1}^{L}\left(\frac{b_{i}}{s_{i}}\right)^{2/3}\right)^{3/2}\left(\prod_ {i=1}^{L}s_{i}p_{i}\right).\]
Now, we can achieve Theorem 2 by utilizing Lemma 7 to derive a union bound over the parameter space and input space. This can be done by following the same steps as the proofs of Lemma A.9 in Bartlett et al. (2017). Finally, we note that \(\mu_{n}=\mathcal{O}\left(1/\sqrt{n}\right)\) and \(\varphi(n)=\mathcal{O}\left(1/n\right)\). Therefore,

\[\frac{1}{n}\sum_{i=1}^{n}\mu_{i}=\mathcal{O}\left(\frac{1}{\sqrt{n}}\right), \quad||\Delta_{n}||_{\infty}=\mathcal{O}\left(\log n\right).\]

## 4 Discussion and conclusion

In this paper, we propose a generalization bound of feed-forward neural networks for the nonstationary \(\varphi\)-mixing sequences using Rademacher complexity. We first derive a generalization bound for bounded loss on a general hypothesis space when data are nonstationary and \(\varphi\)-mixing. Our result allows data to converge to the target distribution at a slower rate compared to Kuznetsov and Mohri (2017). Moreover, the generalization bound in Kuznetsov and Mohri (2017) does not work for our setting where data include only one mixing sequence. Using our new bound, we establish a generalization bound of feed-forward neural networks, including the result of Bartlett et al. (2017) for iid data as a special case. A future research direction is extending our generalization bound beyond mixing data. Alternative options include data generated from a dynamical system (Ho et al., 2023), evolutionary data (Ho and Ane, 2013), and data from infectious disease epidemics (Ho et al., 2018). Another direction is to develop a generalization bound for other types of deep neural networks. This requires new bounds for the Rademacher complexity of these neural networks.

## Acknowledgement

LSTH was supported by the Canada Research Chairs program, the NSERC Discovery Grant RGPIN-2018-05447, and the NSERC Discovery Launch Supplement DGECR-2018-00181. We want to thank the University of Science, Vietnam National University Ho Chi Minh City, and AISIA Research Lab for supporting us in this project.
