# Coefficient-Based Regression with Non-Identical Unbounded Sampling

Authors: Jia Cai
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We investigate a coefficient-based least squares regression problem with indefinite kernels from non-identical unbounded sampling processes. Here non-identical unbounded sampling means the
samples are drawn independently but not identically from unbounded sampling processes. The kernel is not necessarily symmetric or positive semi-definite. This leads to additional difficulty in the error analysis. By introducing a suitable reproducing kernel Hilbert space (RKHS) and a suitable intermediate integral operator, elaborate analysis is presented by means of a novel technique for the sample error. This leads to satisfactory results.


---

## Body

## 1. Introduction and Preliminary

We study coefficient-based least squares regression with indefinite kernels from non-identical unbounded sampling processes. In our setting, functions are defined on a compact subsetX of ℝn and take values in Y=ℝ. Let ρ be a Borel probability measure on Z=X×Y. A sample z={zt=(xt,yt)}t=1T⊂ZT is drawn independently from different Borel probability measures ρ(t) (t=1,…,T), ρ(t)(·∣x)=ρ(·∣x). Let ρX(t) be the marginal distribution of ρ(t) on X and ρX the marginal distribution of ρ on X. We assume that the sequence {ρX(t)} converges exponentially fast in the dual of the Hölder space Cs(X). Here the Hölder space Cs(X) (0≤s≤1) is defined as the space of all continuous functions on X with the following norm finite [1]:
(1)∥f∥Cs(X)=∥f∥∞+|f|Cs(X),
where
(2)|f|Cs(X):=supx≠y∈X|f(x)-f(y)|(d(x,y))s.Definition 1.
Let0≤s≤1; we say that the sequence {ρX(t)} converges exponentially fast in (Cs(X))* to a probability measure ρX on X or converges exponentially in short if there exist C1>0 and 0<α< 1 such that
(3)∥ρX(t)-ρX∥(Cs(X))*≤C1αt,∀t∈ℕ.By the definition of the dual space(Cs(X))*, the decay condition (3) can be expressed as
(4)|∫X‍f(x)dρX(t)-∫X‍f(x)dρX|≤C1αt∥f∥Cs(X),∀f∈Cs(X),t∈ℕ.
The regression function fρ:X→Y is given by
(5)fρ(x)=∫Y‍ydρ(y∣x),x∈X,
where ρ(y∣x) is the conditional distribution of y at x∈X and ρ is unknown, so fρ cannot be obtained directly. The aim of regression problem is to learn a good approximation of fρ from sample z. This is an ill-posed problem and regularization scheme is needed.Classical learning algorithm is conducted by a scheme in a reproducing kernel Hilbert space (RKHS) [2] associated with a Mercer kernel K:X×X→ℝ, which is defined to be a continuous, symmetric, and positive semi-definite (p.s.d.) function. RKHS ℋK is defined to be the completion of the linear span of {Kx=K(·,x):x∈X} with the inner product 〈Kx,Ky〉K=K(x,y). Define κ=supx,v∈X|K(x,v)|<∞; then the regularized regression problem is given by
(6)fz=argminf∈ℋK{1T∑t=1T‍(f(xt)-yt)2+λ∥f∥K2}.
It has been well understood due to lots of the literature ([3–5] and the references therein). Here we consider the indefinite kernel scheme in a hypothesis space ℋK,z depending on the sample z; this space is defined by
(7)ℋK,z={∑i=1T‍βiKxi:βi∈ℝ}.And the regularized penalty term is imposed on the coefficients of functionf. Indefinite kernel K means Kdoes not need to satisfy symmetry and p.s.d. condition except for continuity and boundedness. Define K~(u,v)=∫X‍K(u,x)K(v,x)dρX(x); then K~(u,v) is a Mercer kernel. For more introductions about learning with indefinite kernels, please see [6–8]. For allx∈X, if we define LK,ρXf(x)=∫X‍K(x,u)f(u)dρX(u) and LK,ρX(t)f(x)=∫X‍K(x,u)f(u)dρX(t)(u), since X is compact and K is continous, LK,ρX and its adjoint LK,ρX* are both compact operators. Hence LK~,ρX=LK,ρXLK,ρX*, LK~,ρX(t)=LK,ρX(t)LK,ρX(t)*. The learning algorithm we are interested in this paper takes the following form:(8)fz,λ=argminf∈ℋK,z{1T∑i=1T‍(f(xi)-yi)2+λΩz(f)},λ>0.We define the following coefficient-based regularizer:(9)Ωz(f)=∥f∥z2:=T∑i=1T‍βi2forf=∑i=1T‍βiKxi.Then we havefz,λ=fβz,λ=∑i=1T‍βz,λ,iKxi. By using the integral operator technique from [4], in [9], Sun and Wu gave the capacity independent estimate for the convergence rate of ∥fz,λ-fρ∥ρ2, where ∥f∥ρ=(∫X‍|f(x)|2dρX(x))1/2. Shi investigated the error analysis in a data dependent hypothesis space for general kernels [10]. Sun and Guo conducted error analysis for the Mercer kernels by uniform bounded non-i.i.d. sampling [11]. In this paper, we study learning algorithm (8) by non-identical unbounded sampling processes with indefinite kernels.IfK is a Mercer kernel, from [3] we know that ℋK is in the range of LK1/2. For an indefinite kernel K, recall LK~,ρX=LK,ρXLK,ρX*. Based on the polar decomposition of compact operators ([12]).Lemma 2.
LetH be a separable Hilbert space and T a compact operator on H; then T can be factored as
(10)T=ΓA,
where A=(T*T)1/2 and Γ is a partial isometry on H with Γ*Γ being orthogonal projection onto ℛ(A)-.We immediately have the following proposition [10].Proposition 3.
ConsiderℋK~ as a subspace of LρX2; then LK*=ULK~1/2 and LK=LK~1/2U*, where U is a partial isometry on LρX2 with U*U being the orthogonal projection onto ℋK~-.We use the RKHSℋK~ to approximate fρ, hence define
(11)fλ,ρX=argminf∈ℋK~{∫Z‍(f(x)-fρ(x))2dρ(x,y)+λ∥f∥K~2}.In order to estimatefz,λ-fρ, we construct
(12)fλ,ρ-X(T)=(λI+LK~,ρ-X(T))-1LK~,ρ-X(T)fρ,
where ρ-X(T)=(1/T)∑t=1T‍ρX(t). Then we can decompose the error term into the following three parts:
(13)fz,λ-fρ=fz,λ-fλ,ρ-X(T)+fλ,ρ-X(T)-fλ,ρX+fλ,ρX-fρ.We will conduct the error analysis in several steps. The major contribution we make is on the sample error estimate; the main difficulty is the non-identical unbounded sampling of the samples; we overcome this difficulty by introducing a suitable intermediate operator.


## 2. Key Analysis and Main Results

In order to give the error analysis, we assume that the kernelK~satisfies the following kernel condition [1, 11].Definition 4.
We say that the Mercer kernelK~ satisfies the kernel condition of order s if, for some constant κs>0,K~∈Cs(X×X), and for all u,v∈X,
(14)∥K~u-K~v∥K~≤κs(d(u,v))s.
Since samplez is drawn from unbounded sampling processes, we will assume the following moment hypothesis condition [13].Moment Hypothesis. There exist constants M>0 and C2>0 such that
(15)∫Y‍|y|ldρ(y∣x)≤C2l!Ml∀l∈ℕ,x∈X.There is a large literature on error analysis for learning algorithm (6); see, for example, [4, 5, 14–17]. But most obtained results are presented under the standard assumption that |y|≤M almost surely (M is a constant). This excludes the case of Gaussian noise. The moment hypothesis condition is a natural generalization of the condition |y|≤M. Wang and Zhou considered error analysis for algorithm (6) under condition (15). Our main results are about learning rates of algorithm (8) under conditions (3), (14) and the approximation ability of ℋK~ in terms of fρ.Now we can state our general results on learning rates for algorithm (8).Theorem 5.
Assume moment hypothesis condition (15);ρX(t) satisfies condition (3) and K~ satisfies condition (14); fρ∈LK~,ρXr(LρX2), for 1/2<r≤3/2; take λ=T-θ with 0<θ<1/3; then
(16)𝔼∥fz,λ-fρ∥ρ≤Cκ′′T-min{1/2-(3/2)θ,(r-1/2)θ},
where Cκ′′ is a constant depending on κ,s,andα, but not on T or δ, and will be given explicitly in Section 3.3.Remark 6.
If we takeλ=T-1/2(r+1), then our rate is O(T-(2r-1)/4(r+1)). The proof of Theorem 5 will be conducted in Section 3, where the error term is decomposed into three parts. In [11], the authors consider the coefficient-based regression with the Mercer kernels by uniform bounded non-i.i.d sampling; the best rate of order O(T-2r/(1+2r)) was obtained.
When the samples are drawn i.i.d from measureρ, we have the following result.Theorem 7.
Assume moment hypothesis condition (15);K~ satisfies condition (14); fρ∈LK~,ρXr(LρX2); then if 0<r≤1, take λ=T-1/(2r+3); one see that
(17)𝔼∥fz,λ-fρ∥ρ≤C~κT-r/(2r+3),
where C~κ is a constant depending on κ,s,andα but not on T or δ. And if r>1, take λ=T-1/5; we have
(18)𝔼∥fz,λ-fρ∥ρ≤C~κT-1/5.Here we get the same learning rate as the one in [9]. But our rate is derived under a relaxation condition of the sampling output.


## 3. Error Analysis

In this section, we will state the error analysis in several steps.


### 3.1. Regularization Error Estimation

In this subsection, we address a bound for the regularization error∥fλ,ρX-fρ∥. The error estimate for regularization error has been investigated in lots of the literature in learning theory ([4, 18] and the references therein); we will omit the proof and quote it directly.Proposition 8.
Assumefρ=LK~,ρXr(gρ) for some gρ∈LρX2 and r>0; the following bound for approximation error holds:
(19)∥fλ,ρX-fρ∥ρ≤Cqλq,
where Cq=(1+κ2r-2)∥LK~,ρX-rfρ∥ρ, q=min{r,1}, and when 1/2<r≤3/2,
(20)∥fλ,ρX-fρ∥K~≤Crλr-1/2,
where Cr=∥LK~,ρX-rfρ∥ρ.


### 3.2. Estimate for the Measure Error

This subsection is devoted to the analysis of the term∥fλ,ρ-X(T)-fλ,ρX∥K~ caused by the difference of measures, which we called measure error. The ideas of proof are from [1]. Before giving the result, let us state a crucial lemma first.Lemma 9.
AssumeK~ satisfies condition (14); then
(21)∥LK~,ρ-X(T)-LK~,ρX∥≤(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*.Proof.
For anyh∈Cs(X), we see that
(22)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~2=∫X‍h(u){∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)}×d(ρX-ρ-X(T))(u)≤∥ρX-ρ-X(T)∥(Cs(X))*∥g∥Cs(X)=∥ρX-ρ-X(T)∥(Cs(X))*(∥g∥∞+|g|Cs(X)),
where g(u)=h(u){∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)},u∈X. Now we need to estimate ∥g∥∞ and |g|Cs(X), respectively. For the term ∥g∥∞, it is easy to see that
(23)∥g∥∞≤∥h∥∞supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|.
The estimation of |g|Cs(X) is more involved:
(24)|g|Cs(X)≤|h|Cs(X)supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|+∥h∥∞|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X).supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|≤∥ρX-ρ-X(T)∥(Cs(X))*∥h(·)K~(u,·)∥Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*×{κ2∥h∥∞+|h|Cs(X)κ2+∥h∥∞κκs},|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X)=supu1≠u2∈X|∫X‍h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s×d(ρX-ρ-X(T))(v)K~(u1,v)-K~(u2,v)d(u1,u2)s|≤supu1≠u2∈X∥ρX-ρ-X(T)∥(Cs(X))*×∥h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s∥Cs(X).
Since
(25)supu1≠u2∈X∥h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s∥Cs(X)≤∥h∥∞supu1≠u2∈Xsupv∈X|K~(u1,v)-K~(u2,v)d(u1,u2)s|+|h|Cs(X)supu1≠u2∈Xsupv∈X|K~(u1,v)-K~(u2,v)d(u1,u2)s|+∥h∥∞supu1≠u2∈Xsupv1≠v2∈X((d(u1,u2)sd(v1,v2)s)-1|K~(u1,v2)-K~(u2,v2)-K~(u1,v1)+K~(u2,v1)|×(d(u1,u2)sd(v1,v2)s)-1)≤∥h∥Cs(X)κκs+∥h∥∞κs2,
then
(26)|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*∥h∥Cs(X)(κκs+κs2).
Therefore
(27)|g|Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*×[|h|Cs(X){κ2∥h∥Cs(X)+∥h∥∞κκs}+∥h∥∞∥h∥Cs(X)(κκs+κs2)].
Combining the estimation of ∥g∥∞ and |g|Cs(X), we get
(28)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~2≤∥h∥Cs(X)2∥ρX-ρ-X(T)∥(Cs(X))*2(κ+κs)2.
When condition (14) is satisfied, it was proved in [19] that ℋK~ is included in Cs(X) with the inclusion bounded
(29)∥f∥Cs(X)≤(κ+κs)∥f∥K~,∀f∈ℋK~.
Then
(30)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~≤∥h∥K~(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*.
This completes the proof.Proposition 10.
Assumefρ∈LK~,ρXr(LρX2) for some 1/2<r≤3/2; K~ satisfies condition (14); the following bound for measure error holds:
(31)∥fλ,ρ-X(T)-fλ,ρX∥K~≤C3λr-3/2T,
where Cκ=(κ+κs2)2andC3=C1CκCrα/(1-α).Proof.
From (11), simple calculation shows that fλ,ρX=(λI+LK~,ρX)-1LK~,ρXfρ. Recalling (12), we can see that
(32)∥fλ,ρ-X(T)-fλ,ρX∥K~=∥(λI+LK~,ρ-X(T))-1{(LK~,ρ-X(T)-LK~,ρX)fρ+(LK~,ρX-LK~,ρ-X(T))fλ,ρX}(λI+LK~,ρ-X(T))-1{(LK~,ρ-X(T)-LK~,ρX)fρ∥K~=∥(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)-LK~,ρX)(fρ-fλ,ρX)∥K~≤1λ∥(LK~,ρ-X(T)-LK~,ρX)(fρ-fλ,ρX)∥K~.
Applying Lemma 9 to the case h=fρ-fλ,ρX, we get
(33)∥fλ,ρ-X(T)-fλ,ρX∥K~≤1λ(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*∥fλ,ρX-fρ∥K~.
By the definition of ρ-X(T) and noticing (3), we can see
(34)∥ρX-ρ-X(T)∥Cs(X)*=1T∑t=1T‍∥ρX(t)-ρX∥(Cs(X))*≤C1αT(1-α).
This in connection with Proposition8 yields the conclusion.


### 3.3. Sample Error Estimation

In this subsection we will conduct the estimation of the termfz,λ-fλ,ρ-X(T). At first, we give some notations. Let C(X) be the space of bounded continuous functions on X with supremum norm ∥·∥∞. Define sampling operator Sx:C(X)→ℝT by Sx(f)=(f(x1),…,f(xT)) ([18]). For β=(β1,…,βT), let Ux and U^x be operators from ℝT to C(X) defined as
(35)Uxβ=1T∑i=1T‍βiK(x,xi),U^xβ=1T∑i=1T‍βiK(xi,x).It is easy to see that bothUx and U^x are bounded operators. Recall the definition of fz,λ; then
(36)βz,λ=argminβ∈ℝT{1T∑i=1T‍(fβ(xi)-yi)2+λT∑i=1T‍βi2}.
Computing the gradient of the above equation, we immediately have [9]
(37)βz,λ=1T(λI+SxU^xSxUx)-1SxU^xy.
Hence fz,λ=Ux(λI+SxU^xSxUx)-1SxU^xy. Employing the method as shown in [9], we can decompose the sample error into two parts:
(38)fz,λ-fλ,ρ-X(T)=Ux(λI+SxU^xSxUx)-1SxU^xy-(λI+LK~,ρ-X(T))-1LK~,ρ-X(T)fρ={(λI+LK~,ρ-X(T))-1UxSxU^xyUx(λI+SxU^xSxUx)-1SxU^xyo-(λI+LK~,ρ-X(T))-1UxSxU^xy}+{(λI+LK~,ρ-X(T))-1UxSxU^xy-(λI+LK~,ρ-X(T))-1LK~,ρ-X(T)fρ}=I+II.Now we state our estimation for the sample error. The estimates are more involved since the sample is drawn by non-identical unbounded sampling processes. We overcome the difficulty by introducing a stepping integral operatorLK^,ρ-X(T) which plays an intermediate role in the estimates, and the definition of it will be given later.Theorem 11.
Letfz,λ be given by (8), assume moment hypothesis condition  (15), and the marginal distribution sequence ρX(t),t∈ℕ, satisfies condition (3); then
(39)𝔼∥fz,λ-fλ,ρ-X(T)∥ρ≤Cκ′λ3/2T1/2,
where C4=αC1κM(κ+2|K|Cs(X×X))(κ2C2+C2), Cκ′=43C2Mκ2+45C2Mκ3+C4/(1-α).Proof.
We will estimateI and II, respectively:
(40)I=(λI+LK~,ρ-X(T))-1(λI+LK~,ρ-X(T))×Ux(λI+SxU^xSxUx)-1SxU^xy-(λI+LK~,ρ-X(T))-1Ux(λI+SxU^xSxUx)×(λI+SxU^xSxUx)-1SxU^xy=(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)Ux-UxSxU^xSxUx)×(λI+SxU^xSxUx)-1SxU^xy=(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)Ux-UxSxU^xSxUx)Tβz,λ.
Then
(41)∥I∥ρ≤λ-1T∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥∥βz,λ∥2+λ-1T∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥∥βz,λ∥2,
where K^(x,u)=∫X‍K(x,v)K(u,v)dρ-X(T)(v) and ∥βz,λ∥2 is the l2 norm on ℝT, for ∥βz,λ∥2; noticing (36), we can have
(42)λT∥βz,λ∥22≤1T∑i=1T‍yi2.
This means
(43)𝔼∥I∥ρ≤λ-1T(𝔼∥βz,λ∥22)1/2{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}≤λ-3/2T(𝔼(1T∑i=1T‍yi2))1/2×{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}≤λ-3/22C2TM{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}.
According to the definition of Ux, for any β∈ℝT, ∥Uxβ∥ρ≤(κ/T)∥β∥2; this implies that ∥Ux∥≤κ/T. Therefore
(44)∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥=sup∥β∥2≤1∥1T∑i=1T‍βi∫X‍(K~(x,u)-K^(x,u))i×K(u,xi)dρ-X(T)(u)∑i=1T‍∥ρ≤sup∥β∥2≤11T∑i=1T‍|βi|∥dρ-X(T)(u)∫X‍[K~(x,u)-K^(x,u)]2)12(∫X‍K2(u,xi)dρ-X(T)(u))1/2i×(∫X‍[K~(x,u)-K^(x,u)]2i×dρ-X(T)(u)∫X‍[K~(x,u)-K^(x,u)]2)1/2(∫X‍K2(u,xi)dρ-X(T)(u))12∥ρ≤κT∥∫X‍K(x,v)K(u,v)d(ρ-X(T)-ρX)(v)∥∞≤κT∥ρ-X(T)-ρX∥(Cs(X))*∥K(x,·)K(u,·)∥Cs(X)≤αC1κ2(κ+2|K|Cs(X×X))T3/2(1-α).
Hence
(45)(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2≤αC1κ2(κ+2|K|Cs(X×X))T3/2(1-α).
For the term ∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥, let
(46)ηt,j,l(x)=K(xt,xl)K(xt,xj)K(x,xj)-∬XK(x,v)K(u,v)K(u,xl)dρX(j)(v)dρX(t)(u),
and ξl(x)=(1/T2)∑t,j=1T‍ηt,j,l. Then |ηt,j,l|≤2κ3 and
(47)∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥=sup∥β∥2≤1∥(LK^,ρ-X(T)Ux-UxSxU^xSxUx)β∥ρ=sup∥β∥2≤1∥1T∑l=1T‍βlξl∥ρ≤1T3(∫X‍∑l=1T‍(∑t,j=1T‍ηt,j,l)2dρX)1/2=1T3(∫X‍∑t,j,w,τ,l=1T‍ηt,j,l(x)ηw,τ,l(x)dρX)1/2.
Applying the same method as shown in the proof of Lemma 4.1 in [9], we can see that when all the indices t,j,w,τ,andl are pairwise different, there holds 𝔼x(ηt,j,l(x)ηw,τ,l(x))=0; therefore
(48)(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2≤1T3(𝔼x(∑t,j,w,τ,l=1T‍ηt,j,l(x)ηw,τ,l(x)))1/2≤2κ3T3T5-T(T-1)(T-2)(T-3)(T-4)≤210κ3T.
This together with (45) yields
(49)𝔼∥I∥ρ≤2C2M(210κ3λ3/2T1/2+αC1κ2(κ+2|K|Cs(X×X))λ3/2T(1-α)).
The termII is more involved; recall that
(50)II=(λI+LK~,ρ-X(T))-1(UxSxU^xy-LK~,ρ-X(T)fρ)=(λI+LK~,ρ-X(T))-1{UxSxU^xy-LK^,ρ-X(T)fρ+LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ}.
Hence
(51)𝔼∥II∥ρ≤λ-1(𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ+𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ).
If we defineηtj(x)=ytK(xt,xj)K(x,xj) and
(52)ξtj(x)=ηtj(x)-∬XK(x,u)K(v,u)fρ(v)dρX(j)(u)dρX(t)(v),(t,j=1,…,T),
therefore
(53)𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ2≤T-4∑t,j,w,τ=1T‍𝔼zξtj(x)ξwτ(x).
If t,j,w,andτ are pairwise distinct, then 𝔼z(ξtj(x)ξwτ(x))=0. If t=j or w=τ,
(54)𝔼zηtt≠∬XK(x,u)K(v,u)fρ(v)dρX(t)(u)dρX(t)(v),𝔼zηww≠∬XK(x,u)K(v,u)fρ(v)dρX(w)(u)dρX(w)(v).
By the Cauchy-Schwartz inequality, for any t,j,w,τ=1,…,T,
(55)𝔼zξtj(x)ξwτ(x)≤(𝔼zξtj2(x))1/2(𝔼zξwτ2(x))1/2≤max{𝔼zξtj2(x),𝔼zξwτ2(x)}.
Hence we only need to give a bound for 𝔼zξtj2. Simple calculation shows
(56)𝔼zξtj2≤𝔼zηtj2≤∬XK2(x,u)K2(v,u)×∫Y‍y2dρ(y∣v)dρX(j)(u)dρX(t)(v)≤2C2M2κ4,(t≠j).
By the same method, we know that
(57)𝔼zξtt2=𝔼zηtt2-2𝔼zηtt∬XK(x,u)K(v,u)×∫Y‍ydρ(y∣v)dρX(t)(u)dρX(t)(v)+(∬XK(x,u)K(v,u)fρ(v)dρX(t)(u)dρX(t)(v))2≤∫X‍K2(v,v)K2(x,v)×∫Y‍y2dρ(y∣v)dρX(t)(v)+2C2M2κ4-2∫X‍K(v,v)K(x,v)∫Y‍ydρ(y∣v)dρX(t)(v)×∬XK(x,u)K(v,u)×∫Y‍ydρ(y∣v)dρX(t)(u)dρX(t)(v)≤8C2M2κ4.
Applying the conclusion as shown in [9] and together with the above bound, we can see that
(58)T-4∑t,j,w,τ=1T‍𝔼zξtj(x)ξwτ(x)≤8T-4(T4-T(T-1)(T-2)(T-3))C2M2κ4≤48C2M2κ4T.
Hence
(59)𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ≤43C2Mκ2T,𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ≤∥∫X‍(K^(x,v)-K~(x,v))fρ(v)dρ-X(T)(v)∥ρ≤∥fρ∥∞∥∫X‍K(x,u)K(v,u)d(ρ-X(T)-ρX)(u)∥∞≤C2M∥ρ-X(T)-ρX∥(Cs(X))*∥K(x,·)K(v,·)∥Cs(X)≤αC1κ(κ+2|K|Cs(X×X))C2MT(1-α).
This yields(60)𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ≤αC1κ(κ+2|K|Cs(X×X))C2MT(1-α);
then
(61)𝔼∥II∥ρ≤43C2Mκ2λT+αC1κ(κ+2|K|Cs(X×X))C2MλT(1-α).
This together with (49) yields the conclusion.Now we are in a position to give the proofs of Theorems5 and 7.Proof of Theorem5.
Theorem11 ensures that
(62)𝔼∥fz,λ-fλ,ρ-X(T)∥ρ≤Cκ′λ3/2T1/2.
For1/2<r≤3/2, Proposition 10 tells that
(63)∥fλ,ρ-X(T)-fλ,ρX∥K~≤C3λr-3/2T,
and Proposition 8 shows that
(64)∥fλ,ρX-fρ∥K~≤Crλr-1/2,
since
(65)∥f∥ρ≤∥f∥∞≤κ∥f∥K~,∀f∈ℋK~.
Combining all the bounds together and noting thatλ=T-θ with 0<θ<1/3, we can get the conclusion of Theorem 5 by taking Cκ′′=(C3+Cr)κ+Cκ′.Proof of Theorem7.
When the samples are drawn i.i.d. from measureρ, then fλ,ρ-X(T)=fλ,ρX. Hence
(66)𝔼∥fz,λ-fρ∥ρ≤𝔼∥fz,λ-fλ,ρX∥ρ+𝔼∥fλ,ρX-fρ∥ρ≤Cκ′λ3/2T1/2+Cqλq.
Let λ=T-θ; then
(67)𝔼∥fz,λ-fρ∥ρ≤C~κT-min{1/2-(3/2)θ,qθ}.
The conclusion follows by discussing the relationship betweenr and 1.


## 3.1. Regularization Error Estimation

In this subsection, we address a bound for the regularization error∥fλ,ρX-fρ∥. The error estimate for regularization error has been investigated in lots of the literature in learning theory ([4, 18] and the references therein); we will omit the proof and quote it directly.Proposition 8.
Assumefρ=LK~,ρXr(gρ) for some gρ∈LρX2 and r>0; the following bound for approximation error holds:
(19)∥fλ,ρX-fρ∥ρ≤Cqλq,
where Cq=(1+κ2r-2)∥LK~,ρX-rfρ∥ρ, q=min{r,1}, and when 1/2<r≤3/2,
(20)∥fλ,ρX-fρ∥K~≤Crλr-1/2,
where Cr=∥LK~,ρX-rfρ∥ρ.


## 3.2. Estimate for the Measure Error

This subsection is devoted to the analysis of the term∥fλ,ρ-X(T)-fλ,ρX∥K~ caused by the difference of measures, which we called measure error. The ideas of proof are from [1]. Before giving the result, let us state a crucial lemma first.Lemma 9.
AssumeK~ satisfies condition (14); then
(21)∥LK~,ρ-X(T)-LK~,ρX∥≤(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*.Proof.
For anyh∈Cs(X), we see that
(22)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~2=∫X‍h(u){∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)}×d(ρX-ρ-X(T))(u)≤∥ρX-ρ-X(T)∥(Cs(X))*∥g∥Cs(X)=∥ρX-ρ-X(T)∥(Cs(X))*(∥g∥∞+|g|Cs(X)),
where g(u)=h(u){∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)},u∈X. Now we need to estimate ∥g∥∞ and |g|Cs(X), respectively. For the term ∥g∥∞, it is easy to see that
(23)∥g∥∞≤∥h∥∞supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|.
The estimation of |g|Cs(X) is more involved:
(24)|g|Cs(X)≤|h|Cs(X)supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|+∥h∥∞|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X).supu∈X|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|≤∥ρX-ρ-X(T)∥(Cs(X))*∥h(·)K~(u,·)∥Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*×{κ2∥h∥∞+|h|Cs(X)κ2+∥h∥∞κκs},|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X)=supu1≠u2∈X|∫X‍h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s×d(ρX-ρ-X(T))(v)K~(u1,v)-K~(u2,v)d(u1,u2)s|≤supu1≠u2∈X∥ρX-ρ-X(T)∥(Cs(X))*×∥h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s∥Cs(X).
Since
(25)supu1≠u2∈X∥h(v)K~(u1,v)-K~(u2,v)d(u1,u2)s∥Cs(X)≤∥h∥∞supu1≠u2∈Xsupv∈X|K~(u1,v)-K~(u2,v)d(u1,u2)s|+|h|Cs(X)supu1≠u2∈Xsupv∈X|K~(u1,v)-K~(u2,v)d(u1,u2)s|+∥h∥∞supu1≠u2∈Xsupv1≠v2∈X((d(u1,u2)sd(v1,v2)s)-1|K~(u1,v2)-K~(u2,v2)-K~(u1,v1)+K~(u2,v1)|×(d(u1,u2)sd(v1,v2)s)-1)≤∥h∥Cs(X)κκs+∥h∥∞κs2,
then
(26)|∫X‍h(v)K~(u,v)d(ρX-ρ-X(T))(v)|Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*∥h∥Cs(X)(κκs+κs2).
Therefore
(27)|g|Cs(X)≤∥ρX-ρ-X(T)∥(Cs(X))*×[|h|Cs(X){κ2∥h∥Cs(X)+∥h∥∞κκs}+∥h∥∞∥h∥Cs(X)(κκs+κs2)].
Combining the estimation of ∥g∥∞ and |g|Cs(X), we get
(28)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~2≤∥h∥Cs(X)2∥ρX-ρ-X(T)∥(Cs(X))*2(κ+κs)2.
When condition (14) is satisfied, it was proved in [19] that ℋK~ is included in Cs(X) with the inclusion bounded
(29)∥f∥Cs(X)≤(κ+κs)∥f∥K~,∀f∈ℋK~.
Then
(30)∥(LK~,ρ-X(T)-LK~,ρX)h∥K~≤∥h∥K~(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*.
This completes the proof.Proposition 10.
Assumefρ∈LK~,ρXr(LρX2) for some 1/2<r≤3/2; K~ satisfies condition (14); the following bound for measure error holds:
(31)∥fλ,ρ-X(T)-fλ,ρX∥K~≤C3λr-3/2T,
where Cκ=(κ+κs2)2andC3=C1CκCrα/(1-α).Proof.
From (11), simple calculation shows that fλ,ρX=(λI+LK~,ρX)-1LK~,ρXfρ. Recalling (12), we can see that
(32)∥fλ,ρ-X(T)-fλ,ρX∥K~=∥(λI+LK~,ρ-X(T))-1{(LK~,ρ-X(T)-LK~,ρX)fρ+(LK~,ρX-LK~,ρ-X(T))fλ,ρX}(λI+LK~,ρ-X(T))-1{(LK~,ρ-X(T)-LK~,ρX)fρ∥K~=∥(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)-LK~,ρX)(fρ-fλ,ρX)∥K~≤1λ∥(LK~,ρ-X(T)-LK~,ρX)(fρ-fλ,ρX)∥K~.
Applying Lemma 9 to the case h=fρ-fλ,ρX, we get
(33)∥fλ,ρ-X(T)-fλ,ρX∥K~≤1λ(κ+κs)2∥ρX-ρ-X(T)∥(Cs(X))*∥fλ,ρX-fρ∥K~.
By the definition of ρ-X(T) and noticing (3), we can see
(34)∥ρX-ρ-X(T)∥Cs(X)*=1T∑t=1T‍∥ρX(t)-ρX∥(Cs(X))*≤C1αT(1-α).
This in connection with Proposition8 yields the conclusion.


## 3.3. Sample Error Estimation

In this subsection we will conduct the estimation of the termfz,λ-fλ,ρ-X(T). At first, we give some notations. Let C(X) be the space of bounded continuous functions on X with supremum norm ∥·∥∞. Define sampling operator Sx:C(X)→ℝT by Sx(f)=(f(x1),…,f(xT)) ([18]). For β=(β1,…,βT), let Ux and U^x be operators from ℝT to C(X) defined as
(35)Uxβ=1T∑i=1T‍βiK(x,xi),U^xβ=1T∑i=1T‍βiK(xi,x).It is easy to see that bothUx and U^x are bounded operators. Recall the definition of fz,λ; then
(36)βz,λ=argminβ∈ℝT{1T∑i=1T‍(fβ(xi)-yi)2+λT∑i=1T‍βi2}.
Computing the gradient of the above equation, we immediately have [9]
(37)βz,λ=1T(λI+SxU^xSxUx)-1SxU^xy.
Hence fz,λ=Ux(λI+SxU^xSxUx)-1SxU^xy. Employing the method as shown in [9], we can decompose the sample error into two parts:
(38)fz,λ-fλ,ρ-X(T)=Ux(λI+SxU^xSxUx)-1SxU^xy-(λI+LK~,ρ-X(T))-1LK~,ρ-X(T)fρ={(λI+LK~,ρ-X(T))-1UxSxU^xyUx(λI+SxU^xSxUx)-1SxU^xyo-(λI+LK~,ρ-X(T))-1UxSxU^xy}+{(λI+LK~,ρ-X(T))-1UxSxU^xy-(λI+LK~,ρ-X(T))-1LK~,ρ-X(T)fρ}=I+II.Now we state our estimation for the sample error. The estimates are more involved since the sample is drawn by non-identical unbounded sampling processes. We overcome the difficulty by introducing a stepping integral operatorLK^,ρ-X(T) which plays an intermediate role in the estimates, and the definition of it will be given later.Theorem 11.
Letfz,λ be given by (8), assume moment hypothesis condition  (15), and the marginal distribution sequence ρX(t),t∈ℕ, satisfies condition (3); then
(39)𝔼∥fz,λ-fλ,ρ-X(T)∥ρ≤Cκ′λ3/2T1/2,
where C4=αC1κM(κ+2|K|Cs(X×X))(κ2C2+C2), Cκ′=43C2Mκ2+45C2Mκ3+C4/(1-α).Proof.
We will estimateI and II, respectively:
(40)I=(λI+LK~,ρ-X(T))-1(λI+LK~,ρ-X(T))×Ux(λI+SxU^xSxUx)-1SxU^xy-(λI+LK~,ρ-X(T))-1Ux(λI+SxU^xSxUx)×(λI+SxU^xSxUx)-1SxU^xy=(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)Ux-UxSxU^xSxUx)×(λI+SxU^xSxUx)-1SxU^xy=(λI+LK~,ρ-X(T))-1(LK~,ρ-X(T)Ux-UxSxU^xSxUx)Tβz,λ.
Then
(41)∥I∥ρ≤λ-1T∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥∥βz,λ∥2+λ-1T∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥∥βz,λ∥2,
where K^(x,u)=∫X‍K(x,v)K(u,v)dρ-X(T)(v) and ∥βz,λ∥2 is the l2 norm on ℝT, for ∥βz,λ∥2; noticing (36), we can have
(42)λT∥βz,λ∥22≤1T∑i=1T‍yi2.
This means
(43)𝔼∥I∥ρ≤λ-1T(𝔼∥βz,λ∥22)1/2{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}≤λ-3/2T(𝔼(1T∑i=1T‍yi2))1/2×{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}≤λ-3/22C2TM{(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2+(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2}.
According to the definition of Ux, for any β∈ℝT, ∥Uxβ∥ρ≤(κ/T)∥β∥2; this implies that ∥Ux∥≤κ/T. Therefore
(44)∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥=sup∥β∥2≤1∥1T∑i=1T‍βi∫X‍(K~(x,u)-K^(x,u))i×K(u,xi)dρ-X(T)(u)∑i=1T‍∥ρ≤sup∥β∥2≤11T∑i=1T‍|βi|∥dρ-X(T)(u)∫X‍[K~(x,u)-K^(x,u)]2)12(∫X‍K2(u,xi)dρ-X(T)(u))1/2i×(∫X‍[K~(x,u)-K^(x,u)]2i×dρ-X(T)(u)∫X‍[K~(x,u)-K^(x,u)]2)1/2(∫X‍K2(u,xi)dρ-X(T)(u))12∥ρ≤κT∥∫X‍K(x,v)K(u,v)d(ρ-X(T)-ρX)(v)∥∞≤κT∥ρ-X(T)-ρX∥(Cs(X))*∥K(x,·)K(u,·)∥Cs(X)≤αC1κ2(κ+2|K|Cs(X×X))T3/2(1-α).
Hence
(45)(𝔼∥LK~,ρ-X(T)Ux-LK^,ρ-X(T)Ux∥2)1/2≤αC1κ2(κ+2|K|Cs(X×X))T3/2(1-α).
For the term ∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥, let
(46)ηt,j,l(x)=K(xt,xl)K(xt,xj)K(x,xj)-∬XK(x,v)K(u,v)K(u,xl)dρX(j)(v)dρX(t)(u),
and ξl(x)=(1/T2)∑t,j=1T‍ηt,j,l. Then |ηt,j,l|≤2κ3 and
(47)∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥=sup∥β∥2≤1∥(LK^,ρ-X(T)Ux-UxSxU^xSxUx)β∥ρ=sup∥β∥2≤1∥1T∑l=1T‍βlξl∥ρ≤1T3(∫X‍∑l=1T‍(∑t,j=1T‍ηt,j,l)2dρX)1/2=1T3(∫X‍∑t,j,w,τ,l=1T‍ηt,j,l(x)ηw,τ,l(x)dρX)1/2.
Applying the same method as shown in the proof of Lemma 4.1 in [9], we can see that when all the indices t,j,w,τ,andl are pairwise different, there holds 𝔼x(ηt,j,l(x)ηw,τ,l(x))=0; therefore
(48)(𝔼∥LK^,ρ-X(T)Ux-UxSxU^xSxUx∥2)1/2≤1T3(𝔼x(∑t,j,w,τ,l=1T‍ηt,j,l(x)ηw,τ,l(x)))1/2≤2κ3T3T5-T(T-1)(T-2)(T-3)(T-4)≤210κ3T.
This together with (45) yields
(49)𝔼∥I∥ρ≤2C2M(210κ3λ3/2T1/2+αC1κ2(κ+2|K|Cs(X×X))λ3/2T(1-α)).
The termII is more involved; recall that
(50)II=(λI+LK~,ρ-X(T))-1(UxSxU^xy-LK~,ρ-X(T)fρ)=(λI+LK~,ρ-X(T))-1{UxSxU^xy-LK^,ρ-X(T)fρ+LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ}.
Hence
(51)𝔼∥II∥ρ≤λ-1(𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ+𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ).
If we defineηtj(x)=ytK(xt,xj)K(x,xj) and
(52)ξtj(x)=ηtj(x)-∬XK(x,u)K(v,u)fρ(v)dρX(j)(u)dρX(t)(v),(t,j=1,…,T),
therefore
(53)𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ2≤T-4∑t,j,w,τ=1T‍𝔼zξtj(x)ξwτ(x).
If t,j,w,andτ are pairwise distinct, then 𝔼z(ξtj(x)ξwτ(x))=0. If t=j or w=τ,
(54)𝔼zηtt≠∬XK(x,u)K(v,u)fρ(v)dρX(t)(u)dρX(t)(v),𝔼zηww≠∬XK(x,u)K(v,u)fρ(v)dρX(w)(u)dρX(w)(v).
By the Cauchy-Schwartz inequality, for any t,j,w,τ=1,…,T,
(55)𝔼zξtj(x)ξwτ(x)≤(𝔼zξtj2(x))1/2(𝔼zξwτ2(x))1/2≤max{𝔼zξtj2(x),𝔼zξwτ2(x)}.
Hence we only need to give a bound for 𝔼zξtj2. Simple calculation shows
(56)𝔼zξtj2≤𝔼zηtj2≤∬XK2(x,u)K2(v,u)×∫Y‍y2dρ(y∣v)dρX(j)(u)dρX(t)(v)≤2C2M2κ4,(t≠j).
By the same method, we know that
(57)𝔼zξtt2=𝔼zηtt2-2𝔼zηtt∬XK(x,u)K(v,u)×∫Y‍ydρ(y∣v)dρX(t)(u)dρX(t)(v)+(∬XK(x,u)K(v,u)fρ(v)dρX(t)(u)dρX(t)(v))2≤∫X‍K2(v,v)K2(x,v)×∫Y‍y2dρ(y∣v)dρX(t)(v)+2C2M2κ4-2∫X‍K(v,v)K(x,v)∫Y‍ydρ(y∣v)dρX(t)(v)×∬XK(x,u)K(v,u)×∫Y‍ydρ(y∣v)dρX(t)(u)dρX(t)(v)≤8C2M2κ4.
Applying the conclusion as shown in [9] and together with the above bound, we can see that
(58)T-4∑t,j,w,τ=1T‍𝔼zξtj(x)ξwτ(x)≤8T-4(T4-T(T-1)(T-2)(T-3))C2M2κ4≤48C2M2κ4T.
Hence
(59)𝔼∥UxSxU^xy-LK^,ρ-X(T)fρ∥ρ≤43C2Mκ2T,𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ≤∥∫X‍(K^(x,v)-K~(x,v))fρ(v)dρ-X(T)(v)∥ρ≤∥fρ∥∞∥∫X‍K(x,u)K(v,u)d(ρ-X(T)-ρX)(u)∥∞≤C2M∥ρ-X(T)-ρX∥(Cs(X))*∥K(x,·)K(v,·)∥Cs(X)≤αC1κ(κ+2|K|Cs(X×X))C2MT(1-α).
This yields(60)𝔼∥LK^,ρ-X(T)fρ-LK~,ρ-X(T)fρ∥ρ≤αC1κ(κ+2|K|Cs(X×X))C2MT(1-α);
then
(61)𝔼∥II∥ρ≤43C2Mκ2λT+αC1κ(κ+2|K|Cs(X×X))C2MλT(1-α).
This together with (49) yields the conclusion.Now we are in a position to give the proofs of Theorems5 and 7.Proof of Theorem5.
Theorem11 ensures that
(62)𝔼∥fz,λ-fλ,ρ-X(T)∥ρ≤Cκ′λ3/2T1/2.
For1/2<r≤3/2, Proposition 10 tells that
(63)∥fλ,ρ-X(T)-fλ,ρX∥K~≤C3λr-3/2T,
and Proposition 8 shows that
(64)∥fλ,ρX-fρ∥K~≤Crλr-1/2,
since
(65)∥f∥ρ≤∥f∥∞≤κ∥f∥K~,∀f∈ℋK~.
Combining all the bounds together and noting thatλ=T-θ with 0<θ<1/3, we can get the conclusion of Theorem 5 by taking Cκ′′=(C3+Cr)κ+Cκ′.Proof of Theorem7.
When the samples are drawn i.i.d. from measureρ, then fλ,ρ-X(T)=fλ,ρX. Hence
(66)𝔼∥fz,λ-fρ∥ρ≤𝔼∥fz,λ-fλ,ρX∥ρ+𝔼∥fλ,ρX-fρ∥ρ≤Cκ′λ3/2T1/2+Cqλq.
Let λ=T-θ; then
(67)𝔼∥fz,λ-fρ∥ρ≤C~κT-min{1/2-(3/2)θ,qθ}.
The conclusion follows by discussing the relationship betweenr and 1.



---

*Source: 134727-2013-06-03.xml*