# Approximation Analysis of Learning Algorithms for Support Vector Regression and Quantile Regression

Authors: Dao-Hong Xiang; Ting Hu; Ding-Xuan Zhou
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We study learning algorithms generated by regularization schemes in reproducing
kernel Hilbert spaces associated with anϵ-insensitive pinball loss. This loss
function is motivated by the ϵ-insensitive loss for support vector regression and the
pinball loss for quantile regression. Approximation analysis is conducted for these
algorithms by means of a variance-expectation bound when a noise condition is
satisfied for the underlying probability measure. The rates are explicitly derived
under a priori conditions on approximation and capacity of the reproducing kernel
Hilbert space. As an application, we get approximation orders for the support
vector regression and the quantile regularized regression.


---

## Body

## 1. Introduction and Motivation

In this paper, we study a family of learning algorithms serving both purposes ofsupport vector regression and quantile regression. Approximation analysis and learning rates will be provided, which also helps better understanding of some classical learning methods.Support vector regression is a classical kernel-based algorithm in learning theory introduced in [1]. It is a regularization scheme in a reproducing kernel Hilbert space (RKHS) ℋK associated with an ϵ-insensitive lossψϵ:ℝ→ℝ+ defined for ϵ≥0 by(1.1)ψϵ(u)=max⁡{|u|-ϵ,0}={|u|-ϵ,if|u|≥ϵ,0,otherwise.
Here, for learning functions on a compact metric space X, K:X×X→ℝ is a continuous, symmetric, and positive semidefinite function called a Mercer kernel. The associated RKHS ℋK is defined [2] as the completion of the linear span of the set of function {Kx=K(x,·):x∈X} with the inner product 〈·,·〉K satisfying 〈Kx,Ky〉K=K(x,y). Let Y=ℝ and ρ be a Borel probability measure on Z:=X×Y. With a sample z={(xi,yi)}i=1m∈Zm independently drawn according to ρ, the support vector regression is defined as(1.2)fzSVR=argmin⁡f∈HK{1m∑i=1mψϵ(f(xi)-yi)+λ‖f‖K2},
where λ=λ(m)>0 is a regularization parameter.Whenϵ>0 is fixed, convergence of (1.2) was analyzed in [3]. Notice from the original motivation [1] for the insensitive parameter ϵ for balancing the approximation and sparsity of the algorithm that ϵ should change with the sample size and usually ϵ=ϵ(m)→0 as the sample size m increases. Mathematical analysis for this original algorithm is still open. We will solve this problem in a special case of our approximation analysis for general learning algorithms. In particular, we show how fzSVR approximates the median function fρ,1/2, which is one of the purposes of this paper. Here, for x∈X, the median function value fρ,1/2(x) is a median of the conditional distribution ρ(·∣x) of ρ at x.Quantile regression, compared with the least squares regression, provides richer information about response variables such as stretching or compressing tails [4]. It aims at estimating quantile regression functions. With a quantile parameter 0<τ<1, a quantile regression functionfρ,τ is defined by its value fρ,τ(x) to be a τ-quantile of ρ(·∣x), that is, a value u∈Y satisfying(1.3)ρ({y∈Y:y≤u}∣x)≥τ,ρ({y∈Y:y≥u}∣x)≥1-τ.Quantile regression has been studied by kernel-based regularization schemes in a learning theory literature (e.g., [5–8]). These regularization schemes take the form(1.4)fzQR=argmin⁡f∈HK{1m∑i=1mψτ(f(xi)-yi)+λ‖f‖K2},
where ψτ:ℝ→ℝ+ is the pinball loss shown in Figure 1 defined by(1.5)ψτ(u)={(1-τ)u,ifu>0,-τu,ifu≤0.Motivated by theϵ-insensitive loss ψϵ and the pinball loss ψτ, we propose the ϵ-insensitive pinball lossψτϵ:ℝ→ℝ+ with an insensitive parameter ϵ≥0 shown in Figure 1 defined as(1.6)ψτϵ(u)={(1-τ)(u-ϵ),ifu>ϵ,-τ(u+ϵ),ifu≤-ϵ,0,otherwise.
This loss function has been applied to online learning for quantile regression in our previous work [8]. It is applied here to a regularization scheme in the RKHS as(1.7)fz(ϵ)=fz,λ,τ(ϵ)=argmin⁡f∈HK{1m∑i=1mψτϵ(f(xi)-yi)+λ‖f‖K2}.
The main goal of this paper is to study how the output function fz(ϵ) given by (1.7) converges to the quantile regression function fρ,τ and how explicit learning rates can be obtained with suitable choices of the parameters λ=m-α,ϵ=m-β based on a priori conditions on the probability measure ρ.


## 2. Main Results on Approximation

Throughout the paper, we assume that the conditional distributionρ(·∣x) is supported on [-1,1] for every x∈X. Then, we see from (1.3) that we can take values of fρ,τ to be on [-1,1]. So to see how fz(ϵ) approximates fρ,τ, it is natural to project values of the output function fz(ϵ) onto the same interval by the projection operator introduced in [9].Definition 2.1.
The projection operatorπ on the space of function on X is defined by
(2.1)π(f)(x)={1,iff(x)>1,-1,iff(x)<-1,f(x),if-1≤f(x)≤1.Our approximation analysis aims at establishing bounds for the error∥π(fz(ϵ))-fρ,τ∥LρXp* in the space LρXp* with some p*>0 where ρX is the marginal distribution of ρ on X.


### 2.1. Support Vector Regression and Quantile Regression

Our error bounds and learning rates are presented in terms of a noise condition and approximation condition onρ.The noise condition onρ is defined in [5, 6] as follows.Definition 2.2.
Letp∈(0,∞] and q∈(1,∞). We say that ρ has a τ-quantile of p-average type q if for every x∈X, there exist a τ-quantile t*∈ℝ and constants ax∈(0,2],bx>0 such that for each u∈[0,ax],
(2.2)ρ({y∈(t*-u,t*)}∣x)≥bxuq-1,ρ({y∈(t*,t*+u)}∣x)≥bxuq-1,
and that the function on X taking value (bxaxq-1)-1 at x∈X lies in LρXp.Note that condition (2.2) tells us that fρ,τ(x)=t* is uniquely defined at every x∈X.The approximation condition onρ is stated in terms of the integral operator LK:LρX2→LρX2 defined by LK(f)(x)=∫XK(x,u)f(u)dρX(u). Since K is positive semidefinite, LK is a compact positive operator and its r-th power LKr is well-defined for any r>0. Our approximation condition is given as(2.3)fρ,τ=LKr(gρ,τ)forsome0<r≤12,gρ,τ∈LρX2.Let us illustrate our approximation analysis by the following special case which will be proved in Section5.Theorem 2.3.
LetX⊂ℝn and K∈C∞(X×X). Assume fρ,τ∈ℋK and ρ has a τ-quantile of p-average type 2 for some p∈(0,∞]. Take λ=m-(p+1)/(p+2) and ϵ=m-β with (p+1)/(p+2)≤β≤∞. Let 0<η<(p+1)/2(p+2). Then, with p*=2p/(p+1)>0, for any 0<δ<1, with confidence 1-δ, one has
(2.4)‖π(fz(ϵ))-fρ,τ‖LρXp*≤C̃log⁡3δmη-(p+1)/2(p+2),
where C̃ is a constant independent of m or δ.Ifp≥(1/2η)-2 for 0<η<1/4, we see that the power exponent for the learning rate (2.4) is at least (1/2)-2η. This exponent can be arbitrarily close to 1/2 when η is small enough.In particular, if we takeτ=1/2, Theorem 2.3 provides rates for output function fzSVR of the support vector regression (1.2) to approximate the median function fρ,1/2.If we takeβ=∞ leading to ϵ=0, Theorem 2.3 provides rates for output function fzQR of the quantile regression algorithm (1.4) to approximate the quantile regression function fρ,τ.


### 2.2. General Approximation Analysis

To state our approximation analysis in the general case, we need the capacity of the hypothesis space measured by covering numbers.Definition 2.4.
For a subsetS of C(X) and u>0, the covering number𝒩(S,u) is the minimal integer l∈ℕ such that there exist l disks with radius u covering S.The covering numbers of ballsBR={f∈ℋK:∥f∥K≤R} with radius R>0 of the RKHS have been well studied in the learning theory literature [10, 11]. In this paper, we assume for some s>0 and Cs>0 that(2.5)log⁡N(B1,u)≤Cs(1u)s,∀u>0.Now we can state our main result which will be proved in Section5. For p∈(0,∞] and q∈(1,∞), we denote(2.6)θ=min⁡{2q,pp+1}∈(0,1].Theorem 2.5.
Assume (2.3) with 0<r≤1/2 and (2.5) with s>0. Suppose that ρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞). Take λ=m-α with 0<α≤1 and α<(2+s)/s(2+s-θ). Set ϵ=m-β with αr/(1-r)≤β≤∞. Let
(2.7)0<η<(1+s)[2+2s-sα(2+s-θ)]s(2+s-θ)(2+s).
Then, with p*=pq/(p+1)>0, for any 0<δ<1, with confidence 1-δ, one has
(2.8)‖π(fz(ϵ))-fρ,τ‖LρXp*≤C̃(log⁡3η)2log⁡3δm-ϑ,
where C̃ is a constant independent of m or δ and the power index ϑ is given in terms of r,s,p,q,α, and η by
(2.9)ϑ=1qmin⁡{αr1-r,12+s-θ-s[α(2+s-θ)-1](2+s-θ)(2+s)-sη1+s,12+s-θ-sα(1-2r)(1+s)(2-2r),12+s-θ-s1+s(α2-12(2-θ))}.The indexϑ can be viewed as a function of variables r,s,p,q,α,η. The restriction 0<α<(2+s)/s(2+s-θ) on α and (2.7) on η ensure that ϑ is positive, which verifies the valid learning rate in Theorem 2.5.Assumption (2.5) is a measurement of regularity of the kernel K when X is a subset of ℝn. In particular, s can be arbitrarily small when K is smooth enough. In this case, the power index ϑ in (2.8) can be arbitrarily close to (1/q)min{αr/(1-r),1/(2-θ)}. Again, when β=∞, ϵ=0, algorithm (1.7) corresponds to algorithm (1.4) for quantile regression. In this case, Theorem 2.5 provides learning rates for quantile regression algorithm (1.4).Error analysis has been done for quantile regression algorithm (1.4) in [5, 6]. Under the assumptions that ρ satisfies (2.2) with some p∈(0,∞] and q>1 and the ℓ2-empirical covering number 𝒩z(B1,η,ℓ2) (see [5] for more details) of B1 is bounded as(2.10)sup⁡z∈Zmlog⁡Nz(B1,η,l2)≤a(1η)swiths∈(0,2),a≥1,
it was proved in [5] that with confidence 1-δ,(2.11)‖π(fzQR)-fρ,τ‖LρXp*≤{Dτ(λ)+Dτ(λ)λlog⁡(3/δ)m+(Ks,Cpaλs/2m)(p+1)/(p+2-s/2)+Ks,Cpaλs/2m+5(32Cplog⁡(3/δ)m)(p+1)/(p+2)+145log⁡(3/δ)m(Ks,Cpaλs2m)(p+1)/(p+2-s/2)}1/q,
where Cp and Ks,Cp are constants independent of m or λ. Here, 𝒟τ(λ) is the regularization error defined as(2.12)Dτ(λ)=inf⁡f∈HK{Eτ(f)-Eτ(fρ,τ)+λ‖f‖K2},
and ℰτ(f) is the generalization error associated with the pinball loss ψτ defined by(2.13)Eτ(f)=∫Zψτ(f(x)-y)dρ=∫X∫Yψτ(f(x)-y)dρ(y∣x)dρX(x).
Note that ℰτ(f) is minimized by the quantile regression function fρ,τ. Thus, when the regularization error 𝒟τ(λ) decays polynomially as 𝒟τ(λ)=O(λr/(1-r)) (which is ensured by Lemma 2.6 below when (2.3) is satisfied) and λ=m-α, then ∥π(fzQR)-fρ,τ∥LρXp*=O(log(3/δ)m-ϑ) with(2.14)ϑ=1qmin⁡{αr1-r,p+1p+2-(s/2)(1-αs2),p+1p+2}.
Since (p+1)/(p+2)=1/(2-θ), we see that this learning rate is comparable to our result in (2.8).


### 2.3. Comparison with Least Squares Regression

There has been a large literature in learning theory (described in [12]) for the least squares algorithms:(2.15)fzLS=argmin⁡f∈HK{1m∑i=1m(f(xi)-yi)2+λ‖f‖K2}.
It aims at learning the regression function fρ(x)=∫Yydρ(y∣x). A crucial property for its error analysis is the identity ℰls(f)-ℰls(fρ)=∥f-fρ∥LρX22 for the least squares generalization error ℰls(f)=∫Z(y-f(x))2dρ. It yields a variance-expectation bound E(ξ2)≤4E(ξ) for the random variable ξ=(y-f(x))2-(y-fρ(x))2 on (Z,ρ) where f:X→Y is an arbitrary measurable function. Such a variance-expectation bound with E(ξ) possibly replaced by its positive power (E(ξ))θ plays an essential role for analyzing regularization schemes and the power exponent θ depends on strong convexity of the loss. See [13] and references therein. However, the pinball loss in the quantile regression setting has no strong convexity [6] and we would not expect a variance-expectation bound for a general distribution ρ. When ρ has a τ-quantile of p-average type q, the following variance-expectation bound with θ given by (2.6) can be found in [5, 7] (derived by means of Lemma 3.1 below).Lemma 2.6.
Ifρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞), then
(2.16)E{(ψτ(f(x)-y)-ψτ(fρ,τ(x)-y))2}≤Cθ(Eτ(f)-Eτ(fρ,τ))θ,∀f:X⟶Y,
where the power index θ is given by (2.6) and the constant Cθ is Cθ=22-θqθ∥γ-1∥LρXpθ.Lemma2.6 overcomes the difficulty of quantile regression caused by lack of strong convexity of the pinball loss. It enables us to derive satisfactory learning rates, as in Theorem 2.5.


## 2.1. Support Vector Regression and Quantile Regression

Our error bounds and learning rates are presented in terms of a noise condition and approximation condition onρ.The noise condition onρ is defined in [5, 6] as follows.Definition 2.2.
Letp∈(0,∞] and q∈(1,∞). We say that ρ has a τ-quantile of p-average type q if for every x∈X, there exist a τ-quantile t*∈ℝ and constants ax∈(0,2],bx>0 such that for each u∈[0,ax],
(2.2)ρ({y∈(t*-u,t*)}∣x)≥bxuq-1,ρ({y∈(t*,t*+u)}∣x)≥bxuq-1,
and that the function on X taking value (bxaxq-1)-1 at x∈X lies in LρXp.Note that condition (2.2) tells us that fρ,τ(x)=t* is uniquely defined at every x∈X.The approximation condition onρ is stated in terms of the integral operator LK:LρX2→LρX2 defined by LK(f)(x)=∫XK(x,u)f(u)dρX(u). Since K is positive semidefinite, LK is a compact positive operator and its r-th power LKr is well-defined for any r>0. Our approximation condition is given as(2.3)fρ,τ=LKr(gρ,τ)forsome0<r≤12,gρ,τ∈LρX2.Let us illustrate our approximation analysis by the following special case which will be proved in Section5.Theorem 2.3.
LetX⊂ℝn and K∈C∞(X×X). Assume fρ,τ∈ℋK and ρ has a τ-quantile of p-average type 2 for some p∈(0,∞]. Take λ=m-(p+1)/(p+2) and ϵ=m-β with (p+1)/(p+2)≤β≤∞. Let 0<η<(p+1)/2(p+2). Then, with p*=2p/(p+1)>0, for any 0<δ<1, with confidence 1-δ, one has
(2.4)‖π(fz(ϵ))-fρ,τ‖LρXp*≤C̃log⁡3δmη-(p+1)/2(p+2),
where C̃ is a constant independent of m or δ.Ifp≥(1/2η)-2 for 0<η<1/4, we see that the power exponent for the learning rate (2.4) is at least (1/2)-2η. This exponent can be arbitrarily close to 1/2 when η is small enough.In particular, if we takeτ=1/2, Theorem 2.3 provides rates for output function fzSVR of the support vector regression (1.2) to approximate the median function fρ,1/2.If we takeβ=∞ leading to ϵ=0, Theorem 2.3 provides rates for output function fzQR of the quantile regression algorithm (1.4) to approximate the quantile regression function fρ,τ.


## 2.2. General Approximation Analysis

To state our approximation analysis in the general case, we need the capacity of the hypothesis space measured by covering numbers.Definition 2.4.
For a subsetS of C(X) and u>0, the covering number𝒩(S,u) is the minimal integer l∈ℕ such that there exist l disks with radius u covering S.The covering numbers of ballsBR={f∈ℋK:∥f∥K≤R} with radius R>0 of the RKHS have been well studied in the learning theory literature [10, 11]. In this paper, we assume for some s>0 and Cs>0 that(2.5)log⁡N(B1,u)≤Cs(1u)s,∀u>0.Now we can state our main result which will be proved in Section5. For p∈(0,∞] and q∈(1,∞), we denote(2.6)θ=min⁡{2q,pp+1}∈(0,1].Theorem 2.5.
Assume (2.3) with 0<r≤1/2 and (2.5) with s>0. Suppose that ρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞). Take λ=m-α with 0<α≤1 and α<(2+s)/s(2+s-θ). Set ϵ=m-β with αr/(1-r)≤β≤∞. Let
(2.7)0<η<(1+s)[2+2s-sα(2+s-θ)]s(2+s-θ)(2+s).
Then, with p*=pq/(p+1)>0, for any 0<δ<1, with confidence 1-δ, one has
(2.8)‖π(fz(ϵ))-fρ,τ‖LρXp*≤C̃(log⁡3η)2log⁡3δm-ϑ,
where C̃ is a constant independent of m or δ and the power index ϑ is given in terms of r,s,p,q,α, and η by
(2.9)ϑ=1qmin⁡{αr1-r,12+s-θ-s[α(2+s-θ)-1](2+s-θ)(2+s)-sη1+s,12+s-θ-sα(1-2r)(1+s)(2-2r),12+s-θ-s1+s(α2-12(2-θ))}.The indexϑ can be viewed as a function of variables r,s,p,q,α,η. The restriction 0<α<(2+s)/s(2+s-θ) on α and (2.7) on η ensure that ϑ is positive, which verifies the valid learning rate in Theorem 2.5.Assumption (2.5) is a measurement of regularity of the kernel K when X is a subset of ℝn. In particular, s can be arbitrarily small when K is smooth enough. In this case, the power index ϑ in (2.8) can be arbitrarily close to (1/q)min{αr/(1-r),1/(2-θ)}. Again, when β=∞, ϵ=0, algorithm (1.7) corresponds to algorithm (1.4) for quantile regression. In this case, Theorem 2.5 provides learning rates for quantile regression algorithm (1.4).Error analysis has been done for quantile regression algorithm (1.4) in [5, 6]. Under the assumptions that ρ satisfies (2.2) with some p∈(0,∞] and q>1 and the ℓ2-empirical covering number 𝒩z(B1,η,ℓ2) (see [5] for more details) of B1 is bounded as(2.10)sup⁡z∈Zmlog⁡Nz(B1,η,l2)≤a(1η)swiths∈(0,2),a≥1,
it was proved in [5] that with confidence 1-δ,(2.11)‖π(fzQR)-fρ,τ‖LρXp*≤{Dτ(λ)+Dτ(λ)λlog⁡(3/δ)m+(Ks,Cpaλs/2m)(p+1)/(p+2-s/2)+Ks,Cpaλs/2m+5(32Cplog⁡(3/δ)m)(p+1)/(p+2)+145log⁡(3/δ)m(Ks,Cpaλs2m)(p+1)/(p+2-s/2)}1/q,
where Cp and Ks,Cp are constants independent of m or λ. Here, 𝒟τ(λ) is the regularization error defined as(2.12)Dτ(λ)=inf⁡f∈HK{Eτ(f)-Eτ(fρ,τ)+λ‖f‖K2},
and ℰτ(f) is the generalization error associated with the pinball loss ψτ defined by(2.13)Eτ(f)=∫Zψτ(f(x)-y)dρ=∫X∫Yψτ(f(x)-y)dρ(y∣x)dρX(x).
Note that ℰτ(f) is minimized by the quantile regression function fρ,τ. Thus, when the regularization error 𝒟τ(λ) decays polynomially as 𝒟τ(λ)=O(λr/(1-r)) (which is ensured by Lemma 2.6 below when (2.3) is satisfied) and λ=m-α, then ∥π(fzQR)-fρ,τ∥LρXp*=O(log(3/δ)m-ϑ) with(2.14)ϑ=1qmin⁡{αr1-r,p+1p+2-(s/2)(1-αs2),p+1p+2}.
Since (p+1)/(p+2)=1/(2-θ), we see that this learning rate is comparable to our result in (2.8).


## 2.3. Comparison with Least Squares Regression

There has been a large literature in learning theory (described in [12]) for the least squares algorithms:(2.15)fzLS=argmin⁡f∈HK{1m∑i=1m(f(xi)-yi)2+λ‖f‖K2}.
It aims at learning the regression function fρ(x)=∫Yydρ(y∣x). A crucial property for its error analysis is the identity ℰls(f)-ℰls(fρ)=∥f-fρ∥LρX22 for the least squares generalization error ℰls(f)=∫Z(y-f(x))2dρ. It yields a variance-expectation bound E(ξ2)≤4E(ξ) for the random variable ξ=(y-f(x))2-(y-fρ(x))2 on (Z,ρ) where f:X→Y is an arbitrary measurable function. Such a variance-expectation bound with E(ξ) possibly replaced by its positive power (E(ξ))θ plays an essential role for analyzing regularization schemes and the power exponent θ depends on strong convexity of the loss. See [13] and references therein. However, the pinball loss in the quantile regression setting has no strong convexity [6] and we would not expect a variance-expectation bound for a general distribution ρ. When ρ has a τ-quantile of p-average type q, the following variance-expectation bound with θ given by (2.6) can be found in [5, 7] (derived by means of Lemma 3.1 below).Lemma 2.6.
Ifρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞), then
(2.16)E{(ψτ(f(x)-y)-ψτ(fρ,τ(x)-y))2}≤Cθ(Eτ(f)-Eτ(fρ,τ))θ,∀f:X⟶Y,
where the power index θ is given by (2.6) and the constant Cθ is Cθ=22-θqθ∥γ-1∥LρXpθ.Lemma2.6 overcomes the difficulty of quantile regression caused by lack of strong convexity of the pinball loss. It enables us to derive satisfactory learning rates, as in Theorem 2.5.


## 3. Insensitive Relation and Error Decomposition

An important relation for quantile regression observed in [5] assets that the error ∥π(fz(ϵ))-fρ,τ∥ taken in a suitable LρXp* space can be bounded by the excess generalization error ℰτ(π(fz(ϵ)))-ℰτ(fρ,τ) when the noise condition is satisfied.Lemma 3.1.
Letp∈(0,∞] and q∈(1,∞). Denote p*=pq/(p+1)>0. If ρ has a τ-quantile of p-average type q, then for any measurable function f on X, one has
(3.1)‖f-fρ,τ‖LρXp*≤Cq,ρ{Eτ(f)-Eτ(fρ,τ)}1/q,
where Cq,ρ=21-(1/q)q1/q∥{(bxaxq-1)-1}x∈X∥LρXp1/q.By Lemma3.1, to estimate ∥π(fz(ϵ))-fρ,τ∥LρXp*, we only need to bound the excess generalization error ℰτ(π(fz(ϵ)))-ℰτ(fρ,τ). This will be done by conducting an error decomposition which has been developed in the literature for regularization schemes [9, 13–15]. Technical difficulty arises for our problem here because the insensitive parameter ϵ changes with m. This can be overcome [16] by the following insensitive relation(3.2)ψτ(u)-ϵ≤ψτϵ(u)≤ψτ(u),u∈R.Now, we can conduct an error decomposition. Define the empirical errorℰz,τ(f) for f:X→ℝ as(3.3)Ez,τ(f)=1m∑i=1mψτ(f(xi)-yi).Lemma 3.2.
Letλ>0, fz(ϵ) be defined by (1.7) and
(3.4)fλ(0)=argmin⁡f∈HK{Eτ(f)-Eτ(fρ,τ)+λ‖f‖K2}.
Then,
(3.5)Eτ(π(fz(ϵ)))-Eτ(fρ,τ)+λ‖fz(ϵ)‖K2≤S1+S2+ϵ+Dτ(λ),
where
(3.6)S1=[Eτ(π(fz(ϵ)))-Eτ(fρ,τ)]-[Ez,τ(π(fz(ϵ)))-Ez,τ(fρ,τ)],S2=[Ez,τ(fλ(0))-Ez,τ(fρ,τ)]-[Eτ(fλ(0))-Eτ(fρ,τ)],Proof.
The regularized excess generalization errorℰτ(π(fz(ϵ)))-ℰτ(fρ,τ)+λ∥fz(ϵ)∥K2 can be expressed as
(3.7){Eτ(π(fz(ϵ)))-Ez,τ(π(fz(ϵ)))}+{[Ez,τ(π(fz(ϵ)))+λ‖fz(ϵ)‖K2]-[Ez,τ(fλ(0))+λ‖fλ(0)‖K2]}+{[Ez,τ(fλ(0))-Eτ(fλ(0))]}+{Eτ(fλ(0))-Eτ(fρ,τ)+λ‖fλ(0)‖K2}.
The fact |y|≤1 implies that ℰz,τ(π(fz(ϵ)))≤ℰz,τ(fz(ϵ)). The insensitive relation (3.2) and the definition of fz(ϵ) tell us that
(3.8)Ez,τ(fz(ϵ))+λ‖fz(ϵ)‖K2≤1m∑i=1mψτϵ(fz(ϵ)(xi)-yi)+λ‖fz(ϵ)‖K2+ϵ≤1m∑i=1mψτϵ(fλ(0)(xi)-yi)+λ‖fλ(0)‖K2+ϵ≤Ez,τ(fλ(0))+λ‖fλ(0)‖K2+ϵ.
Then, by subtracting and adding ℰτ(fρ,τ) and ℰz,τ(fρ,τ) and noting 𝒟τ(λ)=ℰτ(fλ(0))-ℰτ(fρ,τ)+λ∥fλ(0)∥K2, we see that the desired inequality in Lemma 3.2 holds true.In the error decomposition (3.5), the first two terms are called sample error. The last term is the regularization error defined in (2.12). It can be estimated as follows.Proposition 3.3.
Assume (2.3). Define fλ(0) by (3.4). Then, one has
(3.9)Dτ(λ)≤C0λr/(1-r),‖fλ(0)‖K≤C0λ(2r-1)/(2-2r),
where C0 is the constant C0=∥gρ,τ∥LρX2+∥gρ,τ∥LρX22.Proof.
Letμ=λ1/(1-r)>0 and
(3.10)fμ=(LK+μI)-1LKfρ,τ.
It can be found in [17, 18] that when (2.3) holds, we have
(3.11)‖fμ-fρ,τ‖LρX22+μ‖fμ‖K2≤μ2r‖gρ,τ‖LρX22.
Hence, ∥fμ-fρ,τ∥LρX2≤μr∥gρ,τ∥LρX2 and ∥fμ∥K2≤μ2r-1∥gρ,τ∥LρX22. Since ψτ is Lipschitz, we know by taking f=fμ in (2.12) that
(3.12)Dτ(λ)≤∫Zψτ(fμ(x)-y)-ψτ(fρ,τ(x)-y)+λ‖fμ‖K2≤‖fμ-fρ,τ‖LρX1+λ‖fμ‖K2≤‖fμ-fρ,τ‖LρX2+λ‖fμ‖K2≤μr‖gρ,τ‖LρX2+λμ2r-1‖gρ,τ‖LρX22=(‖gρ,τ‖LρX2+‖gρ,τ‖LρX22)λr/(1-r).
This verifies the desired bound for 𝒟τ(λ). By taking f=0 in (2.12), we have
(3.13)λ‖fλ(0)‖K2≤Dτ(λ)≤C0λr/(1-r).
Then the bound for ∥fλ(0)∥K is proved.


## 4. Estimating Sample Error

This section is devoted to estimating the sample error. This is conducted by using the variance-expectation bound in Lemma2.6.Denoteκ=supx∈XK(x,x). For R≥1, denote(4.1)W(R)={z∈Zm:‖fz(ϵ)‖K≤R}.Proposition 4.1.
Assume (2.3) and (2.5). Let R≥1 and 0<δ<1. If ρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞), then there exists a subset VR of Zm with measure at most δ such that for any z∈𝒲(R)∖VR,
(4.2)Eτ(π(fz(ϵ)))-Eτ(fρ,τ)+λ‖fz(ϵ)‖K2≤2ϵ+C1′log⁡3δλr/(1-r)max⁡{1,λ-(1/(2-2r))m}+C2′log⁡3δm-1/(2-θ)+C3′m-1/(2+s-θ)Rs/(1+s),
where θ is given by (2.6) and C1′,C2′,C3′ are constants given by
(4.3)C1′=4C0+2κC0,C2′=245+324Cθ1/(2-θ),C3′=40(6Cs)1/(1+s)+40(8CθCs)1/(2+s-θ).Proof.
Let us first estimate the second part𝒮2 of the sample error. It can be decomposed into two parts 𝒮2=𝒮2,1+𝒮2,2 where
(4.4)S2,1=[Ez,τ(fλ(0))-Ez,τ(π(fλ(0)))]-[Eτ(fλ(0))-Eτ(π(fλ(0)))],S2,2=[Ez,τ(π(fλ(0)))-Ez,τ(fρ,τ)]-[Eτ(π(fλ(0)))-Eτ(fρ,τ)].
For bounding𝒮2,1, we take the random variable ξ(z)=ψτ(fλ(0)(x)-y)-ψτ(π(fλ(0))(x)-y) on (Z,ρ). It satisfies 0≤ξ≤|π(fλ(0))(x)-fλ(0)(x)|≤1+∥fλ(0)∥∞. Hence, |ξ-E(ξ)|≤1+∥fλ(0)∥∞ and E(ξ-E(ξ))2≤Eξ2≤(1+∥fλ(0)∥∞)E(ξ). Applying the one-side Bernstein inequality [12], we know that there exists a subset Z1,δ of Zm with measure at least 1-(δ/3) such that
(4.5)S2,1≤7(1+‖fλ(0)‖∞)log⁡(3/δ)6m+Eτ(fλ(0))-Eτ(π(fλ(0))),∀z∈Z1,δ.
For𝒮2,2, we apply the one-side Bernstein inequality again to the random variable ξ(z)=ψτ(π(fλ(0))(x)-y)-ψτ(fρ,τ(x)-y), bound the variance by Lemma 2.6 with f=π(fλ(0)), and find that there exists another subset Z2,δ of Zm with measure at least 1-(δ/3) such that
(4.6)S2,2≤4log⁡(3/δ)3m+(θ2)θ/(4-2θ)(1-θ2)(2Cθlog⁡(3/δ)m)1/(2-θ)+Eτ(π(fλ(0)))-Eτ(fρ,τ),∀z∈Z2,δ.
Next, we estimate the first part𝒮1 of the sample error. Consider the function set
(4.7)G={ψτ(π(f)(x)-y)-ψτ(fρ,τ(x)-y):‖f‖K≤R}.
A function from this set g(z)=ψτ(π(f)(x)-y)-ψτ(fρ,τ(x)-y) satisfies E(g)≥0, |g(z)|≤2, and E(g2)≤Cθ(E(g))θ by (2.16). Also, the Lipschitz property of the pinball loss yields 𝒩(𝒢,u)≤𝒩(B1,u/R). Then, we apply a standard covering number argument with a ratio inequality [12, 13, 19, 20] to 𝒢 and find from the covering number condition (2.5) that
(4.8)Probz∈Zm{sup⁡‖f‖K≤R[Eτ(π(f))-Eτ(fρ,τ)]-[Ez,τ(π(f))-Ez,τ(fρ,τ)](Eτ(π(f))-Eτ(fρ,τ))θ+uθ≤4u1-(θ/2)}≥1-N(B1,uR)exp⁡{-mu2-θ2Cθ+(4/3)u1-θ}≥1-exp⁡{Cs(Ru)s-mu2-θ2Cθ+(4/3)u1-θ}.
Setting the confidence to be 1-(δ/3), we take u*(R,m,δ/3) to be the positive solution to the equation
(4.9)Cs(Ru)s-mu2-θ2Cθ+(4/3)u1-θ=log⁡δ3.
Then, there exists a third subset Z3,δ of Zm with measure at least 1-(δ/3) such that
(4.10)sup⁡‖f‖K≤R[Eτ(π(f))-Eτ(fρ,τ)]-[Ez,τ(π(f))-Ez,τ(fρ,τ)](Eτ(π(f))-Eτ(fρ,τ))θ+(u*(R,m,δ/3))θ≤4(u*(R,m,δ3))1-(θ/2),∀z∈Z3,δ.
Thus, for z∈𝒲(R)∩Z3,δ, we have
(4.11)S1=[Eτ(π(fz(ϵ)))-Eτ(fρ,τ)]-[Ez,τ(π(fz(ϵ)))-Ez,τ(fρ,τ)]≤4[u*(R,m,δ3)]1-(θ/2)[Eτ(π(fz(ϵ)))-Eτ(fρ,τ)]θ+[u*(R,m,δ3)]θ≤(1-θ2)42/(2-θ)u*(R,m,δ3)+θ2[Eτ(π(fz(ϵ)))-Eτ(fρ,τ)]+4u*(R,m,δ3).
Here, we have used the elementary inequality a+b≤a+b and Young’s inequality. Putting this bound and (4.5), (4.6) into (3.5), we know that for z∈𝒲(R)∩Z3,δ∩Z1,δ∩Z2,δ, there holds
(4.12)Eτ(π(fz))-Eτ(fρ,τ)+λ‖fz(ϵ)‖K2≤12[Eτ(π(fz(ϵ)))-Eτ(fρ,τ)]+ϵ+2Dτ(λ)+20u*(R,m,δ3)+7(1+‖fλ(0)‖∞)log⁡(3/δ)6m+4log⁡(3/δ)3m+(2Cθlog⁡(3/δ)m)1/(2-θ),
which together with Proposition 3.3 implies
(4.13)Eτ(π(fz))-Eτ(fρ,τ)+λ‖fz(ϵ)‖K2≤2ϵ+4C0λr/(1-r)+(5+2(2Cθ)1/(2-θ))log⁡3δm-1/(2-θ)+40u*(R,m,δ3)+2κC0log⁡3δλ(2r-1)/(2-2r)m.
Here, we have used the reproducing property in ℋK which yields [12]
(4.14)‖f‖∞≤κ‖f‖K,∀f∈HK.
Equation (4.9) can be expressed as
(4.15)u2+s-θ-43mlog⁡3δu1+s-θ-2Cθmlog⁡3δus-4CsRs3mu1-θ-2CθCsRsm=0.
By Lemma  7.2 in [12], the positive solution u*(R,m,δ/3) to this equation can be bounded as
(4.16)u*(R,m,δ/3)≤max⁡{6mlog⁡3δ,(8Cθmlog⁡3δ)1/(2-θ),(6CsRsm)1/(1+s),(8CθCsRsm)1/(2+s-θ)}≤(6+(8Cθ)1/(2-θ))log⁡3δm-1/(2-θ)+((6Cs)1/(1+s)+(8CθCs)1/(2+s-θ))×m-1/(2+s-θ)Rs/(1+s).
Thus, for z∈𝒲(R)∩Z3,δ∩Z1,δ∩Z2,δ, the desired bound (4.2) holds true. Since the measure of the set Z3,δ∩Z1,δ∩Z2,δ is at least 1-δ, our conclusion is proved.


## 5. Deriving Convergence Rates by Iteration

To apply Proposition4.1 for error analysis, we need some R≥1 for z∈𝒲(R). One may choose R=λ-1/2 according to(5.1)‖fz(ϵ)‖K≤λ-1/2,∀z∈Zm
which is seen by taking f=0 in (1.7). This choice is too rough. Recall from Proposition 3.3 that ∥fλ(0)∥K≤C0λ(2r-1)/(2-2r) which is a bound for the noise-free limit fλ(0) of fz(ϵ). It is much better than λ-1/2. This motivates us to try similar tight bounds for fz(ϵ). This target will be achieved in this section by applying Proposition 4.1 iteratively. The iteration technique has been used in [13, 21] to improve learning rates.Lemma 5.1.
Assume (2.3) with 0<r≤1/2 and (2.5) with s>0. Take λ=m-α with 0<α≤1 and ϵ=m-β with 0<β≤∞. Let 0<η<1. If ρ has a τ-quantile of p-average type q for some p∈(0,∞] and q∈(1,∞), then for any 0<δ<1, with confidence 1-δ, there holds
(5.2)‖fz(ϵ)‖K≤4C3′(1+2+C1′+C2′)(log⁡3η)2log⁡3δmθη,
where θη is given by
(5.3)θη=max⁡{α-β2,α(1-2r)2-2r,α2-12(2-θ),[α(2+s-θ)-1](1+s)(2+s-θ)(2+s)+η}≥0.Proof.
Puttingλ=m-α with 0<α≤1 and ϵ=m-β with 0<β≤∞ into Proposition 4.1, we know that for any R≥1 there exists a subset VR of Zm with measure at most δ such that
(5.4)‖fz(ϵ)‖K≤amRs/(2+2s)+bm,∀z∈W(R)∖VR,
where with ζ:=max{(α-β)/2,α(1-2r)/(2-2r),α/2-1/2(2-θ)}≥0, the constants are given by
(5.5)am=C3′m(α/2)-(1/2(2+s-θ)),bm=(2+C1′log⁡3δ+C2′log⁡3δ)mζ.
It follows that
(5.6)W(R)⊆W(amRs/(2+2s)+bm)∪VR.
Let us apply (5.6) iteratively to a sequence {R(j)}j=0J defined by R(0)=λ-1/2 and R(j)=am(R(j-1))s/(2+2s)+bm where J∈ℕ will be determined later. Then, 𝒲(R(j-1))⊆𝒲(R(j))∪VR(j-1). By (5.1), 𝒲(R(0))=Zm. So we have
(5.7)Zm=W(R(0))⊆W(R(1))∪VR(0)⊆⋯⊆W(R(J))∪(∪j=0J-1VR(j)).
As the measure of VR(j) is at most δ, we know that the measure of ∪j=0J-1VR(j) is at most Jδ. Hence, 𝒲(R(J)) has measure at least 1-Jδ.
DenoteΔ=s/(2+2s)<1/2. The definition of the sequence {R(j)}j=0J tells us that
(5.8)R(J)=am1+Δ+Δ2+⋯+ΔJ-1(R(0))ΔJ+∑j=1J-1am1+Δ+Δ2+⋯+Δj-1bmΔj+bm.
Let us bound the two terms on the right-hand side.
The first term equals(5.9)(C3′)(1-ΔJ)/2(1-Δ)m((α(2+s-θ)-1)/(4+2s-2θ))((1-ΔJ)/(1-Δ))m(α/2)ΔJ,
which is bounded by
(5.10)C3′m(α(2+s-θ)-1)/(4+2s-2θ)(1-Δ)m((α/2)-(α(2+s-θ)-1)/(4+2s-2θ)(1-Δ))ΔJ≤C3′m[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)m(1/(2+s-θ))2-J.
Take J to be the smallest integer greater than or equal to log(1/η)/log2. The above expression can be bounded by C3′m[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)+η.
The second terms equals(5.11)∑j=1J-1am1+Δ+Δ2+⋯+Δj-1bmΔj+bm≤∑j=1J-1C3′m((α/2)-1/2(2+s-θ))((1-Δj)/(1-Δ))b1ΔjmζΔj+b1mζ,
where b1∶=2+C1′log(3/δ)+C2′log(3/δ). It is bounded by
(5.12)m[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)C3′b1∑j=0J-1m(ζ-([α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)))(sj/(2+2s)j).
When ζ≤[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s), the above expression is bounded by C3′b1Jm[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s). When ζ≥[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s), it is bounded by C3′b1Jmζ.
Based on the above discussion, we obtain(5.13)R(J)≤(C3′+C3′b1J)mθη,
where θη=max{[α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)+η,ζ}. So with confidence 1-Jδ, there holds
(5.14)‖fz(ϵ)‖K≤R(J)≤C3′(1+2+C1′+C2′)Jlog⁡3δmθη.
Then, our conclusion follows by replacing δ by δ/J and noting J≤2log(3/η).Now, we can prove our main result, Theorem2.5.Proof of Theorem2.5.
TakeR to be the right side of (5.2). By Lemma 5.1, there exists a subset VR′ of Zm with measure at most δ such that Zm∖VR′⊆𝒲(R). Applying Proposition 4.1 to this R, we know that there exists another subset VR of Zm with measure at most δ such that for any z∈𝒲(R)∖VR,
(5.15)Eτ(π(fz(ϵ)))-Eτ(fρ,τ)≤2m-β+C1′log⁡3δm-αr/(1-r)+C2′log⁡3δm-1/(2-θ)+C4′(log⁡3η)2log⁡3δm(s/(1+s))θη-(1/(2+s-θ)),
where
(5.16)C4′=C3′(4C3′)s/(1+s)(1+2+C1′+C2′).
Since the set VR∪VR′ has measure at most 2δ, after scaling 2δ to δ and setting the constant C̃ by
(5.17)C̃=2Cq,ρ(2+C1′+C2′+C4′),
we see that the above estimate together with Lemma 3.1 gives the error bound
(5.18)‖π(fz(ϵ))-fρ,τ‖LρXp*≤C̃(log⁡3η)2log⁡3δm-ϑ
with confidence 1-δ and the power index ϑ give by
(5.19)ϑ=1qmin⁡{β,αr1-r,12+s-θ-s1+sθη},
provided that
(5.20)θη<1+ss(2+s-θ).
Since β≥αr/(1-r), we know that (α-β)/2≤α(1-2r)/(2-2r). By the restriction 0<α<(2+s)/s(2+s-θ) on α, we find α(1-2r)/(2-2r)<(1+s)/s(2+s-θ) and (α/2)-(1/2(2-θ))<(1+s)/s(2+s-θ). Moreover, restriction (2.7) on η tell us that [α(2+s-θ)-1](1+s)/(2+s-θ)(2+s)+η<(1+s)/s(2+s-θ). Therefore, condition (5.20) is satisfied. The restriction β≥αr/(1-r) and the above expression for ϑ tells us that the power index for the error bound can be exactly expressed by formula (2.9). The proof of Theorem 2.5 is complete.Finally, we prove Theorem2.3.Proof of Theorem2.3.
Sincefρ,τ∈ℋK, we know that (2.3) holds with r=1/2. The noise condition on ρ is satisfied with q=2 and p∈(0,∞]. Then, θ=p/(p+1)∈(0,1]. Since X⊂ℝn and K∈C∞(X×X), we know from [11] that (2.5) holds true for any s>0. With 0<η<((p+1)/2(p+2)), let us choose s to be a positive number satisfying the following four inequalities:
(5.21)p+1p+2<2+ss(2+s-θ),13<(1+s)[2+2s-(s(2+s-θ)(p+1))/(p+2)]s(2+s-θ)(2+s),p+1p+2-2η≤12+s-θ-s[(2+s-θ)(p+1)/(p+2-1)](2+s-θ)(2+s)-s3(1+s),p+1p+2-2η≤12+s-θ.
The first inequality above tells us that the restrictions on α,β are satisfied by choosing α=(p+1)/(p+2)=1/(2-θ) and (p+1)/(p+2)≤β≤∞. The second inequality shows that condition (2.7) for the parameter η renamed now as η* is also satisfied by taking η*=1/3. Thus, we apply Theorem 2.5 and know that with confidence 1-δ, (2.8) holds with the power index ϑ given by (2.9); but r=1/2,α=1/(2-θ), and η*=1/3 imply that
(5.22)ϑ=12min⁡{α,12+s-θ,12+s-θ-s[α(2+s-θ)-1](2+s-θ)(2+s)-s3(1+s)}.
The last two inequalities satisfied by s yield ϑ≥(α/2)-η. So (2.8) verifies (2.4). This completes the proof of the theorem.



---

*Source: 902139-2012-02-08.xml*