# The Learning Rates of Regularized Regression Based on Reproducing Kernel Banach Spaces

Authors: Baohuai Sheng; Peixin Ye
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

We study the convergence behavior of regularized regression based on reproducing kernel Banach spaces (RKBSs). The convex inequality of uniform convex Banach spaces is used to show the robustness of the optimal solution with respect to the distributions. The learning rates are derived in terms of the covering number andK-functional.


---

## Body

## 1. Introduction

Recently, there is an increasing research interest in learning with abstract functional spaces, and considerable work has been done in [1–3] and so on.Let(ℬ,∥·∥ℬ)be a normed vector space consisting of real functions on a compact distance space(X,d(·,·)),  and let M>0be a given positive number. Let z={zi}i=1m={(xi,yi)}i=1m∈Zm=(X×[-M,M])mbe a finite set of samples drawn independently and identically (i.i.d.) according to a distributionρ(x,y)onZ.Then, the regularized learning scheme associating with a given hypothesis spaceℬand the least square loss is
(1)fz∶=argminf∈ℬ(1m∑i=1m‍(yi-f(xi))2+λq∥f∥ℬq),whereq≥1is a given real number. The unknown Borel probability distributionρ(x,y)can be decomposed intoρ(y∣x)andρX(x), where ρ(y∣x) is the conditional probability of ρ at x∈X and ρX(x) is the marginal probability on X.The regression function corresponding to the least square loss is(2)fρ(x)=∫[-M,M]‍ydρ(y∣x),which satisfies(3)fρ(x):=argminfℰρ(f)=argminf∫Z‍(y-f(x))2dρ.When the hypothesis spacesℬin (1) are reproducing kernel Banach spaces, we call it the RKBSs based on regularized regression learning defined by [4, 5] recently. The represented theorem related closely to regularized learning is studied in case thatℬis an RKBS, and the discussions are extended to the generalized semi-inner-product RKBSs in [6].In the present paper, we will provide an investigation on the learning rates of scheme (1) whenℬis an RKBS with uniform convexity. The paper is organized as follows. In Section 2, we show the main results of the present paper. The robustness is studied in Section 3, and the sample errors are bounded in Section 4. The approximation error boils down to a K-functional. The learning rates are bounded in Section 5.For a given real numberp≥1, we denote byLp(ρX)the class ofρX-measurable functionsfsatisfying ∥f∥Lp(ρX)=(∫X|f(x)|pdρX‍)<+∞.We sayA=O(B) if there is a constantC>0such thatA/B≤C. We say A~Bif bothA=O(B)andB=O(A).


## 2. Notions and Results

To state the results of the present paper, we first introduce some notions as follows.


### 2.1. The RKBSs

We denote byℬthe Banach space with dual spaceℬ*and norm∥·∥ℬ. Forf∈ℬand f*∈ℬ*, we write〈f,f*〉ℬ=f*(f).A reproducing kernel Banach space (RKBS) onXis a reflexive Banach space of real functions onXwhose dual spaceℬ*is isometric to a Banach spaceℬ#of functions on X, and the point evaluations are continuous functions on bothℬand ℬ#. It was shown by Theorem  2 of [4] that ifBis an RKBS onX, then, there exists uniquely a functionK:X×X→ℜ called the reproducing kernel ofℬsatisfying the following:(i)
K(x,·)∈ℬ, K(·,x)∈ℬ*, x∈X;(ii)
f(x)=〈f,K(·,x)〉ℬ, f*(x)=〈K(x,·),f*〉ℬ, f*∈ℬ*,  x∈X.(iii)
The linear span of{K(x,·):x∈X}is dense inℬ, namely,
(4)span¯{K(x,·):x∈X}=ℬ.(iv)
The linear span of{K(·,x):x∈X}is dense inℬ*, namely,
(5)
span
¯
{
K
(
·
,
x
)
:
x
∈
X
}
=
ℬ
*
.(v)
For allx,y∈Xthere holdsK(x,y)=〈K(x,·),K(·,y)〉ℬ.Whenℬis an RKHS,Kis indeed the reproducing kernel in the usual sense (see [7]).Sinceℬis a reflective Banach space, we have
(6)〈f,f*〉ℬ≤∥f∥ℬ×∥f*∥ℬ*,f∈ℬ,f*∈ℬ*,(7)∥f*∥ℬ*=sup∥f∥ℬ≤1〈f,f*〉ℬ.A way of producing reproducing kernel spaces inLp spaces by the idempotent integral operators was provided in [8]. In the present paper, we provide a method to construct RKBSs by orthogonal function series.Example 1.
LetX=[a,b]be a given closed interval and let,{φk(x)}k=0+∞be a sequence of continuous functions on[a,b]satisfying the following:(i)
φk∈Lp(ρ)fork=0,1,2,…;(ii)
φkandφlare orthonormal (inL2(ρ)) whenl≠k;(iii)
span({φk(x)}k=0+∞)is dense inLp(ρ)for1<p<+∞.
Let{λl}l=0+∞be a given positive real number sequence satisfying ∑l=0+∞λl≤1. Define
(8)K(x,y)=∑l=0∞‍λlφl(x)φl(y),x,y∈X,
and the functional classℬK(p)onXby
(9)ℬK(p)={f∈C(X):∥f∥ℬK(p)=(∑l=0∞‍|al(f)|p′λl)1/p′<+∞},
whereak(f)=∫[a,b]‍f(y)φk(y)dρ(y),k∈N. We define the spaceℬK(p′)forp′=p/(p-1)in an analogous way.We have the following proposition.Proposition 2.
Define a bivariate operation onℬK(p)andℬK(p′)by
(10)〈f,g〉=∑l=0∞‍al(f)al(g)λl,f∈ℬK(p),g∈ℬK(p′).
Then,ℬK(p)is a reproducing kernel Banach space with reproducing kernelK(x,y).Proof.
LetlKp={a={ak}k=0+∞:∥a∥lKp=(∑l=0∞(|al|p/λl))1/p<+∞} andlKp′be defined in an analogous way. Then, bothlKpandlKp′are Banach spaces and(lKp)*=lKp′and(lKp′)*=lKp.By (9) we knowℬK(p)andlKp′are isometric isomorphisms. Therefore,ℬK(p)are Banach spaces.Sinceal(K(·,y))=λlφl(y), we have for f∈ℬK(p) that
(11)〈f,K(·,y)〉=∑l=0∞‍al(f)al(K(·,y))λl〈f,K(·,y)〉=∑l=0∞‍al(f)φl(y)=f(y).By the same way, we have for anyg∈ℬK(p′) that 〈K(x,·),g〉=g(x); that is, the reproducing property holds.


### 2.2.  The Uniform Convexity

In this subsection, we focus on some notions in convex analysis and Banach geometry theory.LetF(f):ℬ→ℜ be a convex function. Then,
(12)∂F(f)={ξ∈ℬ*:F(f′)-F(f)≥〈f′-f,ξ〉ℬ,∀f′∈ℬ}≠ϕ.We call∂F(f)the subdifferential ofF(f)atf∈ℬ. Ifξ∈∂F(f), then, we callξa subgradient ofFatf.A well-known result is thatf0is a minimal value point of a convex functionF(f)onℬif and only if0∈∂F(f0)(see [9]).A Banach spaceℬis calledq-uniform convex if there are constantsq>0,  c>0such that the modulus defined by
(13)δℬ(ɛ)=inf(1-∥f+g∥ℬ2:∥f∥ℬ=∥g∥ℬ=1,∥f-g∥ℬ=ɛ),ɛ∈(0,2]satisfiesδℬ(ɛ)≥cɛq.In particular, any Hilbert spaces are 2-uniform convex Banach spaces.DefineJq(f)ℬ=∂((1/q)∥f∥ℬq).Then, by (28) in Corollary  1 of [10] we knowℬisq-uniform convex if and only if there is a positive constantcq>0such that for allf,g∈ℬ and all jq(f)∈Jq(f)ℬ there holds
(14)1q(∥f∥ℬq-∥g∥ℬq)≥〈jq(g),f-g〉ℬ+cq∥f-g∥ℬq,∀f,g∈ℬ.In [11–14] we know that, for a given 1<p<+∞, the space lp, the Lebesgue spacesLpand the Sobolev spaceWpmaremax{2,p}-uniform convex. Also, letℬK(p)andℬK(p′)be defined as in Section 2.1. Then, by the fact thatℬK(p)andlKp′ are isometric isomorphisms, we knowℬK(p)is2-uniform convex ifp>2andp′-uniform convex if1<p≤2. Therefore, we knowℬK(p)is aq-uniform convex Banach space, whereqis 2 ifp>2and its value isp/(p-1)if1<p≤2.


### 2.3. Main Results

LetSbe a distance space andη>0. The covering number𝒩(S,η) is defined to be the minimal positive integer numberlsuch that there existsldisk inSwith radiusηcoveringS.We say a compact subsetEin a distance space(ℬ,∥·∥ℬ) has logarithmic complexity exponents≥0if there is a constantcs>0such that the closed ball of radiusRcentered at origin, that is, ℬR={f∈E:∥f∥ℬ≤R}, satisfies
(15)log𝒩(ℬR,η)≤cs(Rη)s,∀η>0.Now we are in a position to present the main results of this paper.Theorem 3.
Letℬbe an RKBS withq-uniform convexity and a reproducing kernel K(·,x)which is uniform continuous onXin terms of the norm∥·∥ℬ*, that is, ∥K(·,x)∥ℬ*. ∥K(·,x)∥ℬ* is a uniform continuous function onX, and there is a constantk>0such that∥K(·,x)∥ℬ*≤kholds for allx∈X. Letfzbe the unique minimizer of scheme (1). Iffρ∈L2(ρX), then for anyϵ>0there holds
(16)Probz∈Zm(∥fz-fρ∥L2(ρX)≤kϵ+Dq(fρ,λq))≥1-2𝒩(ℬ1,λcqϵq-18γq)×exp(-mλ2cq2ϵ2(q-1)32k2γq2),
where(17)Dq(fρ,λ)=inff∈ℬ(∥f-fρ∥L2(ρX)2+λ∥f∥ℬq)
is aK-functional,γq∶=M+k(qDq(fρ,λ/q)/λ)1/qand
(18)ℬ1={f(x):f∈ℬ,∥f∥ℬ≤1}.The covering number involved in (16) has been studied widely (see [15–19]). In this paper, we assume 𝒩(ℬR,η)has the logarithmic complexity.Theorem 4.
Under the conditions of Theorem3, if fρ∈L2(ρX) and (ℬ,∥·∥ℬ)has logarithmic complexity with exponent s≥0, then for any δ∈(0,1), with confidence 1-δ, there holds
(19)∥fz-fρ∥L2(ρX)≤k[(64γq2log(2/δ)mλ2cq2)1/2(q-1)+(82+sγq2+scsmλ2+scq2+s)1/(2+s)(q-1)]+Dq(fρ,λq),
wherecsis defined in (15).We now give some remarks on Theorems3 and 4.(i)
In Theorem3, we require that the kernelK(x,y)is uniform continuous and uniform bounded onX. In fact, a large class of real bivariate functions satisfies these conditions. For example, if the function sequence{φl(x)}l=0+∞defined in Example 1 is uniformly bounded, that is, |φl(x)|≤1holds for allland allx∈[a,b], then, kernelK(x,y) is  continuous on [a,b]×[a,b]which turns out that K(x,y) is uniform continuous on [a,b]×[a,b]. Therefore, |K(x,y)|≤∑l=0+∞λl≤1 shows that K(x,y) is uniform continuous and bounded with norm ∥·∥Lp(ρ).(ii)
By the definition ofγq,  we know that if Dq(fρ,λ)=O(λβ),0<β≤1, then, γq=M+O(qλβ-1)1/q. It is bounded if β=1.(iii)
Ifℬ is a reproducing kernel Hilbert space, then, q=2,  cq=1. Moreover, if Dq(fρ,λ)=O(λβ),0<β≤1, then, we have by (19) that
(20)∥fz-fρ∥L2(ρX)=O[(log(2/δ)mλ3-β)1/2+(1mλ(2+s)(3-β)/2)1/(2+s)+λβ/2].(iv)
We can show a way of bounding the decay rates ofDq(fρ,λ) for 1<p≤2. Letf∈Lp(ρ). Then, we have the following Fourier expansion:
(21)
f
(
x
)
~
∑
l
=
0
∞
‍
a
l
(
f
)
φ
l
(
x
)
.
Define an operator sequence by(22)Vn(f,x)=∑l=0n‍λlal(f)φl(x),x∈X.
Then, for a given positive integernwe haveal(Vn(f))=λlal(f)and
(23)∥Vn(f)∥ℬK(p)=(∑l=0∞‍|al(Vn(f))|p′λl)1/p′∥Vn(f)∥ℬK(p)=(∑l=0n‍λlp′-1|al(f)|p′)1/p′∥Vn(f)∥ℬK(p)≤(max0≤l≤nλl1-(1/p′))(∑l=0+∞‍|al(f)|p′)1/p′∥Vn(f)∥ℬK(p)≤(max0≤l≤nλl1-(1/p′))∥f∥Lp(ρ),
where we have used the generalized Bessel inequality (see [20]):
(24)(∑l=0+∞‍|al(f)|p′)1/p′≤∥f∥Lp(ρ).
Also,(25)〈Vn(f),K(·,y)〉=∑l=0∞‍al(Vn(f))al(K(·,y))λl〈Vn(f),K(·,y)〉=∑l=0n‍λlal(f)φl(y)=Vn(f,y).
By (25) and (23) we knowVn(f)∈ℬK(p)holds for all positive integersnand, in this case,
(26)Dq(fρ,λ)≤∥Vn(fρ)-fρ∥L2(ρX)2+λ∥Vn(fρ)∥ℬK(p)qDq(fρ,λ)≤∥Vn(fρ)-fρ∥L2(ρX)2Dq(fρ,λ)+λ(max0≤l≤nλl1-(1/p′))q∥f∥Lp(ρ).
One can choose suitablensuch that it depends upon the sample numbermand obtain the decay rates whenm→+∞.There are many choices for the type of operator (22). For example, the Bernstein-Durrmeyer operators (see, e.g., [21–23]) and the de la Valle´e-Poussin sum operators are such types (see [24]). This method was first provided by [25] and was extended in [26, 27].
(v)
We know from [19] that the RKHSs with logarithmic complexity with exponents≥0  exist. By Corollary  4.1 and Theorem  2.1 of [16] we know that ifλlsatisfyλl~1/(1+l)α,α>1, then, the covering number ofℬK(2)may attain the decay of complexity exponent. In a recent paper (see [28]), Guntuboyina and Sen showed that the set of all convex functions defined on[a,b]dthat are uniform bounded has the logarithmic complexity exponentd/2in theLp-metric.


## 2.1. The RKBSs

We denote byℬthe Banach space with dual spaceℬ*and norm∥·∥ℬ. Forf∈ℬand f*∈ℬ*, we write〈f,f*〉ℬ=f*(f).A reproducing kernel Banach space (RKBS) onXis a reflexive Banach space of real functions onXwhose dual spaceℬ*is isometric to a Banach spaceℬ#of functions on X, and the point evaluations are continuous functions on bothℬand ℬ#. It was shown by Theorem  2 of [4] that ifBis an RKBS onX, then, there exists uniquely a functionK:X×X→ℜ called the reproducing kernel ofℬsatisfying the following:(i)
K(x,·)∈ℬ, K(·,x)∈ℬ*, x∈X;(ii)
f(x)=〈f,K(·,x)〉ℬ, f*(x)=〈K(x,·),f*〉ℬ, f*∈ℬ*,  x∈X.(iii)
The linear span of{K(x,·):x∈X}is dense inℬ, namely,
(4)span¯{K(x,·):x∈X}=ℬ.(iv)
The linear span of{K(·,x):x∈X}is dense inℬ*, namely,
(5)
span
¯
{
K
(
·
,
x
)
:
x
∈
X
}
=
ℬ
*
.(v)
For allx,y∈Xthere holdsK(x,y)=〈K(x,·),K(·,y)〉ℬ.Whenℬis an RKHS,Kis indeed the reproducing kernel in the usual sense (see [7]).Sinceℬis a reflective Banach space, we have
(6)〈f,f*〉ℬ≤∥f∥ℬ×∥f*∥ℬ*,f∈ℬ,f*∈ℬ*,(7)∥f*∥ℬ*=sup∥f∥ℬ≤1〈f,f*〉ℬ.A way of producing reproducing kernel spaces inLp spaces by the idempotent integral operators was provided in [8]. In the present paper, we provide a method to construct RKBSs by orthogonal function series.Example 1.
LetX=[a,b]be a given closed interval and let,{φk(x)}k=0+∞be a sequence of continuous functions on[a,b]satisfying the following:(i)
φk∈Lp(ρ)fork=0,1,2,…;(ii)
φkandφlare orthonormal (inL2(ρ)) whenl≠k;(iii)
span({φk(x)}k=0+∞)is dense inLp(ρ)for1<p<+∞.
Let{λl}l=0+∞be a given positive real number sequence satisfying ∑l=0+∞λl≤1. Define
(8)K(x,y)=∑l=0∞‍λlφl(x)φl(y),x,y∈X,
and the functional classℬK(p)onXby
(9)ℬK(p)={f∈C(X):∥f∥ℬK(p)=(∑l=0∞‍|al(f)|p′λl)1/p′<+∞},
whereak(f)=∫[a,b]‍f(y)φk(y)dρ(y),k∈N. We define the spaceℬK(p′)forp′=p/(p-1)in an analogous way.We have the following proposition.Proposition 2.
Define a bivariate operation onℬK(p)andℬK(p′)by
(10)〈f,g〉=∑l=0∞‍al(f)al(g)λl,f∈ℬK(p),g∈ℬK(p′).
Then,ℬK(p)is a reproducing kernel Banach space with reproducing kernelK(x,y).Proof.
LetlKp={a={ak}k=0+∞:∥a∥lKp=(∑l=0∞(|al|p/λl))1/p<+∞} andlKp′be defined in an analogous way. Then, bothlKpandlKp′are Banach spaces and(lKp)*=lKp′and(lKp′)*=lKp.By (9) we knowℬK(p)andlKp′are isometric isomorphisms. Therefore,ℬK(p)are Banach spaces.Sinceal(K(·,y))=λlφl(y), we have for f∈ℬK(p) that
(11)〈f,K(·,y)〉=∑l=0∞‍al(f)al(K(·,y))λl〈f,K(·,y)〉=∑l=0∞‍al(f)φl(y)=f(y).By the same way, we have for anyg∈ℬK(p′) that 〈K(x,·),g〉=g(x); that is, the reproducing property holds.


## 2.2.  The Uniform Convexity

In this subsection, we focus on some notions in convex analysis and Banach geometry theory.LetF(f):ℬ→ℜ be a convex function. Then,
(12)∂F(f)={ξ∈ℬ*:F(f′)-F(f)≥〈f′-f,ξ〉ℬ,∀f′∈ℬ}≠ϕ.We call∂F(f)the subdifferential ofF(f)atf∈ℬ. Ifξ∈∂F(f), then, we callξa subgradient ofFatf.A well-known result is thatf0is a minimal value point of a convex functionF(f)onℬif and only if0∈∂F(f0)(see [9]).A Banach spaceℬis calledq-uniform convex if there are constantsq>0,  c>0such that the modulus defined by
(13)δℬ(ɛ)=inf(1-∥f+g∥ℬ2:∥f∥ℬ=∥g∥ℬ=1,∥f-g∥ℬ=ɛ),ɛ∈(0,2]satisfiesδℬ(ɛ)≥cɛq.In particular, any Hilbert spaces are 2-uniform convex Banach spaces.DefineJq(f)ℬ=∂((1/q)∥f∥ℬq).Then, by (28) in Corollary  1 of [10] we knowℬisq-uniform convex if and only if there is a positive constantcq>0such that for allf,g∈ℬ and all jq(f)∈Jq(f)ℬ there holds
(14)1q(∥f∥ℬq-∥g∥ℬq)≥〈jq(g),f-g〉ℬ+cq∥f-g∥ℬq,∀f,g∈ℬ.In [11–14] we know that, for a given 1<p<+∞, the space lp, the Lebesgue spacesLpand the Sobolev spaceWpmaremax{2,p}-uniform convex. Also, letℬK(p)andℬK(p′)be defined as in Section 2.1. Then, by the fact thatℬK(p)andlKp′ are isometric isomorphisms, we knowℬK(p)is2-uniform convex ifp>2andp′-uniform convex if1<p≤2. Therefore, we knowℬK(p)is aq-uniform convex Banach space, whereqis 2 ifp>2and its value isp/(p-1)if1<p≤2.


## 2.3. Main Results

LetSbe a distance space andη>0. The covering number𝒩(S,η) is defined to be the minimal positive integer numberlsuch that there existsldisk inSwith radiusηcoveringS.We say a compact subsetEin a distance space(ℬ,∥·∥ℬ) has logarithmic complexity exponents≥0if there is a constantcs>0such that the closed ball of radiusRcentered at origin, that is, ℬR={f∈E:∥f∥ℬ≤R}, satisfies
(15)log𝒩(ℬR,η)≤cs(Rη)s,∀η>0.Now we are in a position to present the main results of this paper.Theorem 3.
Letℬbe an RKBS withq-uniform convexity and a reproducing kernel K(·,x)which is uniform continuous onXin terms of the norm∥·∥ℬ*, that is, ∥K(·,x)∥ℬ*. ∥K(·,x)∥ℬ* is a uniform continuous function onX, and there is a constantk>0such that∥K(·,x)∥ℬ*≤kholds for allx∈X. Letfzbe the unique minimizer of scheme (1). Iffρ∈L2(ρX), then for anyϵ>0there holds
(16)Probz∈Zm(∥fz-fρ∥L2(ρX)≤kϵ+Dq(fρ,λq))≥1-2𝒩(ℬ1,λcqϵq-18γq)×exp(-mλ2cq2ϵ2(q-1)32k2γq2),
where(17)Dq(fρ,λ)=inff∈ℬ(∥f-fρ∥L2(ρX)2+λ∥f∥ℬq)
is aK-functional,γq∶=M+k(qDq(fρ,λ/q)/λ)1/qand
(18)ℬ1={f(x):f∈ℬ,∥f∥ℬ≤1}.The covering number involved in (16) has been studied widely (see [15–19]). In this paper, we assume 𝒩(ℬR,η)has the logarithmic complexity.Theorem 4.
Under the conditions of Theorem3, if fρ∈L2(ρX) and (ℬ,∥·∥ℬ)has logarithmic complexity with exponent s≥0, then for any δ∈(0,1), with confidence 1-δ, there holds
(19)∥fz-fρ∥L2(ρX)≤k[(64γq2log(2/δ)mλ2cq2)1/2(q-1)+(82+sγq2+scsmλ2+scq2+s)1/(2+s)(q-1)]+Dq(fρ,λq),
wherecsis defined in (15).We now give some remarks on Theorems3 and 4.(i)
In Theorem3, we require that the kernelK(x,y)is uniform continuous and uniform bounded onX. In fact, a large class of real bivariate functions satisfies these conditions. For example, if the function sequence{φl(x)}l=0+∞defined in Example 1 is uniformly bounded, that is, |φl(x)|≤1holds for allland allx∈[a,b], then, kernelK(x,y) is  continuous on [a,b]×[a,b]which turns out that K(x,y) is uniform continuous on [a,b]×[a,b]. Therefore, |K(x,y)|≤∑l=0+∞λl≤1 shows that K(x,y) is uniform continuous and bounded with norm ∥·∥Lp(ρ).(ii)
By the definition ofγq,  we know that if Dq(fρ,λ)=O(λβ),0<β≤1, then, γq=M+O(qλβ-1)1/q. It is bounded if β=1.(iii)
Ifℬ is a reproducing kernel Hilbert space, then, q=2,  cq=1. Moreover, if Dq(fρ,λ)=O(λβ),0<β≤1, then, we have by (19) that
(20)∥fz-fρ∥L2(ρX)=O[(log(2/δ)mλ3-β)1/2+(1mλ(2+s)(3-β)/2)1/(2+s)+λβ/2].(iv)
We can show a way of bounding the decay rates ofDq(fρ,λ) for 1<p≤2. Letf∈Lp(ρ). Then, we have the following Fourier expansion:
(21)
f
(
x
)
~
∑
l
=
0
∞
‍
a
l
(
f
)
φ
l
(
x
)
.
Define an operator sequence by(22)Vn(f,x)=∑l=0n‍λlal(f)φl(x),x∈X.
Then, for a given positive integernwe haveal(Vn(f))=λlal(f)and
(23)∥Vn(f)∥ℬK(p)=(∑l=0∞‍|al(Vn(f))|p′λl)1/p′∥Vn(f)∥ℬK(p)=(∑l=0n‍λlp′-1|al(f)|p′)1/p′∥Vn(f)∥ℬK(p)≤(max0≤l≤nλl1-(1/p′))(∑l=0+∞‍|al(f)|p′)1/p′∥Vn(f)∥ℬK(p)≤(max0≤l≤nλl1-(1/p′))∥f∥Lp(ρ),
where we have used the generalized Bessel inequality (see [20]):
(24)(∑l=0+∞‍|al(f)|p′)1/p′≤∥f∥Lp(ρ).
Also,(25)〈Vn(f),K(·,y)〉=∑l=0∞‍al(Vn(f))al(K(·,y))λl〈Vn(f),K(·,y)〉=∑l=0n‍λlal(f)φl(y)=Vn(f,y).
By (25) and (23) we knowVn(f)∈ℬK(p)holds for all positive integersnand, in this case,
(26)Dq(fρ,λ)≤∥Vn(fρ)-fρ∥L2(ρX)2+λ∥Vn(fρ)∥ℬK(p)qDq(fρ,λ)≤∥Vn(fρ)-fρ∥L2(ρX)2Dq(fρ,λ)+λ(max0≤l≤nλl1-(1/p′))q∥f∥Lp(ρ).
One can choose suitablensuch that it depends upon the sample numbermand obtain the decay rates whenm→+∞.There are many choices for the type of operator (22). For example, the Bernstein-Durrmeyer operators (see, e.g., [21–23]) and the de la Valle´e-Poussin sum operators are such types (see [24]). This method was first provided by [25] and was extended in [26, 27].
(v)
We know from [19] that the RKHSs with logarithmic complexity with exponents≥0  exist. By Corollary  4.1 and Theorem  2.1 of [16] we know that ifλlsatisfyλl~1/(1+l)α,α>1, then, the covering number ofℬK(2)may attain the decay of complexity exponent. In a recent paper (see [28]), Guntuboyina and Sen showed that the set of all convex functions defined on[a,b]dthat are uniform bounded has the logarithmic complexity exponentd/2in theLp-metric.


## 3. Robustness

Robustness is a quantitative description of the solutions on the distributions.Define theρ-control integral regularized model corresponding to (1) by
(27)f(ρ)∶=argminf∈ℬ(ℰρ(f)+λq∥f∥ℬq),whereℰρ(f)is defined in (3). Then,f(ρ)is influenced by the distributionsρ. For any boundedρ-measurable functionf(x,y)onZ, we define the empirical measureγz(x,y)as follows:
(28)Eγz[f(x,y)]=∫Z‍f(x,y)dγz=1m∑i=1m‍f(xi,yi).Then,fz=f(γz).We give the following theorem.Theorem 5.
Letℬbe an RKBS withq-uniform convexity and the reproducing kernelK(x,y), and let f(ρ)andf(γ)be the solutions of scheme (27) with respect to distributionsρandγ,   respectively. Then,
(29)∥f(ρ)-f(γ)∥ℬ≤(2λcq×∥∫Z‍(y-f(ρ)(x))K(·,x)dρ-∫Z‍(y-f(ρ)(x))K(·,x)dγ∥ℬ*)1/(q-1),
wherecqis the constant defined in (14).Theorem5 shows howρinfluences the unique solutionf(ρ).To prove Theorem5, we need the following lemmas.Lemma 6.
Under the conditions of Theorem5, there holds
(30)∂ℰρ(f0)={-2∫Z‍(y-f0(x))K(·,x)dρ},f0∈ℬ,
where the point·inK(·,x)meansK(·,x)∈ℬfor anyx∈X.Proof.
We restate the following statement.
Let(ℬ,∥·∥ℬ)be a Banach space, F(f):ℬ→ℜ⋃‍{∓∞}be a real function. We sayFis Gateaux differentiable atf0∈ℬif there is anξ∈ℬ*such that for anyg∈ℬthere holds
(31)limt→0F(f0+tg)-F(f0)t=〈g,ξ〉ℬ,
and writeFG′(f0)=ξ.By [29] we know that  ifFis convex onℬand is Gateaux differentiable atf0∈ℬ, then,∂F(f0)={FG′(f0)}.
By equality(32)x2-y2=2y(x-y)+(x-y)2,x,y∈ℜ,
we have for anyg(x)=〈g,K(·,x)〉ℬ∈ℬ that
(33)limt→0ℰρ(f0+tg)-ℰρ(f0)t=limt→0∫Z‍(y-f0(x)-tg(x))2dρ-∫Z‍(y-f0(x))2dρt=limt→0-2t∫Z‍(y-f0(x))g(x)dρ+t2∫Z‍g(x)2dρt=-2∫Z‍(y-f0(x))g(x)dρ=〈g,-2∫Z‍(y-f0(x))K(·,x)dρ〉ℬ.
Sinceℰρ(f)is a convex function onℬ, we know (30) holds.Lemma 7.
TakeJq(f)=∂((1/q)∥f∥ℬq). Then, under the conditions of Theorem 5, there hold the following.(i)
There exists uniquely a minimizerf(ρ)of the problem (27) and
(34)∥f(ρ)∥ℬ≤(qDq(fρ,λ/q)λ)1/q.(ii)
There is ajq(f(ρ))∈Jq(f(ρ))such that
(35)λjq(f(ρ))=2∫Z‍(y-f(ρ)(x))K(·,x)dρ.Proof.
The uniqueness of the minimizer can be obtained by the fact that (27) is a strict convex optimization problem. By the definition off(ρ), we have
(36)λq∥f(ρ)∥ℬq≤λq∥f(ρ)∥ℬq+ℰρ(f(ρ))-ℰρ(fρ)λq∥f(ρ)∥ℬq=Dq(fρ,λq).
We then have (34).Proof of (35).
Sincef(ρ)is the unique solution of (27), we have
(37)0∈∂f(ℰρ(f)+λq∥f∥ℬq)|f=f(ρ).
Notice that bothℰρ(f)and∥f∥ℬqare convex functions aboutfonℬ. We have
(38)∂f(ℰρ(f)+λq∥f∥ℬq)|f=f(ρ)=∂f(ℰρ(f))|f=f(ρ)+∂f(λq∥f∥ℬq)|f=f(ρ).
By (30), we know that  (37) leads to
(39)0∈{-2∫Z‍(y-f(ρ)(x))K(·,x)dρ}+λJq(f(ρ)).
Therefore, there isjq(f(ρ))∈Jq(f(ρ))such that (35) holds.Lemma 8.
Letℬbe an RKBS satisfying the conditions of Theorem 3. Then,
(40)|f(x)|≤k∥f∥ℬ,x∈X,f∈ℬ.Proof.
The reproducing property and (16) give
(41)|f(x)|=|〈f,K(·,x)〉ℬ|≤∥f∥ℬ×∥K(·,x)∥ℬ*.
Then, the fact∥K(·,x)∥ℬ*≤kgives (40).Lemma 9.
LetK(x,y) be the reproducing kernel of ℬ,   and K(·,x) is uniform continuous about x on X in norm∥·∥ℬ*, R>0 be a given real number. Then, the ball ℬR={f∈ℬ:∥f∥ℬ≤R} is a compact subset of C(X).Proof.
SinceXis a compact distance space, so is X×X. SinceK(·,x)is uniform continuous aboutxin norm∥·∥ℬ*, we know that for anyϵ>0there is aδ>0such that for allx,x′∈X with d(x,x′)<δ, we have
(42)∥K(·,x)-K(·,x′)∥ℬ*<ϵ
and for anyf∈ℬRholds
(43)|f(x)-f(x′)|=|〈f,K(·,x)〉ℬ-〈f,K(·,x′)〉ℬ|=|〈f,K(·,x)-K(·,x′)〉ℬ|≤∥f∥ℬ×∥K(·,x)-K(·,x′)∥ℬ*≤Rϵ.
By (43), we know that ℬRis a closed, bounded, and equicontinuous set. Therefore, ℬR is a compact set of C(X).Proof of Theorem5.
By the definition of∂ℰγ(f(ρ))and (30) we know
(44)ℰγ(f(γ))-ℰγ(f(ρ))≥〈f(γ)-f(ρ),-2∫Z‍(y-f(ρ)(x))K(·,x)dγ〉ℬ.
Also, by (44) and the definitions of f(ρ) and f(γ) we have
(45)0≥(∫Z‍(y-f(γ)(x))2dγ+λq∥f(γ)∥ℬq)0≥-(∫Z‍(y-f(ρ)(x))2dγ+λq∥f(ρ)∥ℬq)0=ℰγ(f(γ))-ℰγ(f(ρ))+λq(∥f(γ)∥ℬq-∥f(ρ)∥ℬq)0≥2〈f(γ)-f(ρ),-∫Z‍(y-f(ρ)(x))K(·,x)dγ〉ℬ0+λq(∥f(γ)∥ℬq-∥f(ρ)∥ℬq).
Sinceℬisq-uniform convex, we have by (14) and the definition ofjq(f(ρ))that
(46)1q(∥f(γ)∥ℬq-∥f(ρ)∥ℬq)≥〈f(γ)-f(ρ),jq(f(ρ))〉ℬ+cq∥f(γ)-f(ρ)∥ℬq.
Combining (46) with (45), we have
(47)0≥(∫Z‍(y-f(γ)(x))2dγ+λq∥f(γ)∥ℬq)-(∫Z‍(y-f(ρ)(x))2dγ+λq∥f(ρ)∥ℬq)≥2〈f(ρ)-f(γ),∫Z‍(y-f(ρ)(x))K(·,x)dγ〉ℬ+λ〈f(γ)-f(ρ),jq(f(ρ))〉ℬ+λcq∥f(γ)-f(ρ)∥ℬq=(35)2〈f(ρ)-f(γ),∫Z‍(y-f(ρ)(x))K(·,x)dγ〉ℬ-2〈f(ρ)-f(γ),∫Z‍(y-f(ρ)(x))K(·,x)dρ〉ℬ+λcq∥f(γ)-f(ρ)∥ℬq=2〈∫Z‍(y-f(ρ)(x))K(·,x)dγ-∫Z‍(y-f(ρ)(x))K(·,x)dρ,f(ρ)-f(γ)〉ℬ+λcq∥f(γ)-f(ρ)∥ℬq.
It follows that(48)λcq∥f(γ)-f(ρ)∥ℬq≤2〈f(γ)-f(ρ),∫Z‍(y-f(ρ)(x))K(·,x)dγ-∫Z‍(y-f(ρ)(x))K(·,x)dρ〉ℬ≤2∥f(γ)-f(ρ)∥ℬ×∥∫Z‍(y-f(ρ)(x))K(·,x)dρ-∫Z‍(y-f(ρ)(x))K(·,x)dγ∥ℬ*.
We then have (29).


## 4. Sample Error

We give the following sample error bounds.Theorem 10.
Letℬbe an RKBS satisfying the conditions of Theorem 3.f(ρ)is the solution of scheme (27) with respect toρandfzis the solution of (1). Then, for all ϵ>0there hold
(49)Probz∈Zm{∥f(ρ)-fz∥ℬ≤ϵ}≥1-2𝒩(ℱ,λcqϵq-18)exp(-mλ2cq2ϵ2(q-1)32γq2),
where(50)ℱ={h(z)f(x):f∈ℬ,∥f∥ℬ≤1,∥h∥C(Z)≤γq}.To show Theorem10, we first give a lemma.Lemma 11 (see [15]).
Letℱbe a family of functions from a probability spaceZtoℜand d(·,·) a distance onℱ. Let𝒰⊂Zbe of full measure and constantsB,L>0such that(i)
|ξ(z)|≤B for all ξ∈ℱ and all z∈𝒰,(ii)
|Lz(ξ1)-Lz(ξ2)|≤Ld(ξ1,ξ2) for all ξ1,ξ2∈ℱ and all z∈𝒰m, where
(51)Lz(ξ)=∫Z‍ξ(z)-1m∑i=1m‍ξ(zi).
Then, for allϵ>0,
(52)Probz∈Zm{supξ∈ℱ|Lz(ξ)|≤ϵ}≥1-𝒩(ℱ,ϵ2L)×2exp(-mϵ28B2).Proof of Theorem10.
Takeγ=γz into (29). Then,
(53)∥f(ρ)-fz∥ℬ≤(2λcq×∥∫Z‍(y-f(ρ)(x))K(·,x)dρ∑i=1m‍-1m∑i=1m‍(yi-f(ρ)(xi))K(·,xi)∥ℬ*)1/(q-1).
By (7) and the reproducing property, we have
(54)∥∫Z‍(y-f(ρ)(x))K(·,x)dρ∑i=1m‍-1m∑i=1m‍(yi-f(ρ)(xi))K(·,xi)∥ℬ*=sup∥f∥ℬ≤1|〈∑i=1m‍f,∫Z‍(y-f(ρ)(x))K(·,x)dρ-1m∑i=1m‍(yi-f(ρ)(xi))K(·,xi)〉ℬ-1m∑i=1m‍(yi-f(ρ)(xi))K(·,xi)〉ℬ|=sup∥f∥ℬ≤1|∫Z‍(y-f(ρ)(x))〈f,K(·,x)〉ℬdρ∑i=1m‍-1m∑i=1m‍(yi-f(ρ)(xi))〈f,K(·,xi)〉ℬ|=sup∥f∥ℬ≤1|∫Z‍(y-f(ρ)(x))f(x)dρ∑i=1m‍-1m∑i=1m‍(yi-f(ρ)(xi))f(xi)|.
Since(55)|(y-f(ρ)(x))|≤|y|+|f(ρ)(x)||y-f(ρ)(x)|≤M+k(qDq(fρ,λ/q)λ)1/q
and (40), we have
(56)∥∫Z‍(y-f(ρ)(x))K(·,x)dρ∑i=1m‍-1m∑i=1m‍(yi-f(ρ)(xi))K(·,xi)∥ℬ*≤supf∈ℱ|∫Z‍f(z)dρ-1m∑i=1m‍f(zi)|.
Define(57)Lz(f)=∫Z‍f(z)dρ-1m∑i=1m‍f(zi).
Then,(58)|Lz(f1)-Lz(f2)|≤|∫Z‍(f1(z)-f2(z))dρ|+1m∑i=1m‍|f1(zi)-f2(zi)|≤2∥f1-f2∥C(Z).
By (52), we have for allϵ>0that
(59)Probz∈Zm{supf∈ℱ|Lz(f)|≥ϵ}≤2𝒩(ℱ,ϵ4)exp(-mϵ28γq2).
By (53), (56), and (59), we know
(60)λcq2∥f(ρ)-fz∥ℬq-1≤supf∈ℱ|∫Z‍f(z)dρ-1m∑i=1m‍f(zi)|,
which gives(61){z∈Zm:λcq2∥f(ρ)-fz∥ℬq-1≥ϵ}⊂{z∈Zm:supf∈ℱ|Lz(f)|≥ϵ}.
It follows that(62)Probz∈Zm{λcq2∥f(ρ)-fz∥ℬq-1≥ϵ}≤Probz∈Zm{supf∈ℱ|Lz(f)|≥ϵ}≤2𝒩(ℱ,ϵ4)exp(-mϵ28γq2).
That is,(63)Probz∈Zm{∥f(ρ)-fz∥ℬ≥ϵ}≤2𝒩(ℱ,λcqϵq-18)exp(-mλ2cq2ϵ2(q-1)32γq2).
We then have (49).


## 5. Learning Rates

Proof of Theorem3.
We know from [30] that for anyf∈L2(ρX)there holds
(64)∥f-fρ∥L2(ρX)2=ℰρ(f)-ℰρ(fρ).
SinceXis a compact set, we have by (40) that∥f∥L2(ρX)≤k∥f∥ℬ.Therefore,
(65)∥fz-fρ∥L2(ρX)≤∥fz-f(ρ)∥L2(ρX)+ℰρ(f(ρ))+λq∥f(ρ)∥ℬq-ℰρ(fρ)≤k∥fz-f(ρ)∥ℬ+inff∈ℬ(∥f-fρ∥L2(ρX)2+λq∥f∥ℬq)=k∥fz-f(ρ)∥ℬ+Dq(fρ,λq).
By (65) we have
(66)1k(∥fz-fρ∥L2(ρX)-Dq(fρ,λq))≤∥fz-f(ρ)∥ℬ,
which gives for anyh>0 that
(67){z∈Zm:1k(∥fz-fρ∥L2(ρX)-Dq(fρ,λq))>h}⊂{z∈Zm:∥fz-f(ρ)∥ℬ>h}.
By (49) and above inequality we have
(68)Probz∈Zm{1k(∥fz-fρ∥L2(ρX)-Dq(fρ,λq))>h}≤Probz∈Zm{∥fz-f(ρ)∥ℬ>h}≤2𝒩(ℱ,λcqhq-18)exp(-mλ2cq2h2(q-1)32γq2)
or(69)Probz∈Zm{∥fz-fρ∥L2(ρX)≤kh+Dq(fρ,λq)}≥1-2𝒩(ℱ,λcqhq-18)×exp(-mλ2cq2h2(q-1)32γq2).
Sinceℱ⊂ℬ1,we know
(70)𝒩(ℱ,λcqhq-18)≤𝒩(ℬ1,λcqhq-18).
By (69) and above inequality we have (16).To show Theorem4, we need two lemmas.Lemma 12 (see [31]).
Letc1>0,  c2>0and u>t>0.Then, the equation
(71)xu-c1xt-c2=0
has a unique positive zerox*.  In addition,
(72)x*≤max{(2c1)1/(u-t),(2c2)1/u}.Proof of Theorem4.
Since(ℬ,∥·∥ℬ)has logarithmic complexity exponents≥0, we have by (15) a constantcs>0such that
(73)log𝒩(ℬ1,λcqhq-18)≤cs(8γqλcqϵq-1)s.
Then, by (16) we have
(74)Probz∈Zm{∥fz-fρ∥L2(ρX)≤kϵ+Dq(fρ,λ)}≥1-2exp(cs(8γqλcqϵq-1)s-mλ2cq2ϵ2(q-1)32γq2).
Take(75)2exp(cs(8γqλcqϵq-1)s-mλ2cq2ϵ2(q-1)32γq2)=δ.
Then,(76)ϵ(2+s)(q-1)-32γq2log(2/δ)mλ2cq2ϵs(q-1)-32γq2csmλ2cq2×(8γqλcq)s=0.
By Lemma12, we know that the unique solutionϵ*of (75) satisfies
(77)ϵ*≤max{(64γq2log(2/δ)mλ2cq2)1/2(q-1),(64γq2csmλ2cq2×(8γqλcq)s)1/(2+s)(q-1)}ϵ*≤(64γq2log(2/δ)mλ2cq2)1/2(q-1)ϵ*≤+(82+sγq2+scsmλ2+scq2+s)1/(2+s)(q-1).By (74) and (77), we have (19).



---

*Source: 694181-2013-12-23.xml*