# Learning Bounds of ERM Principle for Sequences of Time-Dependent Samples

Authors: Mingchen Yao; Chao Zhang; Wei Wu
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Many generalization results in learning theory are established under the assumption that samples are independent and identically distributed (i.i.d.). However, numerous learning tasks in practical applications involve the time-dependent data. In this paper, we propose a theoretical framework to analyze the generalization performance of the empirical risk minimization (ERM) principle for sequences of time-dependent samples (TDS). In particular, we first present the generalization bound of ERM principle for TDS. By introducing some auxiliary quantities, we also give a further analysis of the generalization properties and the asymptotical behaviors of ERM principle for TDS.


---

## Body

## 1. Introduction

LetX⊂RI and Y⊂RJ be an input space and the corresponding output space, respectively. Define Z≔X×Y⊂RP with P=I+J. Many classical results of statistical learning theory are built under the assumption that samples zn≔xn,yn are independently drawn from an identical distribution on Z, that is, the so-called i.i.d.-sample assumption, for example, [1–5]. However, the theoretical results sharing the i.i.d.-sample assumption may not be valid for (or cannot be directly used in) the non-i.i.d. scenario.There have been many research interests lying in the theoretical analysis of the learning processes for time-dependent samples. Zhang and Tao [6, 7] study the generalization properties of ERM-based learning processes for time-dependent samples drawn from Lévy processes and continues-time Markov chains, respectively. Zou et al. [8] establish exponential bound on the rate of relative uniform convergence for the ERM algorithm with dependent observations and derived the related generalization bounds with α-mixing sequence. Jiang [9] introduces a triplex inequality based on Hoeffding’s inequality (cf. [10]) and then obtains probability bounds for uniform deviations in a very general framework, which is suitable for the cases with unbounded loss functions and dependent samples. Zou et al. [11] present a novel Markov sampling algorithm to generate uniformly ergodic Markov chain samples from a given dataset. Xu et al. [12] adopt the similar techniques of [11] to develop the error bound for an online SVM classification algorithm, which provides a higher learning performance than that of classical random sampling methods.In this paper, we are mainly concerned with the generalization performance of ERM principle for the sequences of time-dependent samples (TDS), which are independently and repeatedly observed from an undetermined stochastic process at the fixed time points. We can see that the generalization performance of such learning process is affected by the following factors: the number of independent observation sequences, time-dependence among samples in a sequence, the sample number in a sequence, and the observing time points.By introducing some auxiliary quantities, we propose a new framework to analyze the generalization properties of the learning process. In particular, we first show that the generalization bound of this learning process can be decomposed into four parts:Φ1, Φ2, Φ3, and Φ4, which are related to the aforementioned factors. We then analyze the properties of these quantities. By imposing some mild conditions, we further obtain the upper bounds of the first three types of quantities Φ1, Φ2, and Φ3, respectively. Finally, some techniques of statistical learning theory are applied to bound the quantity Φ4, for example, the uniform entry number, the relevant deviation, and the symmetrization inequalities for independent sequences of TDS.Different from previous works [6, 7], there is no specific assumption on the distribution of the stochastic process sampled from. In contrast, the previous works require that samples should be observed from Lévy processes and continuous-time Markov chains, respectively. Instead of the only Z-valued function class appearing in the previous works, we impose a function class consisting of functions evaluated on Z and the time interval [T1,T2]. Moreover, the samples considered in previous works [6–8] are a series of data observed from one certain stochastic process, while this paper discusses the learning process based on quantities of independent sequences of TDS observed from a stochastic process at the fixed time points.Moreover, the works [9, 11, 12] only consider the case of one single sequence of TDS, while this paper studies the learning process for multiple sequences of TDS, where one sequence corresponds to one trajectory (sample path) of a stochastic process. Therefore, our results are more general than previous ones.The rest of paper is organized as follows. In Section2, we first introduce some notions and notations used in the paper and then exhibit the decomposition of the generalization bounds of ERM principle for TDS. In Section 3, we bound the four auxiliary quantities Φ1, Φ2, Φ3, and Φ4 and present the main results of the paper. The last section concludes the paper.


## 2. Problem Setup

In this section, we formalize the main research issue of this paper and then show the decomposition of the generalization error of ERM principle for TDS.


### 2.1. ERM Principle and Generalization Bounds

For anyt≥0, let xt∈X and yt∈Y be the t-time inputs and the corresponding outputs, respectively. Denote zt≔(xt,yt)∈RP (t≥0) and assume that ztt≥0 is an undetermined stochastic process with a countable space. Consider a function class G⊂YX×T consisting of functions evaluated at the input space X and the time interval T=[T1,T2]. We would like to find a function g∗∈G such that, for any input xt∈X (t∈T), the corresponding output yt can be predicted as accurately as possible.A natural criterion to choose the functiong∗ is the lowestexpected risk caused by some function in G:(1)g∗=arg⁡ming∈G⁡El∘g=arg⁡ming∈G⁡1T∫T1T2∫lgxt,t,ytdPtdt,where g(xt,t) is a function with respect to the t-time input xt and the time point t (Here, xt in the function g(xt,t) is just an input value of the functional g(·,t)), l∘g is the composite function l after g, and Pt stands for the t-time distribution of the stochastic process ztt≥0 on Z. However, the distribution of ztt≥0 is unknown, and it is difficult to directly obtain the target function g∗ by minimizing the expected risk E(l∘g).Instead, the empirical risk minimization (ERM) principle provides a solution scheme to this issue. For1≤m≤M, let SN[m]≔ztnmn=1N be the mth sequence of samples observed from a certain stochastic process ztt≥0 at the fixed time points T1≤t1<t2<⋯<tn≤T2 and let the sequences SN[m] (1≤m≤M) be independent of each other. The ERM principle aims to minimize theempirical risk over G:(2)g^=arg⁡ming∈G⁡E^l∘g=arg⁡ming∈G⁡1MN∑m=1M∑n=1Nlgxtnm,tn,ytnm,and the solution g^ is regarded as an estimate to the expected solution g∗ with respect to the sample sequences SNmm=1M.For convenience, we further define the loss function class(3)F≔zt,t⟼lgxt,t,yt:g∈Gand call F the function class in the rest of this paper. Given M sample sequences SNmm=1M, taking f=l∘g provides the following brief notations of expected risk (1) and empirical risk (2):(4)Ef=El∘g=1T∫T1T2∫fzt,tdPtdt,(5)E^f=E^l∘g=1MN∑m=1M∑n=1Nfztnm,tn.Similar to the classical statistical learning theory [13], the main issue of this paper is to discuss whether the empirical solution g^ provided by ERM principle will perform as well as the expected solution g∗. Then, the supremum(6)supf∈F⁡Ef-E^f,called the generalization bound of ERM principle for TDS SNmm=1M, will play an important role in analyzing the generalization performance of the above learning process as well.


### 2.2. Relationship with Some Time-Dependent Problem

At the end of this section, we will show that many time-dependent problems can come down to the aforementioned learning process based on ERM principle, for example, the estimation of information channel and functional linear models.


#### 2.2.1. Estimation of Information Channel

Since the functions inF are evaluated at both the real input space X and the time interval T, the framework proposed in the paper can describe the inherent characteristics of the time-dependent problems more precisely than the learning framework given in the previous works [6, 7], where the function class is only evaluated at X. Certainly, the time-dependent problem mentioned in [14], for example, the estimation of information channel, can also be included in this learning setting. Different from the previous one, the setting considered in this paper is also suitable for analyzing the performance of estimating dynamic information channel.The estimation of dynamic information channel is of the following model:yt=H(t)xt+n(t), where H(t) and n(t), changing status with time varying, are the channel matrix and the noise vector, respectively. The corresponding function class H is formalized as (7)H≔x,t⟼Htx+nt:Ht∈RJ×RI,nt∈RJ.


#### 2.2.2. Functional Linear Models

Moreover, the functional data classification or regression with functional linear models is also in accordance with the learning setting mentioned in this paper. By denoting(8)Bt≔βjitJ×I,ρt≔ρ1t,…,ρJt⊤,τt≔τ1t,…,τJt⊤,the following are the most frequently used functional linear models mentioned by [15]: (i)
The model with a scalar input and a functional output:y(t)=B(t)x+ρ(t), which corresponds to the function class for any t∈T: (9)G·,t=x⟼Btx+ρt:βjit,ρjt∈RT.(ii)
The model with a functional input and a scalar output:y=τ+∫Θt‍B(t)x(t)dt+ρ, which corresponds to the function class for any t∈T: (10)G·,t=xt⟼τ+∫ΘtBtxtdt+ρ:βjit∈RT;τ,ρ∈RJ.(iii)
The two models with a functional input and a functional output:
(a)
one model isy(t)=τ(t)+B(t)x(t)+ρ(t), which corresponds to the function class for any t∈T: (11)G·,t=xt⟼τt+Btxt+ρt:βjit,ρjt,τjt∈RT;(b)
the other isy(t)=τ(t)+∫Θt‍B(s,t)x(t)ds+ρ(t), which corresponds to the function class for any t∈T: (12)G·,t=xt⟼τt+∫ΘtBs,txtds+ρt:βjis,t∈RT×T;ρjt,τjt∈RT.In the above models, the loss function l is usually selected as the mean square error function and then some functional data algorithms are used to find the function that minimizes empirical risk (2) over the function class F. We refer to [16] for more details on functional linear models.


### 2.3. Analysis of Generalization Performance

Different from the i.i.d. learning setting, regardless of the distribution characteristics ofztt≥0, the generalization performance of the aforementioned learning process is also affected by the following factors:(i)
Time-dependence among samples in one sequence.(ii)
The numberM of independent sequences of samples.(iii)
The numberN of samples in one sequence.(iv)
The fixed time pointst1,…,tN, at which the samples zt1,…,ztN are observed.The main concern of this paper is to quantitatively analyze the influence to the generalization performance caused by these factors and then achieve the generalization bound of ERM principle for TDS.Proposition 1.
DenoteΓ∗≔τ0∗,τ1∗,…,τN∗⊂[T1,T2] as an ordered set with T1=τ0∗<τ1∗<⋯<τN∗<T2 and Δτn∗≔τn∗-τn-1∗(1≤n≤N). If the set Γ∗ achieves the supremum(13)supf∈FΓ⊂T1,T2⁡∑n=1NΔτnT∫fzτn,τndPτn-1NM∑m=1M∑n=1Nfztnm,tn,then there holds that(14)supf∈F⁡Ef-E^f≤Φ1+Φ2+Φ3+Φ4,where the quantities Φ1, Φ2, Φ3, and Φ4 are, respectively, defined by(15)Φ1≔∑n=1NΔτn∗T-1Nsupf∈F⁡∫fzτn∗,τn∗dPτn∗;(16)Φ2≔supf∈F⁡1N∑n=1N∫fzτn∗,τn∗dPτn∗-∫fztn,τn∗dPtn;(17)Φ3≔supf∈F⁡1N∑n=1N∫fztn,τn∗dPtn-∫fztn,tndPtn;(18)Φ4≔supf∈F⁡1N∑n=1N∫ftnzdPtn-1MN∑n=1N∑m=1Mftnztnm.This result implies that the behavior of the generalization bound can be described by using the summation of the quantitiesΦ1, Φ2, Φ3, and Φ4. In the next section, we will discuss the properties of the quantities Φ1, Φ2, Φ3, and Φ4, respectively.


## 2.1. ERM Principle and Generalization Bounds

For anyt≥0, let xt∈X and yt∈Y be the t-time inputs and the corresponding outputs, respectively. Denote zt≔(xt,yt)∈RP (t≥0) and assume that ztt≥0 is an undetermined stochastic process with a countable space. Consider a function class G⊂YX×T consisting of functions evaluated at the input space X and the time interval T=[T1,T2]. We would like to find a function g∗∈G such that, for any input xt∈X (t∈T), the corresponding output yt can be predicted as accurately as possible.A natural criterion to choose the functiong∗ is the lowestexpected risk caused by some function in G:(1)g∗=arg⁡ming∈G⁡El∘g=arg⁡ming∈G⁡1T∫T1T2∫lgxt,t,ytdPtdt,where g(xt,t) is a function with respect to the t-time input xt and the time point t (Here, xt in the function g(xt,t) is just an input value of the functional g(·,t)), l∘g is the composite function l after g, and Pt stands for the t-time distribution of the stochastic process ztt≥0 on Z. However, the distribution of ztt≥0 is unknown, and it is difficult to directly obtain the target function g∗ by minimizing the expected risk E(l∘g).Instead, the empirical risk minimization (ERM) principle provides a solution scheme to this issue. For1≤m≤M, let SN[m]≔ztnmn=1N be the mth sequence of samples observed from a certain stochastic process ztt≥0 at the fixed time points T1≤t1<t2<⋯<tn≤T2 and let the sequences SN[m] (1≤m≤M) be independent of each other. The ERM principle aims to minimize theempirical risk over G:(2)g^=arg⁡ming∈G⁡E^l∘g=arg⁡ming∈G⁡1MN∑m=1M∑n=1Nlgxtnm,tn,ytnm,and the solution g^ is regarded as an estimate to the expected solution g∗ with respect to the sample sequences SNmm=1M.For convenience, we further define the loss function class(3)F≔zt,t⟼lgxt,t,yt:g∈Gand call F the function class in the rest of this paper. Given M sample sequences SNmm=1M, taking f=l∘g provides the following brief notations of expected risk (1) and empirical risk (2):(4)Ef=El∘g=1T∫T1T2∫fzt,tdPtdt,(5)E^f=E^l∘g=1MN∑m=1M∑n=1Nfztnm,tn.Similar to the classical statistical learning theory [13], the main issue of this paper is to discuss whether the empirical solution g^ provided by ERM principle will perform as well as the expected solution g∗. Then, the supremum(6)supf∈F⁡Ef-E^f,called the generalization bound of ERM principle for TDS SNmm=1M, will play an important role in analyzing the generalization performance of the above learning process as well.


## 2.2. Relationship with Some Time-Dependent Problem

At the end of this section, we will show that many time-dependent problems can come down to the aforementioned learning process based on ERM principle, for example, the estimation of information channel and functional linear models.


### 2.2.1. Estimation of Information Channel

Since the functions inF are evaluated at both the real input space X and the time interval T, the framework proposed in the paper can describe the inherent characteristics of the time-dependent problems more precisely than the learning framework given in the previous works [6, 7], where the function class is only evaluated at X. Certainly, the time-dependent problem mentioned in [14], for example, the estimation of information channel, can also be included in this learning setting. Different from the previous one, the setting considered in this paper is also suitable for analyzing the performance of estimating dynamic information channel.The estimation of dynamic information channel is of the following model:yt=H(t)xt+n(t), where H(t) and n(t), changing status with time varying, are the channel matrix and the noise vector, respectively. The corresponding function class H is formalized as (7)H≔x,t⟼Htx+nt:Ht∈RJ×RI,nt∈RJ.


### 2.2.2. Functional Linear Models

Moreover, the functional data classification or regression with functional linear models is also in accordance with the learning setting mentioned in this paper. By denoting(8)Bt≔βjitJ×I,ρt≔ρ1t,…,ρJt⊤,τt≔τ1t,…,τJt⊤,the following are the most frequently used functional linear models mentioned by [15]: (i)
The model with a scalar input and a functional output:y(t)=B(t)x+ρ(t), which corresponds to the function class for any t∈T: (9)G·,t=x⟼Btx+ρt:βjit,ρjt∈RT.(ii)
The model with a functional input and a scalar output:y=τ+∫Θt‍B(t)x(t)dt+ρ, which corresponds to the function class for any t∈T: (10)G·,t=xt⟼τ+∫ΘtBtxtdt+ρ:βjit∈RT;τ,ρ∈RJ.(iii)
The two models with a functional input and a functional output:
(a)
one model isy(t)=τ(t)+B(t)x(t)+ρ(t), which corresponds to the function class for any t∈T: (11)G·,t=xt⟼τt+Btxt+ρt:βjit,ρjt,τjt∈RT;(b)
the other isy(t)=τ(t)+∫Θt‍B(s,t)x(t)ds+ρ(t), which corresponds to the function class for any t∈T: (12)G·,t=xt⟼τt+∫ΘtBs,txtds+ρt:βjis,t∈RT×T;ρjt,τjt∈RT.In the above models, the loss function l is usually selected as the mean square error function and then some functional data algorithms are used to find the function that minimizes empirical risk (2) over the function class F. We refer to [16] for more details on functional linear models.


## 2.2.1. Estimation of Information Channel

Since the functions inF are evaluated at both the real input space X and the time interval T, the framework proposed in the paper can describe the inherent characteristics of the time-dependent problems more precisely than the learning framework given in the previous works [6, 7], where the function class is only evaluated at X. Certainly, the time-dependent problem mentioned in [14], for example, the estimation of information channel, can also be included in this learning setting. Different from the previous one, the setting considered in this paper is also suitable for analyzing the performance of estimating dynamic information channel.The estimation of dynamic information channel is of the following model:yt=H(t)xt+n(t), where H(t) and n(t), changing status with time varying, are the channel matrix and the noise vector, respectively. The corresponding function class H is formalized as (7)H≔x,t⟼Htx+nt:Ht∈RJ×RI,nt∈RJ.


## 2.2.2. Functional Linear Models

Moreover, the functional data classification or regression with functional linear models is also in accordance with the learning setting mentioned in this paper. By denoting(8)Bt≔βjitJ×I,ρt≔ρ1t,…,ρJt⊤,τt≔τ1t,…,τJt⊤,the following are the most frequently used functional linear models mentioned by [15]: (i)
The model with a scalar input and a functional output:y(t)=B(t)x+ρ(t), which corresponds to the function class for any t∈T: (9)G·,t=x⟼Btx+ρt:βjit,ρjt∈RT.(ii)
The model with a functional input and a scalar output:y=τ+∫Θt‍B(t)x(t)dt+ρ, which corresponds to the function class for any t∈T: (10)G·,t=xt⟼τ+∫ΘtBtxtdt+ρ:βjit∈RT;τ,ρ∈RJ.(iii)
The two models with a functional input and a functional output:
(a)
one model isy(t)=τ(t)+B(t)x(t)+ρ(t), which corresponds to the function class for any t∈T: (11)G·,t=xt⟼τt+Btxt+ρt:βjit,ρjt,τjt∈RT;(b)
the other isy(t)=τ(t)+∫Θt‍B(s,t)x(t)ds+ρ(t), which corresponds to the function class for any t∈T: (12)G·,t=xt⟼τt+∫ΘtBs,txtds+ρt:βjis,t∈RT×T;ρjt,τjt∈RT.In the above models, the loss function l is usually selected as the mean square error function and then some functional data algorithms are used to find the function that minimizes empirical risk (2) over the function class F. We refer to [16] for more details on functional linear models.


## 2.3. Analysis of Generalization Performance

Different from the i.i.d. learning setting, regardless of the distribution characteristics ofztt≥0, the generalization performance of the aforementioned learning process is also affected by the following factors:(i)
Time-dependence among samples in one sequence.(ii)
The numberM of independent sequences of samples.(iii)
The numberN of samples in one sequence.(iv)
The fixed time pointst1,…,tN, at which the samples zt1,…,ztN are observed.The main concern of this paper is to quantitatively analyze the influence to the generalization performance caused by these factors and then achieve the generalization bound of ERM principle for TDS.Proposition 1.
DenoteΓ∗≔τ0∗,τ1∗,…,τN∗⊂[T1,T2] as an ordered set with T1=τ0∗<τ1∗<⋯<τN∗<T2 and Δτn∗≔τn∗-τn-1∗(1≤n≤N). If the set Γ∗ achieves the supremum(13)supf∈FΓ⊂T1,T2⁡∑n=1NΔτnT∫fzτn,τndPτn-1NM∑m=1M∑n=1Nfztnm,tn,then there holds that(14)supf∈F⁡Ef-E^f≤Φ1+Φ2+Φ3+Φ4,where the quantities Φ1, Φ2, Φ3, and Φ4 are, respectively, defined by(15)Φ1≔∑n=1NΔτn∗T-1Nsupf∈F⁡∫fzτn∗,τn∗dPτn∗;(16)Φ2≔supf∈F⁡1N∑n=1N∫fzτn∗,τn∗dPτn∗-∫fztn,τn∗dPtn;(17)Φ3≔supf∈F⁡1N∑n=1N∫fztn,τn∗dPtn-∫fztn,tndPtn;(18)Φ4≔supf∈F⁡1N∑n=1N∫ftnzdPtn-1MN∑n=1N∑m=1Mftnztnm.This result implies that the behavior of the generalization bound can be described by using the summation of the quantitiesΦ1, Φ2, Φ3, and Φ4. In the next section, we will discuss the properties of the quantities Φ1, Φ2, Φ3, and Φ4, respectively.


## 3. Analysis of Relevant Quantities

As mentioned above, regardless of the distribution characteristics ofztt≥0, there are four factors affecting the generalization performance of the ERM learning process for TDS: time-dependence, the number of TDS sequences, the sample number, and the observing time points, which are actually related to the quantities Φ1, Φ2, Φ3, and Φ4, respectively.Moreover, two mild conditions will be imposed for the following discussion:(C1)
Assume that there exists a constantC1 such that, for all t∈T and f∈F, there holds that(19)∫fzt,tdPt<C1.(C2)
Assume that eachf∈F is differentiable with respect to the time t and there exists a constant C2 such that, for all t≥0 and f∈F, there holds that, for any z∈Z and t∈T,(20)∂f∂tz,t≤C2.The former requires that any function f∈F should have the bounded expectation with respect to the distribution of ztt≥0 at any time t∈T, and the latter implies that all functions in F should have bounded first-order partial derivative with respect to t.


### 3.1. Upper Bound of QuantityΦ1

Under Condition (C1) and recalling (15), we can bound the quantity Φ1 as follows:(21)Φ1≤C1∑n=1NΔτn∗T-1N,which implies that Φ1 is affected by the choice of the specific time sequence Γ∗={τ0∗,τ1∗,…,τN∗} which achieves supremum (13). Note that it is possible that the time sequence Γ∗ is not the unique one which can achieve supremum (13); then we define(22)ΓN∗≔arg⁡minΓ⁡∑n=1NΔτnT-1N.It can be observed that if the time pointsτ1∗,…,τN∗ satisfy that the length of each Δτn∗ (1≤n≤N) is equivalent, the sampling-time error Φ1 is equal tozero. From the probabilistic perspective, it means that ΓN∗ is the one that is closest to uniform distribution among the candidate sequences. In other words, more uniformly the time points in ΓN∗ are distributed and the quantity Φ1 is closer tozero. On the other hand, the uniform distribution of time points τ0∗,τ1∗,…,τN∗ implies that, for the stochastic process ztt≥0, the distributions of zt are identical for all t≤0, which is actually a probability distribution.


### 3.2. Upper Bound of QuantityΦ2

Denote(23)Ft≔f·,t:f∈F,DFtPt,Pτ=supf·,t∈Ft⁡∫fzt,tdPt-∫fzτ,tdPτ,which is the so-called integral probability metric (IPM) between the two distributions Pt and Pτ with respect to the function class Ft. IPM plays an important role in measuring the discrepancy between two distributions in probability theory, and we refer to [17, 18] for more details on IPM.According to (16), we then obtain that(24)Φ2≤1N∑n=1NDFτn∗Ptn,Pτn∗.Particularly, according to (23), if the stochastic process zt≥0 has an identical distribution at any time, the quantity Φ2 is equal tozero.


### 3.3. Upper Bound of QuantityΦ3

According to (17), it follows from the condition of (C2) that(25)Φ3=supf∈F⁡1N∑n=1N∫fztn,τn∗dPtn-∫fztn,tndPtn=supf∈F1N∑n=1N∫∂f∂tztn,ρnτn∗-tnPtn≤C2N∑n=1Nτn∗-tn,where ρn lies between τn∗ and tn. According to (25), quantity Φ3 can be bounded by the summation of the discrepancies between the supremum time points τn∗ and the fixed observation time point tn. Recalling (13), the time points τn∗n=1N are determined by the selection of tnn=1N. It is noteworthy that the time points t1,…,tn usually cannot coincide with τ1∗,…,τN∗.


### 3.4. Upper Bound of QuantityΦ4

Similar to the classical statistical learning theory, the task to boundΦ4 can be divided into three steps: complexity measure of function classes and the deviation and the symmetrization inequalities. Based on Azuma’s inequality, we will obtain a suitable deviation inequality for TDS and then the relevant symmetrization inequality. By using the uniform entropy number, we finally bound the quantity Φ4 in the sense of probability.


#### 3.4.1. Deviation Inequality

LetSN=ztnn=1N be the observation sequence of the stochastic process ztt≥0 with a countable state space Z. By the way presented in [19], a filtration associated with SN can be built as follows:(i)
LetΩN be all subset of ZN.(ii)
SetΩ0=∅,ZN.(iii)
For any1≤n≤N-1, let Ωn be the σ-algebra generated by zt1,…,ztn-1.Then, there naturally holds that(26)Ω0⊂Ω1⊂⋯⊂ΩN.According to Azuma’s inequality [19, 20], since the observation sequences SN[1],…,SN[M] are independent of each other, we obtain the following result.Lemma 2.
Given a functionF:ZN→R, set F≔∑n=1N‍f(ztn,tn) and for any 1≤n≤N, define the associated martingale differences as follows:(27)UnF=EFSN∣Ωn-EFSN∣Ωn-1.Then, there holds that, for any ξ>0,(28)Pr⁡1M∑m=1MFSNm-EFSN>ξ≤2exp⁡-Mξ22∑n=1NUnF2.


#### 3.4.2. Symmetrization Inequality

Symmetrization inequalities are mainly used to replace the expected risk by an empirical risk computed on another sample set that is independent of the given sample set but has the identical distribution. In this manner, some kinds of complexity measures can be incorporated in the resulting bounds.For clarity of presentation, we give a useful notation for the following discussion. Given a sample sequenceSN=ztnn=1N, consider another sample sequence SN′=ztn′n=1N independent of SN. If ztn′ has the same distribution as ztn′ for any 1≤n≤N, the sequence SN′ is called the ghost sample sequence of SN. The following result is a direct extension of the classical symmetrization results of Lemma  2 in [21].Theorem 3.
Assume thatF is a function class consisting of the functions with the range [a,b] and ztt≥0 is a stochastic process with a countable state space Ω⊂RK. Let SNmm=1M and SN′mm=1M be drawn from ztt≥0 in the time interval [T1,T2]. Then given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(29)Pr⁡supf∈F⁡1M∑m=1MFSNm-EFSN>ξ≤2Pr⁡supf∈F⁡1M∑m=1MFSNm-∑m=1MFSN′m>ξ2,where F(SN[m])≔∑n=1N‍f(ztn[m],tn).


#### 3.4.3. Approximate ErrorΦ4

The following is the definition of the covering number and we refer to [22] for details.Definition 4.
LetF be a function class and let d be a metric on F. For any ξ>0, the covering number of F at radius ξ with respect to the metric d, denoted by N(F,ξ,d), is the minimum size of a cover of radius ξ.The uniform entropy number (UEN) is a variant of the covering number and we refer to [22] for details as well. By setting the metric lp(SN) (p>0), the UEN is defined as follows:(30)ln⁡NpF,ξ,N≔supZ12N⁡ln⁡NF,ξ,lpSN.Based on the uniform entropy number, the upper bound of Φ4 can be obtained as follows.Theorem 5.
Assume thatF⊂YX×T with T=[T1,T2] is a function class such that, for any f∈F and any t∈T, the functional f(·;t) is bounded with the range [a,b]. Let ztt≥0 be a stochastic process with a countable state space. Let SNmm=1M be M independent observation sequences of ztt≥0 at the time points t1,t2,…,tN. Let SN′mm=1M be the ghost samples of SNmm=1M and denote S2N[m]≔SNm,SN′m for any 1≤m≤M. Then, given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(31)Pr⁡supf∈F1N∑n=1N∫fztn,tndPtn-1MN∑n=1N∑m=1Mfztnm,tn>ξ≤8N1F,ξ8,2MNexp⁡-MN2ξ2128∑n=1NUnF2.Compared to the classical generalization results for i.i.d. samples (cf. Theorem  2.3 of [22]), time-dependent data are involved in the analysis of upper bound (31). This result is also different from the generalization bound of [7] because more than one sequence of time-dependent samples are investigated. Denote the right-hand side of (31) by ϵ, and under notations of Theorem 5 we immediately obtain that, with probability of at least 1-ϵ,(32)supf∈F⁡EFSN-1M∑m=1MFSNm≤128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2,which explicitly shows the upper bound of Φ4.Finally, according to the upper bounds ofΦi (i=1,2,3,4) and Proposition 1, we can bound supf∈FEf-E^f given in (6) as follows: with probability of at least 1-ϵ,(33)supf∈F⁡Ef-E^f≤C1∑n=1NΔτn∗T-1N+1N∑n=1NDFτn∗Ptn,Pτn∗+C2N∑n=1Nτn∗-tn+128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2.From result (33), we can find that the generalization performance of ERM principle for TDS is affected by the following factors: (i)
The choice of the observation time pointst1,t2,…,tN.(ii)
The numberM of TDS sequences.(iii)
The lengthN of sequences.(iv)
The properties of the martingale differencesUnF.(v)
The complexity of function classes.And meanwhile, the quantitative relationship among these factors is explicitly given in the above result as well.


## 3.1. Upper Bound of QuantityΦ1

Under Condition (C1) and recalling (15), we can bound the quantity Φ1 as follows:(21)Φ1≤C1∑n=1NΔτn∗T-1N,which implies that Φ1 is affected by the choice of the specific time sequence Γ∗={τ0∗,τ1∗,…,τN∗} which achieves supremum (13). Note that it is possible that the time sequence Γ∗ is not the unique one which can achieve supremum (13); then we define(22)ΓN∗≔arg⁡minΓ⁡∑n=1NΔτnT-1N.It can be observed that if the time pointsτ1∗,…,τN∗ satisfy that the length of each Δτn∗ (1≤n≤N) is equivalent, the sampling-time error Φ1 is equal tozero. From the probabilistic perspective, it means that ΓN∗ is the one that is closest to uniform distribution among the candidate sequences. In other words, more uniformly the time points in ΓN∗ are distributed and the quantity Φ1 is closer tozero. On the other hand, the uniform distribution of time points τ0∗,τ1∗,…,τN∗ implies that, for the stochastic process ztt≥0, the distributions of zt are identical for all t≤0, which is actually a probability distribution.


## 3.2. Upper Bound of QuantityΦ2

Denote(23)Ft≔f·,t:f∈F,DFtPt,Pτ=supf·,t∈Ft⁡∫fzt,tdPt-∫fzτ,tdPτ,which is the so-called integral probability metric (IPM) between the two distributions Pt and Pτ with respect to the function class Ft. IPM plays an important role in measuring the discrepancy between two distributions in probability theory, and we refer to [17, 18] for more details on IPM.According to (16), we then obtain that(24)Φ2≤1N∑n=1NDFτn∗Ptn,Pτn∗.Particularly, according to (23), if the stochastic process zt≥0 has an identical distribution at any time, the quantity Φ2 is equal tozero.


## 3.3. Upper Bound of QuantityΦ3

According to (17), it follows from the condition of (C2) that(25)Φ3=supf∈F⁡1N∑n=1N∫fztn,τn∗dPtn-∫fztn,tndPtn=supf∈F1N∑n=1N∫∂f∂tztn,ρnτn∗-tnPtn≤C2N∑n=1Nτn∗-tn,where ρn lies between τn∗ and tn. According to (25), quantity Φ3 can be bounded by the summation of the discrepancies between the supremum time points τn∗ and the fixed observation time point tn. Recalling (13), the time points τn∗n=1N are determined by the selection of tnn=1N. It is noteworthy that the time points t1,…,tn usually cannot coincide with τ1∗,…,τN∗.


## 3.4. Upper Bound of QuantityΦ4

Similar to the classical statistical learning theory, the task to boundΦ4 can be divided into three steps: complexity measure of function classes and the deviation and the symmetrization inequalities. Based on Azuma’s inequality, we will obtain a suitable deviation inequality for TDS and then the relevant symmetrization inequality. By using the uniform entropy number, we finally bound the quantity Φ4 in the sense of probability.


### 3.4.1. Deviation Inequality

LetSN=ztnn=1N be the observation sequence of the stochastic process ztt≥0 with a countable state space Z. By the way presented in [19], a filtration associated with SN can be built as follows:(i)
LetΩN be all subset of ZN.(ii)
SetΩ0=∅,ZN.(iii)
For any1≤n≤N-1, let Ωn be the σ-algebra generated by zt1,…,ztn-1.Then, there naturally holds that(26)Ω0⊂Ω1⊂⋯⊂ΩN.According to Azuma’s inequality [19, 20], since the observation sequences SN[1],…,SN[M] are independent of each other, we obtain the following result.Lemma 2.
Given a functionF:ZN→R, set F≔∑n=1N‍f(ztn,tn) and for any 1≤n≤N, define the associated martingale differences as follows:(27)UnF=EFSN∣Ωn-EFSN∣Ωn-1.Then, there holds that, for any ξ>0,(28)Pr⁡1M∑m=1MFSNm-EFSN>ξ≤2exp⁡-Mξ22∑n=1NUnF2.


### 3.4.2. Symmetrization Inequality

Symmetrization inequalities are mainly used to replace the expected risk by an empirical risk computed on another sample set that is independent of the given sample set but has the identical distribution. In this manner, some kinds of complexity measures can be incorporated in the resulting bounds.For clarity of presentation, we give a useful notation for the following discussion. Given a sample sequenceSN=ztnn=1N, consider another sample sequence SN′=ztn′n=1N independent of SN. If ztn′ has the same distribution as ztn′ for any 1≤n≤N, the sequence SN′ is called the ghost sample sequence of SN. The following result is a direct extension of the classical symmetrization results of Lemma  2 in [21].Theorem 3.
Assume thatF is a function class consisting of the functions with the range [a,b] and ztt≥0 is a stochastic process with a countable state space Ω⊂RK. Let SNmm=1M and SN′mm=1M be drawn from ztt≥0 in the time interval [T1,T2]. Then given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(29)Pr⁡supf∈F⁡1M∑m=1MFSNm-EFSN>ξ≤2Pr⁡supf∈F⁡1M∑m=1MFSNm-∑m=1MFSN′m>ξ2,where F(SN[m])≔∑n=1N‍f(ztn[m],tn).


### 3.4.3. Approximate ErrorΦ4

The following is the definition of the covering number and we refer to [22] for details.Definition 4.
LetF be a function class and let d be a metric on F. For any ξ>0, the covering number of F at radius ξ with respect to the metric d, denoted by N(F,ξ,d), is the minimum size of a cover of radius ξ.The uniform entropy number (UEN) is a variant of the covering number and we refer to [22] for details as well. By setting the metric lp(SN) (p>0), the UEN is defined as follows:(30)ln⁡NpF,ξ,N≔supZ12N⁡ln⁡NF,ξ,lpSN.Based on the uniform entropy number, the upper bound of Φ4 can be obtained as follows.Theorem 5.
Assume thatF⊂YX×T with T=[T1,T2] is a function class such that, for any f∈F and any t∈T, the functional f(·;t) is bounded with the range [a,b]. Let ztt≥0 be a stochastic process with a countable state space. Let SNmm=1M be M independent observation sequences of ztt≥0 at the time points t1,t2,…,tN. Let SN′mm=1M be the ghost samples of SNmm=1M and denote S2N[m]≔SNm,SN′m for any 1≤m≤M. Then, given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(31)Pr⁡supf∈F1N∑n=1N∫fztn,tndPtn-1MN∑n=1N∑m=1Mfztnm,tn>ξ≤8N1F,ξ8,2MNexp⁡-MN2ξ2128∑n=1NUnF2.Compared to the classical generalization results for i.i.d. samples (cf. Theorem  2.3 of [22]), time-dependent data are involved in the analysis of upper bound (31). This result is also different from the generalization bound of [7] because more than one sequence of time-dependent samples are investigated. Denote the right-hand side of (31) by ϵ, and under notations of Theorem 5 we immediately obtain that, with probability of at least 1-ϵ,(32)supf∈F⁡EFSN-1M∑m=1MFSNm≤128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2,which explicitly shows the upper bound of Φ4.Finally, according to the upper bounds ofΦi (i=1,2,3,4) and Proposition 1, we can bound supf∈FEf-E^f given in (6) as follows: with probability of at least 1-ϵ,(33)supf∈F⁡Ef-E^f≤C1∑n=1NΔτn∗T-1N+1N∑n=1NDFτn∗Ptn,Pτn∗+C2N∑n=1Nτn∗-tn+128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2.From result (33), we can find that the generalization performance of ERM principle for TDS is affected by the following factors: (i)
The choice of the observation time pointst1,t2,…,tN.(ii)
The numberM of TDS sequences.(iii)
The lengthN of sequences.(iv)
The properties of the martingale differencesUnF.(v)
The complexity of function classes.And meanwhile, the quantitative relationship among these factors is explicitly given in the above result as well.


## 3.4.1. Deviation Inequality

LetSN=ztnn=1N be the observation sequence of the stochastic process ztt≥0 with a countable state space Z. By the way presented in [19], a filtration associated with SN can be built as follows:(i)
LetΩN be all subset of ZN.(ii)
SetΩ0=∅,ZN.(iii)
For any1≤n≤N-1, let Ωn be the σ-algebra generated by zt1,…,ztn-1.Then, there naturally holds that(26)Ω0⊂Ω1⊂⋯⊂ΩN.According to Azuma’s inequality [19, 20], since the observation sequences SN[1],…,SN[M] are independent of each other, we obtain the following result.Lemma 2.
Given a functionF:ZN→R, set F≔∑n=1N‍f(ztn,tn) and for any 1≤n≤N, define the associated martingale differences as follows:(27)UnF=EFSN∣Ωn-EFSN∣Ωn-1.Then, there holds that, for any ξ>0,(28)Pr⁡1M∑m=1MFSNm-EFSN>ξ≤2exp⁡-Mξ22∑n=1NUnF2.


## 3.4.2. Symmetrization Inequality

Symmetrization inequalities are mainly used to replace the expected risk by an empirical risk computed on another sample set that is independent of the given sample set but has the identical distribution. In this manner, some kinds of complexity measures can be incorporated in the resulting bounds.For clarity of presentation, we give a useful notation for the following discussion. Given a sample sequenceSN=ztnn=1N, consider another sample sequence SN′=ztn′n=1N independent of SN. If ztn′ has the same distribution as ztn′ for any 1≤n≤N, the sequence SN′ is called the ghost sample sequence of SN. The following result is a direct extension of the classical symmetrization results of Lemma  2 in [21].Theorem 3.
Assume thatF is a function class consisting of the functions with the range [a,b] and ztt≥0 is a stochastic process with a countable state space Ω⊂RK. Let SNmm=1M and SN′mm=1M be drawn from ztt≥0 in the time interval [T1,T2]. Then given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(29)Pr⁡supf∈F⁡1M∑m=1MFSNm-EFSN>ξ≤2Pr⁡supf∈F⁡1M∑m=1MFSNm-∑m=1MFSN′m>ξ2,where F(SN[m])≔∑n=1N‍f(ztn[m],tn).


## 3.4.3. Approximate ErrorΦ4

The following is the definition of the covering number and we refer to [22] for details.Definition 4.
LetF be a function class and let d be a metric on F. For any ξ>0, the covering number of F at radius ξ with respect to the metric d, denoted by N(F,ξ,d), is the minimum size of a cover of radius ξ.The uniform entropy number (UEN) is a variant of the covering number and we refer to [22] for details as well. By setting the metric lp(SN) (p>0), the UEN is defined as follows:(30)ln⁡NpF,ξ,N≔supZ12N⁡ln⁡NF,ξ,lpSN.Based on the uniform entropy number, the upper bound of Φ4 can be obtained as follows.Theorem 5.
Assume thatF⊂YX×T with T=[T1,T2] is a function class such that, for any f∈F and any t∈T, the functional f(·;t) is bounded with the range [a,b]. Let ztt≥0 be a stochastic process with a countable state space. Let SNmm=1M be M independent observation sequences of ztt≥0 at the time points t1,t2,…,tN. Let SN′mm=1M be the ghost samples of SNmm=1M and denote S2N[m]≔SNm,SN′m for any 1≤m≤M. Then, given any ξ>0, one has, for any M≥8(b-a)2/(ξ)2,(31)Pr⁡supf∈F1N∑n=1N∫fztn,tndPtn-1MN∑n=1N∑m=1Mfztnm,tn>ξ≤8N1F,ξ8,2MNexp⁡-MN2ξ2128∑n=1NUnF2.Compared to the classical generalization results for i.i.d. samples (cf. Theorem  2.3 of [22]), time-dependent data are involved in the analysis of upper bound (31). This result is also different from the generalization bound of [7] because more than one sequence of time-dependent samples are investigated. Denote the right-hand side of (31) by ϵ, and under notations of Theorem 5 we immediately obtain that, with probability of at least 1-ϵ,(32)supf∈F⁡EFSN-1M∑m=1MFSNm≤128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2,which explicitly shows the upper bound of Φ4.Finally, according to the upper bounds ofΦi (i=1,2,3,4) and Proposition 1, we can bound supf∈FEf-E^f given in (6) as follows: with probability of at least 1-ϵ,(33)supf∈F⁡Ef-E^f≤C1∑n=1NΔτn∗T-1N+1N∑n=1NDFτn∗Ptn,Pτn∗+C2N∑n=1Nτn∗-tn+128ln⁡8N1F,ξ/8,2MN-ln⁡ϵ∑n=1NUnF2MN2.From result (33), we can find that the generalization performance of ERM principle for TDS is affected by the following factors: (i)
The choice of the observation time pointst1,t2,…,tN.(ii)
The numberM of TDS sequences.(iii)
The lengthN of sequences.(iv)
The properties of the martingale differencesUnF.(v)
The complexity of function classes.And meanwhile, the quantitative relationship among these factors is explicitly given in the above result as well.


## 4. Conclusion

In this paper, we propose a new framework to analyze the generalization properties of ERM principle for the sequences of TDS. By introducing four auxiliary quantitiesϕ1, ϕ2, ϕ3, and ϕ4, we give a detailed insight to the interactions among the complexity of function classes, the size of samples, and the dependence among samples. To achieve the upper bound of ϕ4, we develop the relevant deviation inequality and symmetrization inequality for the sequences of TDS. This work is an extension of the classical techniques of statistical learning theory. In our future works, we will consider to relax conditions (C1) and (C2) and further investigate the properties of ERM-based learning processes for the TDS sequences, which are not observed at the fixed observation time points.



---

*Source: 826812-2015-11-19.xml*