# ERM Scheme for Quantile Regression

Authors: Dao-Hong Xiang
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

This paper considers the ERM scheme for quantile regression. We conduct error analysis for this learning algorithm by means of a variance-expectation bound when a noise condition is satisfied for the underlying probability measure. The learning rates are derived by applying concentration techniques involving theℓ2-empirical covering numbers.


---

## Body

## 1. Introduction

In this paper, we study empirical risk minimization scheme (ERM) for quantile regression. LetX be a compact metric space (input space) and Y=ℝ. Let ρ be a fixed but unknown probability distribution on Z:=X×Y which describes the noise of sampling. The conditional quantile regression aims at producing functions to estimate quantile regression functions. With a prespecified 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 t∈Y satisfying
(1)ρ((-∞,t]∣x)≥τ,ρ([t,∞)∣x)≥1-τ,x∈X,
where ρ(·∣x) is the conditional distribution of ρ at x∈X.We consider a learning algorithm generated by ERM scheme associated with pinball loss and hypothesis spaceℋ. The pinball lossLτ:ℝ→[0,∞) is defined by
(2)Lτ(r)={(τ-1)r,ifr≤0,τr,ifr≥0.
The hypothesis space ℋ is a compact subset of C(X). So there exists some M>0 such that ∥f∥C(X)≤M for any f∈ℋ. We assume without loss of generality ∥f∥C(X)≤1 for any f∈ℋ.The ERM scheme for quantile regression is defined with a samplez={(xi,yi)}i=1m∈Zm drawn independently from ρ as follows:
(3)fz=argminf∈ℋ1m∑i=1m‍Lτ(yi-f(xi)).A family of kernel based learning algorithms for quantile regression has been widely studied in a large literature [1–4] and references therein. The form of the algorithms is a regularized scheme in a reproducing kernel Hilbert space ℋK (RKHS, see [5] for details) associated with a Mercer kernel K. Given a sample z the kernel based regularized scheme for quantile regression is defined by
(4)fz,λ=argminf∈ℋK{1m∑i=1m‍Lτ(yi-f(xi))+λ∥f∥K2}.
In [1, 3, 4], error analysis for general ℋK has been done. Learning with varying Gaussian kernel was studied in [2].ERM scheme (3) is very different from kernel based regularized scheme (4). The output function fz produced by the ERM scheme has a uniform bound, under our assumption, ∥fz∥C(X)≤1. However, we cannot expect it for fz,λ. It is easy to see that λ∥fz,λ∥K2≤∑i=1m‍|yi| by choosing f=0. It happens often that ∥fz,λ∥K→∞ as λ→0. The lack of a uniform bound for fz,λ has a serious negative impact on the learning rates. So in the literature of kernel based regularized schemes for quantile regression, values of the output function fz,λ are always projected onto the interval [-1,1], and error analysis is conducted for the projected function, not fz,λ itself.In this paper, we aim at establishing convergence and learning rates for the error∥fz-fτ,ρ∥LρXr in the space LρXr. Here r>0 depends on the pair (ρ,τ) which will be decided in Section 2 and ρX is the marginal distribution of ρ on X. In the rest of this paper, we assume Y=[-1,1] which in turn leads to values of the target function fτ,ρ lie in the same interval.


## 2. Noise Condition and Main Results

There has been a large literature in learning theory (see [6] and references therein) devoted to the least square regression. It aims at learning the regression function fρ(x)=∫Y‍ydρ(y∣x). The identity ℰls(f)-ℰls(fρ)=∥f-fρ∥LρX22 for the generalization error ℰls(f)=∫Z‍(y-f(x))2dρ leads to a variance-expectation bound with the form of Eξ2≤4Eξ, where ξ=(y-f(x))2-(y-fρ(x))2 on (Z,ρ). It plays an essential role in error analysis of kernel based regularized schemes.However, this identity relation and expectation-variance bound fail in the setting of the quantile regression. The reason is that the pinball loss is lack of strong convexity. If we add some noise condition on distributionρ named τ-quantile of p-average type q (see Definition 1), we can also get a similar identity relation which in turn enables us to have a variance-expectation bound stated in the following which is proved by Steinwart and Christman  [1].Definition 1.
Letp∈(0,∞] and q∈[1,∞). A distribution ρ on X×[-1,1] is said to have a τ-quantile of p-average type q if for ρX-almost every x∈X, there exist a τ-quantile t*∈ℝ and constants αρ(·∣x)∈(0,2],bρ(·∣x)>0 such that for each s∈[0,αρ(·∣x)],
(5)ρ((t*-s,t*)∣x)≥bρ(·∣x)sq-1,ρ((t*,t*+s)∣x)≥bρ(·∣x)sq-1,
and that the function γ on X defined by γ(x)=bρ(·∣x)αρ(·∣x)q-1 satisfies γ-1∈LρXp.We also need capacity of the hypothesis spaceℋ for our learning rates. Here in this paper, we measure the capacity by empirical covering numbers.Definition 2.
Let(𝔐,d) be a pseudometric space and S be a subset of 𝔐. For every ε>0, the covering number 𝒩(S,ε,d) of S with respect to ε and d is defined as the minimal number of balls of radius ε whose union covers S, that is,
(6)𝒩(S,ε,d)=min{ℓ∈ℕ:S⊂∪j=1ℓB(sj,ε)forsome{sj}j=1ℓ⊂𝔐},
where B(sj,ε)={s∈𝔐:d(s,sj)≤ε} is a ball in 𝔐.Definition 3.
Letℱ be a set of functions on X, x=(xi)i=1k⊂Xk and ℱ|x={(f(xi))i=1k:f∈ℱ}⊂ℝk. Set 𝒩2,x(ℱ,ε)=𝒩(ℱ|x,ε,d2). The ℓ2-empirical covering number of ℱ is defined by
(7)𝒩2(ℱ,ε)=supk∈ℕsupx∈Xk𝒩2,x(ℱ,ε),ε>0.
Here d2 is the normalized ℓ2-metric on the Euclidean space ℝk given by
(8)d2(a,b)=(1k∑i=1k‍|ai-bi|2)1/2fora=(ai)i=1k,b=(bi)i=1k∈ℝk.Assumption. Assume that the empirical covering number of the hypothesis space ℋ is bounded for some a>0 and ι∈(0,2),
(9)log𝒩2(ℋ,ε)≤aε-ι,∀ε>0.Theorem 4.
Assume thatρ satisfies (5) with some p∈(0,∞] and q∈[1,∞). Denote r=pq/(p+1). One further assumes that fτ,ρ is uniquely defined. If fτ,ρ∈ℋ and ℋ satisfies (9) with ι∈(0,2), then for any 0<δ<1, with confidence 1-δ, one has
(10)∥fz-fτ,ρ∥LρXr≤C~m-ϑlog2δ,
where
(11)ϑ=2(p+1)4q(p+1)-(2-ι)min{2(p+1),pq}
and C~ is a constant independent of m and δ.Remark 5.
In the ERM scheme, we can choosefτ,ρ∈ℋ which in turn makes the approximation error described by (23) equal to zero. However, it is impossible for the kernel based regularized scheme because of the appearance of the penalty term λ∥f∥K2.
Ifq≤2, all conditional distributions around the quantile behave similar to the uniform distribution. In this case r=pq/(p+1)≤2 and θ=min{2/q,p/(p+1)}=p/(p+1) for all p>0. Hence, ϑ=2(p+1)/((2+ι)pq+4q). Furthermore, when p is large enough, the parameter r tends to q and the power index for the above learning rate arbitrarily approaches to 2/(2+ι)q which shows that the learning rate power index for ∥fz-fτ,ρ∥LρXqq is arbitrarily close to 2/(2+ι) independent of q. In particular, ι can be arbitrarily small when ℋ is smooth enough. In this case, the power index of the learning rates 2/(2+ι) can be arbitrarily close to 1 which is the optimal learning rate for the least square regression.Let us take some examples to demonstrate the above main result.Example 6.
Letℋ be a unit ball of the sobolev space Hs with s>0. Observe that the empirical covering number is bounded above by the uniform covering number defined in Definition 2. Hence we have (see [6, 7])
(12)log𝒩2(ℋ,ε)≤Cs(1ε)n/s,
where n is the dimension of the input space X and Cs>0.
Under the same assumptions as Theorem4, we get that by replacing ι by n/s, for any 0<δ<1, with confidence 1-δ,
(13)∥fz-fτ,ρ∥LρXr≤C~m-ϑlog2δ,
where
(14)ϑ=2(p+1)4q(p+1)-(2-n/s)min{2(p+1),pq}
and C~ is a constant independent of m and δ.
We carry out the same discussions on the case ofq≤2 and large enough p as Remark 5. Therefore the power index of the learning rates for ∥fz-fτ,ρ∥LρXqq is arbitrarily close to 2/(2+n/s) independent of q. Furthermore, s can be arbitrarily large if the Sobolev space is smooth enough. In this special case, the learning rate power index arbitrarily approaches to 1.Example 7.
Letℋ be a unit ball of the reproducing kernel Hilbert space ℋσ generated by a Gaussian kernel (see [5]). Reference [7] tells us that
(15)log𝒩(ℋ,ε)≤Cn,σ(log1ε)n+1,∀ε>0,
where Cn,σ>0 depends only on n and σ>0. Obviously, the right-hand side of (15) is bounded by Cn,σ(1/ε)n+1.
So from Theorem4, we can get different learning rates with power index
(16)ϑ=2(p+1)4q(p+1)-(1-n)min{2(p+1),pq}.
If q≤2 and p is large enough, the power index of the learning rates for ∥fz-fτ,ρ∥LρXqq is arbitrarily close to 2/(3+n) which is very slow if n is large. However, in most data sets the data are concentrated on a much lower dimensional manifold embedded in the high dimensional space. In this setting an analysis that replaces n by the intrinsic dimension of the manifold would be of great interest (see [8] and references therein).


## 3. Error Analysis

Define the noise-free error calledgeneralization error associated with the pinball loss Lτ as
(17)ℰτ(f)=∫Z‍Lτ(y-f(x))dρforf:X→[-1,1].
Then the measurable function fτ,ρ is a minimizer of ℰτ. Obviously, fτ,ρ(x)∈[-1,1].We need the following results from [1] for our error analysis.Proposition 8.
LetLτ be the pinball loss. Assume that ρ satisfies (5) with some p∈(0,∞] and q∈[1,∞). Then for all f:X→[-1,1] one has
(18)∥f-fτ,ρ∥LρXr≤21-1/qq1/q∥γ-1∥LρXp1/q(ℰτ(f)-ℰτ(fτ,ρ))1/q.
Furthermore, with
(19)θ=min{2q,pp+1}∈(0,1],Cθ=22-θqθ∥γ-1∥LρXpθ>0,
one has
(20)E{(Lτ(y-f(x))-Lτ(y-fτ,ρ(x)))2}≤Cθ(ℰτ(f)-ℰτ(fτ,ρ))θ,∀f:X→Y.The above result implies that we can get convergence rates offz in the space LρXr by bounding the excess generalization error ℰτ(fz)-ℰτ(fτ,ρ).To boundℰτ(fz)-ℰτ(fτ,ρ), we need a standard error decomposition procedure [6] and a concentration inequality.


### 3.1. Error Decomposition

Define the empirical error associated with the pinball lossLτ as
(21)ℰz,τ(f)=1m∑i=1m‍Lτ(yi-f(xi))forf:X→[-1,1].
Define
(22)fℋ=argminf∈ℋℰτ(f)=argminf∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}.Lemma 9.
LetLτ be the pinball loss, fz be defined by (3) and fℋ∈ℋ by (22). Then
(23)ℰτ(fz)-ℰτ(fτ,ρ)≤[ℰτ(fz)-ℰτ(fτ,ρ)]-[ℰz,τ(fz)-ℰz,τ(fτ,ρ)]+[ℰz,τ(fℋ)-ℰz,τ(fτ,ρ)]-[ℰτ(fℋ)-ℰτ(fτ,ρ)]+ℰτ(fℋ)-ℰτ(fτ,ρ).Proof.
The excess generalization error can be written as(24)ℰτ(fz)-ℰτ(fτ,ρ)=[ℰτ(fz)-ℰz,τ(fz)]+[ℰz,τ(fz)-ℰz,τ(fℋ)]+[ℰz,τ(fℋ)-ℰτ(fℋ)]+[ℰτ(fℋ)-ℰτ(fτ,ρ)].
The definition of fz implies that ℰz,τ(fz)-ℰz,τ(fℋ)≤0. Furthermore, by subtracting and adding ℰτ(fτ,ρ) and ℰz,τ(fτ,ρ) in the first term and third term, we see that Lemma 9 holds true.We call the term (23) approximation error. It has been studied in [9].


### 3.2. Concentration Inequality and Sample Error

Let us recall the one-sided Bernstein inequality as follows.Lemma 10.
Letξ be a random variable on a probability space Z with variance σ2 satisfying |ξ-𝔼(ξ)|≤Mξ for some constant Mξ. Then for any 0<δ<1, with confidence 1-δ, one has
(25)1m∑i=1m‍ξ(zi)-𝔼(ξ)≤2Mξlog(1/δ)3m+2σ2log(1/δ)m.Proposition 11.
Letfℋ∈ℋ. Assume that ρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). For any 0<δ<1, with confidence 1-δ/2, (3.6) can be bounded as
(26)[ℰz,τ(fℋ)-ℰz,τ(fτ,ρ)]-[ℰτ(fℋ)-ℰτ(fτ,ρ)]≤4log(2/δ)3m+(2Cθlog(2/δ)m)1/(2-θ)+ℰτ(fℋ)-ℰτ(fτ,ρ).Proof.
Letξ(z)=Lτ(y-fℋ(x))-Lτ(y-fτ,ρ(x)) which satisfies |ξ|≤2 and in turn |ξ-E(ξ)|≤2. The variance bound (20) implies that
(27)E(ξ-E(ξ))2≤Eξ2≤Cθ(ℰτ(fℋ)-ℰτ(fτ,ρ))θ.
Using (25) on the random variable ξ(z)=Lτ(y-fℋ(x))-Lτ(y-fτ,ρ(x)), we can get the desired bound (28) with the help of Young’s inequality.Let us turn to estimate the sample error (3.5) involving the functionfz which runs over a set of functions since z is a random sample itself. To estimate it, we use a concentration inequality below involving empirical covering numbers [10–12].Lemma 12.
Letℱ be a class of measurable functions on Z. Assume that there are constants B,c>0 and α∈[0,1] and ∥f∥∞≤B and 𝔼f2≤c(𝔼f)α for every f∈ℱ. If (7) holds, then there exists a constant cι′ depending only on ι such that for any t>0, with probability at least 1-e-t, there holds
(28)𝔼f-1m∑i=1m‍f(zi)≤12η1-α(𝔼f)α+cι′η+2(ctm)1/(2-α)+18Btm,∀f∈ℱ,
where
(29)η:=max{c(2-ι)/(4-2α+ια)(am)2/(4-2α+ια),B(2-ι)/(2+ι)(am)2/(2+ι)}.We apply Lemma12 to a function set ℱ, where
(30)ℱ={Lτ(y-f(x))-Lτ(y-fτ,ρ(x)):f∈ℋ}.Proposition 13.
Assumeρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). If ℋ satisfies (9) with ι∈(0,2), then for any 0<δ<1, with confidence 1-δ/2, one has
(31)[ℰτ(f)-ℰτ(fτ,ρ)]-[ℰz,τ(f)-ℰz,τ(fτ,ρ)]≤12[ℰτ(f)-ℰτ(fτ,ρ)]+Cι,θlog2δ(1m)2/(4-2θ+ιθ),∀f∈ℋ,
where
(32)Cι,θ=(12+cι′)max{Cθ(2-ι)/(4-2θ+ιθ)a2/(4-2θ+ιθ),2(2-ι)/(2+ι)a2/(2+ι)}+2Cθ1/(2-θ)+36.Proof.
Takeg∈ℱ with the form g(z)=Lτ(y-f(x))-Lτ(y-fτ,ρ(x)) where f∈ℋ. Hence 𝔼g=ℰτ(f)-ℰτ(fτ,ρ) and (1/m)∑i=1m‍g(zi)=ℰz,τ(f)-ℰz,τ(fτ,ρ).
The Lipschitz property of the pinball lossLτ implies that
(33)|g(z)|≤|f(x)-fτ,ρ(x)|≤2.
For g1,g2∈ℱ, we have
(34)|g1(z)-g2(z)|=|Lτ(y-f1(x))-Lτ(y-f2(x))|≤|f1(x)-f2(x)|,
where f1,f2∈ℋ. It follows that
(35)𝒩2,z(ℱ,ε)≤𝒩2,x(ℋ,ε).
Hence
(36)log𝒩2(ℱ,ε)≤aε-ι.
Applying Lemma12 with B=2,α=θ, and c=Cθ, we know that for any 0<δ<1, with confidence 1-δ/2, there holds
(37)𝔼f-1m∑i=1m‍g(zi)≤12η1-θ(𝔼g)θ+cι′η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m≤12𝔼g+(12+cι′)η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m.
Here
(38)η≤max{Cθ(2-ι)/(4-2θ+ιθ)a2/(4-2θ+ιθ),2(2-ι)/(2+ι)a2/(2+ι)}×(1m)2/(4-2θ+ιθ).
Note that
(39)(12+cι′)η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m≤Cι,θlog2δ(1m)2/(4-2θ+ιθ),
where Cι,θ is indicated in (32). Then our desired bound holds true.Proposition 14.
Assumeρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). If ℋ satisfies (9) with ι∈(0,2) Then for any 0<δ<1, with confidence 1-δ, there holds
(40)ℰτ(fz)-ℰτ(fτ,ρ)≤2(ℰτ(fℋ)-ℰτ(fτ,ρ))+8log(2/δ)3m+2(2Cθlog(2/δ)m)1/(2-θ)+2Cι,θlog2δ(1m)2/(4-2θ+ιθ).The above bound follows directly from Propositions11 and 13 with the fact that fz∈ℋ.


### 3.3. Bounding the Total Error

Now we are in a position to present our general result on error analysis for algorithm (3).Theorem 15.
Assume thatρ satisfies (5) with some p∈(0,∞] and q∈[1,∞). Denote γ=pq/(p+1). Further assume that ℋ satisfies (9) with ι∈(0,2) and fτ,ρ is uniquely defined. Then for any 0<δ<1, with confidence 1-δ, one has
(41)∥fz-fτ,ρ∥LρXr≤C~inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}1/q+C~m-ϑlog2δ,
where
(42)ϑ=2(p+1)4q(p+1)-(2-ι)min{2(p+1),pq}
and C~ are constant independent of m and δ.Proof.
Combining (18), (19), and (40), with confidence 1-δ, we have
(43)∥fz-fτ,ρ∥LρXr≤C~(ℰτ(fℋ)-ℰτ(fτ,ρ))1/q+C~log2δ(1m)2/q(4-2θ+ιθ)≤C~inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}1/q+C~m-ϑlog2δ,
where
(44)ϑ=2(p+1)4q(p+1)-(2-ι)min{2(p+1),pq},C~=2q1/q∥γ-1∥LρXp1/q(43+(2Cθ)1/(2-θ)+Cι,θ)1/q.Proof of Theorem4.
The assumptionfτ,ρ∈ℋ implies that
(45)inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}=0.
Therefore, our desired result comes directly from Theorem15.


## 3.1. Error Decomposition

Define the empirical error associated with the pinball lossLτ as
(21)ℰz,τ(f)=1m∑i=1m‍Lτ(yi-f(xi))forf:X→[-1,1].
Define
(22)fℋ=argminf∈ℋℰτ(f)=argminf∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}.Lemma 9.
LetLτ be the pinball loss, fz be defined by (3) and fℋ∈ℋ by (22). Then
(23)ℰτ(fz)-ℰτ(fτ,ρ)≤[ℰτ(fz)-ℰτ(fτ,ρ)]-[ℰz,τ(fz)-ℰz,τ(fτ,ρ)]+[ℰz,τ(fℋ)-ℰz,τ(fτ,ρ)]-[ℰτ(fℋ)-ℰτ(fτ,ρ)]+ℰτ(fℋ)-ℰτ(fτ,ρ).Proof.
The excess generalization error can be written as(24)ℰτ(fz)-ℰτ(fτ,ρ)=[ℰτ(fz)-ℰz,τ(fz)]+[ℰz,τ(fz)-ℰz,τ(fℋ)]+[ℰz,τ(fℋ)-ℰτ(fℋ)]+[ℰτ(fℋ)-ℰτ(fτ,ρ)].
The definition of fz implies that ℰz,τ(fz)-ℰz,τ(fℋ)≤0. Furthermore, by subtracting and adding ℰτ(fτ,ρ) and ℰz,τ(fτ,ρ) in the first term and third term, we see that Lemma 9 holds true.We call the term (23) approximation error. It has been studied in [9].


## 3.2. Concentration Inequality and Sample Error

Let us recall the one-sided Bernstein inequality as follows.Lemma 10.
Letξ be a random variable on a probability space Z with variance σ2 satisfying |ξ-𝔼(ξ)|≤Mξ for some constant Mξ. Then for any 0<δ<1, with confidence 1-δ, one has
(25)1m∑i=1m‍ξ(zi)-𝔼(ξ)≤2Mξlog(1/δ)3m+2σ2log(1/δ)m.Proposition 11.
Letfℋ∈ℋ. Assume that ρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). For any 0<δ<1, with confidence 1-δ/2, (3.6) can be bounded as
(26)[ℰz,τ(fℋ)-ℰz,τ(fτ,ρ)]-[ℰτ(fℋ)-ℰτ(fτ,ρ)]≤4log(2/δ)3m+(2Cθlog(2/δ)m)1/(2-θ)+ℰτ(fℋ)-ℰτ(fτ,ρ).Proof.
Letξ(z)=Lτ(y-fℋ(x))-Lτ(y-fτ,ρ(x)) which satisfies |ξ|≤2 and in turn |ξ-E(ξ)|≤2. The variance bound (20) implies that
(27)E(ξ-E(ξ))2≤Eξ2≤Cθ(ℰτ(fℋ)-ℰτ(fτ,ρ))θ.
Using (25) on the random variable ξ(z)=Lτ(y-fℋ(x))-Lτ(y-fτ,ρ(x)), we can get the desired bound (28) with the help of Young’s inequality.Let us turn to estimate the sample error (3.5) involving the functionfz which runs over a set of functions since z is a random sample itself. To estimate it, we use a concentration inequality below involving empirical covering numbers [10–12].Lemma 12.
Letℱ be a class of measurable functions on Z. Assume that there are constants B,c>0 and α∈[0,1] and ∥f∥∞≤B and 𝔼f2≤c(𝔼f)α for every f∈ℱ. If (7) holds, then there exists a constant cι′ depending only on ι such that for any t>0, with probability at least 1-e-t, there holds
(28)𝔼f-1m∑i=1m‍f(zi)≤12η1-α(𝔼f)α+cι′η+2(ctm)1/(2-α)+18Btm,∀f∈ℱ,
where
(29)η:=max{c(2-ι)/(4-2α+ια)(am)2/(4-2α+ια),B(2-ι)/(2+ι)(am)2/(2+ι)}.We apply Lemma12 to a function set ℱ, where
(30)ℱ={Lτ(y-f(x))-Lτ(y-fτ,ρ(x)):f∈ℋ}.Proposition 13.
Assumeρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). If ℋ satisfies (9) with ι∈(0,2), then for any 0<δ<1, with confidence 1-δ/2, one has
(31)[ℰτ(f)-ℰτ(fτ,ρ)]-[ℰz,τ(f)-ℰz,τ(fτ,ρ)]≤12[ℰτ(f)-ℰτ(fτ,ρ)]+Cι,θlog2δ(1m)2/(4-2θ+ιθ),∀f∈ℋ,
where
(32)Cι,θ=(12+cι′)max{Cθ(2-ι)/(4-2θ+ιθ)a2/(4-2θ+ιθ),2(2-ι)/(2+ι)a2/(2+ι)}+2Cθ1/(2-θ)+36.Proof.
Takeg∈ℱ with the form g(z)=Lτ(y-f(x))-Lτ(y-fτ,ρ(x)) where f∈ℋ. Hence 𝔼g=ℰτ(f)-ℰτ(fτ,ρ) and (1/m)∑i=1m‍g(zi)=ℰz,τ(f)-ℰz,τ(fτ,ρ).
The Lipschitz property of the pinball lossLτ implies that
(33)|g(z)|≤|f(x)-fτ,ρ(x)|≤2.
For g1,g2∈ℱ, we have
(34)|g1(z)-g2(z)|=|Lτ(y-f1(x))-Lτ(y-f2(x))|≤|f1(x)-f2(x)|,
where f1,f2∈ℋ. It follows that
(35)𝒩2,z(ℱ,ε)≤𝒩2,x(ℋ,ε).
Hence
(36)log𝒩2(ℱ,ε)≤aε-ι.
Applying Lemma12 with B=2,α=θ, and c=Cθ, we know that for any 0<δ<1, with confidence 1-δ/2, there holds
(37)𝔼f-1m∑i=1m‍g(zi)≤12η1-θ(𝔼g)θ+cι′η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m≤12𝔼g+(12+cι′)η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m.
Here
(38)η≤max{Cθ(2-ι)/(4-2θ+ιθ)a2/(4-2θ+ιθ),2(2-ι)/(2+ι)a2/(2+ι)}×(1m)2/(4-2θ+ιθ).
Note that
(39)(12+cι′)η+2(Cθlog(2/δ)m)1/(2-θ)+36log(2/δ)m≤Cι,θlog2δ(1m)2/(4-2θ+ιθ),
where Cι,θ is indicated in (32). Then our desired bound holds true.Proposition 14.
Assumeρ on X×[-1,1] satisfies the variance bound (20) with index θ indicated in (19). If ℋ satisfies (9) with ι∈(0,2) Then for any 0<δ<1, with confidence 1-δ, there holds
(40)ℰτ(fz)-ℰτ(fτ,ρ)≤2(ℰτ(fℋ)-ℰτ(fτ,ρ))+8log(2/δ)3m+2(2Cθlog(2/δ)m)1/(2-θ)+2Cι,θlog2δ(1m)2/(4-2θ+ιθ).The above bound follows directly from Propositions11 and 13 with the fact that fz∈ℋ.


## 3.3. Bounding the Total Error

Now we are in a position to present our general result on error analysis for algorithm (3).Theorem 15.
Assume thatρ satisfies (5) with some p∈(0,∞] and q∈[1,∞). Denote γ=pq/(p+1). Further assume that ℋ satisfies (9) with ι∈(0,2) and fτ,ρ is uniquely defined. Then for any 0<δ<1, with confidence 1-δ, one has
(41)∥fz-fτ,ρ∥LρXr≤C~inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}1/q+C~m-ϑlog2δ,
where
(42)ϑ=2(p+1)4q(p+1)-(2-ι)min{2(p+1),pq}
and C~ are constant independent of m and δ.Proof.
Combining (18), (19), and (40), with confidence 1-δ, we have
(43)∥fz-fτ,ρ∥LρXr≤C~(ℰτ(fℋ)-ℰτ(fτ,ρ))1/q+C~log2δ(1m)2/q(4-2θ+ιθ)≤C~inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}1/q+C~m-ϑlog2δ,
where
(44)ϑ=2(p+1)4q(p+1)-(2-ι)min{2(p+1),pq},C~=2q1/q∥γ-1∥LρXp1/q(43+(2Cθ)1/(2-θ)+Cι,θ)1/q.Proof of Theorem4.
The assumptionfτ,ρ∈ℋ implies that
(45)inff∈ℋ{ℰτ(f)-ℰτ(fτ,ρ)}=0.
Therefore, our desired result comes directly from Theorem15.


## 4. Further Discussions

In this paper, we studied ERM algorithm (3) for quantile regression and provide convergence and learning rates. We showed some essential differences between ERM scheme and kernel based regularized scheme for quantile regression. We also point out the difficulty to deal with quantile regression: the lack of strong convexity of the pinball loss. To overcome this difficulty, some noise condition on ρ is proposed to enable us to get a variance-expectation bound similar to the one for the least square regression.In our analysis we just considerf∈ℋ and ∥f∥C(X)≤1. The case ∥f∥C(X)≤R for R≥1 would be interesting in the future work. The approximation error involving R can be estimated by the knowledge of interpolation space.In our setting, the sample is drawn independently from the distributionρ. However, in many practical problems, the i.i.d condition is a little demanding, so it would be interesting to investigate the ERM scheme for quantile regression with nonidentical distributions [13, 14] or dependent sampling [15].



---

*Source: 148490-2013-03-28.xml*