arXiv:1701.01956v1 [] 8 Jan 2017

Learning Rates of Regression with q-norm Loss and Threshold
†

Ting Hu
School of Mathematics and Statistics, Wuhan University
Luojia Hill, Wuhan 430072, China, tinghu@whu.edu.cn

Yuan Yao
School of Mathematical Sciences, Peking University
Beijing 100871, China, yuany@math.pku.edu.cn

Abstract
This paper studies some robust regression problems associated with the q-norm loss
(q ≥ 1) and the ǫ-insensitive q-norm loss in the reproducing kernel Hilbert space. We
establish a variance-expectation bound under a priori noise condition on the conditional
distribution, which is the key technique to measure the error bound. Explicit learning
rates will be given under the approximation ability assumptions on the reproducing
kernel Hilbert space.

Key Words and Phrases. Insensitive q-norm loss, quantile regression, reproducing kernel
Hilbert space, sparsity.
Mathematical Subject Classification. 68Q32, 41A25

1

Introduction

In this paper we consider regression with the q-norm loss ψq with q ≥ 1 and an ǫ-insensitive
q-norm loss ψqǫ (to be defined) with a threshold ǫ > 0. Here ψq is the univariate function
defined by ψq (u) = |u|q . For a learning algorithm generated by a regularization scheme in

1

reproducing kernel Hilbert spaces, learning rates and approximation error will be presented
when ǫ is chosen appropriately for balancing learning rates and sparsity.
For q = 1, the regression problem is the classical statistical method of least absolute
deviations which is more robust than the least squares method and is resistant to outliers
in data [4]. Its associated loss ψ(u) = |u|, u ∈ IR, is widely used in practical applications for
robustness. In fact, for all q < 2, the loss ψq is less sensitive to outliers and is thus more
robust than the square loss. Vapnik [13] proposed an ǫ-insensitive loss ψ ǫ (u) : IR → IR+ to
get sparsity in support vector regressions, which is defined by

|u| − ǫ, if |u| > ǫ,
ǫ
(1.1)
ψ (u) =
0,
if |u| ≤ ǫ.
When fixing ǫ > 0, error analysis was conducted in [12]. Xiang, Hu and Zhou [17, 18] showed
how to accelerate learning rates and preserve sparsity by adapting ǫ. In [5], they discussed
the convergence ability with flexible ǫ in an online algorithm. For the quantile regression
with ǫ = 0 and a pinball loss having different slopes in different sides of the origin in IR [6],
Steinwart and Christamann [10, 9] established comparison theorems and derived learning
rates under some noise conditions.
In this paper, we apply the q-norm loss ψq with q > 1 to improve the convexity of
the insensitive loss ψ. Our results show how the insensitive parameter ǫ that produces the
sparsity can be chosen adaptively as the function of the sample size ǫ = ǫ(T ) → 0 when
T → ∞, to affect the error rates of the learning algorithm (to be defined by (1.4)). Such

results include some early studies as special cases.
In the sequel, assume that the input space X is a compact metric space and the output
space Y = IR. Let ρ be a Borel probability measure on Z := X × Y , ρx (·) be the conditional
distribution of ρ at each x ∈ X and ρX be the marginal distribution on X. For a measurable
function f : X → Y, the generalization error E(f ) associated with the q-norm loss ψq , is
defined by

E(f ) =

Z

Z

ψq (y − f (x))dρ.

(1.2)

Denote fq : X → Y as the minimizer of the generalization error E(f ) over all measurable

functions. Its properties and the corresponding learning problem in the empirical risk minimization framework were discussed in [20]. When q = 1, the target function fq is a function
2

containing the medians of the conditional distribution for all x ∈ X. For symmetric distributions, the median is also the regression function, which is the conditional mean for given
X. We aim at learning the minimizer fq from a sample z = {(xi , yi )}Ti=1 ∈ Z T , which is
assumed to be independently drawn according to ρ. Inspired by the ǫ-insensitive loss [13],
we introduce an ǫ-insensitive q-norm loss ψqǫ which is defined by

(|u| − ǫ)q , if |u| > ǫ,
ǫ
ψq (u) =
0,
if |u| ≤ ǫ.

(1.3)

Our learning task will be carried out by a regularization scheme in reproducing kernel Hilbert
spaces. With a continuous, symmetric and positive semidefinite function K : X × X → IR
(called a Mercer kernel), the reproducing kernel Hilbert space (RKHS) HK is defined as the

completion of the span of {Kx = K(x, ·) : x ∈ X} with the inner product h·, ·iK satisfying
hKx , Ku iK = K(x, u). The regularization algorithm in the paper takes the form
fzǫ

T
1 X
= arg min
ψqǫ (f (xt ) − yt ) + λkf k2K .
f ∈HK T
t=1

(1.4)

Here λ > 0 is a regularization parameter. Our learning rates are stated in terms of approximation or regularization error, noise conditions, and the capacity of the RKHS. Our main
goal is to study how the learned function fzǫ in (1.4) converges to the target function fq .
There is a large literature [1, 16, 7] in learning theory for studying the approximation error
or regularization error D(λ) of the triple (K, ρ, q) defined by

D(λ) = min E(f ) − E(fq ) + λkf k2K , λ > 0.
f ∈HK

The regularization function is defined as

fλ = arg min E(f ) − E(fq ) + λkf k2K .
f ∈HK

(1.5)

In the sequel, let LpρX with p > 0 be the space of p integrable functions with respect to ρX
and k · kLpρX be the norm in LpρX . A usual assumption on the regularization error D(λ) which
imposes certain smoothness on HK is
D(λ) ≤ D0 λβ ,
with some 0 < β ≤ 1 and D0 > 0.
3

∀λ > 0

(1.6)

Remark 1. Assumption (1.6) always holds with β = 0. When the target function fq ∈
HK and HK is dense in C(X) which consists of bounded continuous functions on X, the

approximation error D(λ) → 0 as λ → 0. Thus, the decay (1.6) is natural and can be
illustrated in terms of interpolation spaces [7]. Define the integral operator LK : L2ρX → L2ρX
R
by LK (f )(x) = X K(x, y)f (y)dρX , x ∈ X, f ∈ L2ρX and suppose that the minimizer fq is in
ν
the range of LνK with 0 < ν ≤ 21 . When q = 1, the approximation error D(λ) can be O(λ 1−ν )

for quantile regression [18]. When q = 2, D(λ) = O(λ2ν ) for the least square. For other
q > 1, the associated loss ψq is Lipschitz in a bounded domain and the corresponding D(λ)
can be characterized by the K-functional [1], which can have the same polynomial decay as

(1.6).

We assume that the conditional distribution ρx (·) is supported on [−M, M], M > 0
at each x and is non-degenerate, i.e. any non-empty open set of Y has strictly positive
measure, which ensures that the target function fq is unique. Without loss of generality, let
the support of ρx (·) be [− 12 , − 12 ] at each x ∈ X and our analysis below is applicable for any
M > 0. We will prove that in the next section. It is natural to project values of the learned
function fzǫ onto some interval by the projection operator [1, 15].
Definition 1. The projection operator π on
onto the interval [−1, 1] is defined by

 1,
f (x),
π(f (x)) =

−1,

the space of measurable functions f : X → IR
if f (x) ≥ 1,
if − 1 < f (x) < 1,
if f (x) ≤ −1.

To demonstrate our main result in the general case, we shall give the following learning
rate in the special case when K is C ∞ .
Theorem 1. Let X ⊂ IRn and K ∈ C ∞ (X × X). Assume that fq ∈ HK with q > 1,
kfq k∞ ≤

1
4

and the conditional distributions {ρx (·)}x∈X have density functions given by

dρx
A|y − fq (x)|ϕ , if |y − fq (x)| ≤ 41 ,
(1.7)
(y) =
0,
otherwise,
dy

4

q+ϕ+1

where A = 22ϕ+1 (ϕ + 1), ϕ > 0. Take λ = ǫ = T − 2(q+ϕ) , then for any 0 < δ < 1, with
confidence 1 − δ, we have
kπ(fzǫ )

− fq kLq+ϕ+1
≤C
ρ
X

′

r

1
3
log T − 2(q+ϕ) ,
δ

where C ′ is a constant independent of T or δ.
To state our main result in the general case, we need a noise condition on the measure ρ
introduced in [9, 10].
Definition 2. Let 0 < p ≤ ∞ and w > 0. We say that ρ has a p-average type w if there
exist two functions b and a from X to IR such that {baw }−1 ∈ LpρX and for any x ∈ X and
s ∈ (0, a(x)], there holds
ρx ({y : fq (x) ≤ y ≤ fq (x) + s}) ≥ b(x)sw
and
ρx ({y : fq (x) − s ≤ y ≤ fq (x)}) ≥ b(x)sw .

(1.8)

This assumption can be satisfied by many common conditional distributions such as
Guassian, students’ t distributions and uniform distributions. In the following, we will give
an example to illustrate Definition 2 in detail. More examples can be found in [9, 10].
Example 1. We assume that the conditional distributions {ρx (·)}x∈X are Guassian distri2
1
x)
x
(y) = √2πσ
}, where {ux }x∈X
exp{− (y−u
butions with a uniform variance σ > 0, i.e. dρ
dy
2σ2

are expectations of the Gaussian distributions {ρx (·)}x∈X . It is not difficult to check that the
minimizer fρ (x) can take the value of ux at each x ∈ X, then for any s ∈ (0, σ], there holds
Z fρ (x)+s
(y − ux )2
1
exp{−
ρx ({y : fq (x) ≤ y ≤ fq (x) + s} = √
}dy
2σ 2
2πσ fρ (x)
Z s
Z s
1
1
1
e− 2
y2
s2
=√
exp{− 2 }dy ≥ √
exp{− 2 }dy ≥ √
s.
2σ
2σ
2πσ 0
2πσ 0
2πσ
1

By similarity, we also have that ρx ({y : fq (x) − s ≤ y ≤ fq (x)} ≥
ρ has a ∞-average type 1.
5

e− 2
√
s.
2πσ

Thus, the measure

Our error analysis is related to the capacity of the hypothesis space HK which is measured
by covering numbers.
Definition 3. For a subset S of C(X) and ε > 0, the covering number N (S, ε) is the
minimal integer l ∈ IN such that there exist l disks with radius ε covering S.
The covering numbers of balls BR = {f ∈ HK : kf kK ≤ R} with R > 0 of the RKHS

have been well understood in the learning theory [22, 23]. In this paper, we assume for some
k > 0 and Ck > 0 that
1 k
log N (B1 , ε) ≤ Ck
, ∀ε > 0.
(1.9)
ε
Remark 2. When X is a bounded subset of IRn and the RKHS HK is a Sobolev space
. If
H m (X) with index m, it is shown [22] that the condition (1.9) holds true with k = 2n
m

the kernel K lies in the smooth space C ∞ (X × X), then (1.9) is satisfied for an arbitrarily
small k > 0. Another common way to measure the capacity of HK is the empirical covering
number [21], which is out of scope of our discussion in this paper.
Denote

p
p(q + w)
2
,
} ∈ (0, 1],
r=
> 0.
(1.10)
q+w p+1
p+1
The following learning rates in the general case will be proved in Section 4. One need to
θ = min{

point out that the proof of Theorem 2 is only applicable to the case q > 1. However, when
q = 1, it is a special case of quantile regression and the same learning rates as those of
Theorem 2 can be found in [17, 18].
Theorem 2. Suppose that ρ has a p-average type w for some 0 < p ≤ ∞ and ω > 0. Assume
that the regularization error condition (1.6) is satisfied for some 0 < β ≤ 1 and (1.9) holds

with k > 0. Take λ = T −α , ǫ = T −η with 0 < α ≤ 1, 0 < η ≤ ∞. Let ξ > 0. Then for any
0 < δ < 1, with confidence 1 − δ, there holds
r

3
3
2
kπ(fzǫ ) − fq kLrρX ≤ C ∗ log
(1.11)
log T −Λ
ξ
δ
where C ∗ is a constant independent of T or δ ,
Λ=


1
q(1 − β)α 1
1
k
min η, αβ, 1 −
,
,
−
ϑ
q+w
2
2−θ 2+k−θ 1+k
6

with ϑ = max
that

n

α−η α(1−β) α
, 2 ,2
2

+

q(1−β)α
4

− 21 , α2 −

ϑ<

1
, [α(2+k−θ)−1](1+k)
2(2−θ)
(2+k−θ)(2+k)

1+k
.
k(2 + k − θ)

+ξ

o

≥ 0 provided
(1.12)

Corollary 1. Let X ⊂ IRn , K ∈ C ∞ (X × X). Assume (1.6) and (1.8). Take λ = T −1 ,
ǫ = T −η with 0 < η ≤ ∞. If 1 < q ≤ 2, then the index Λ for the learning rate (1.11) is
1
1
min{η, β, 2−θ
}.
q+w

Remark 3. When η = ∞, the corresponding threshold ǫ is 0 and it is a least square problem
for q = 2, which is widely discussed in [15, 16]. If ρ has a ∞-average type w with w > 0 and

= O(T
fq ∈ HK , the learning rate kπ(fzǫ ) − fq kL2+w
ρ
1
− 1+w

1
− 2(1+w)

X

) for the least square. It follows

) by k · kL2ρ ≤ k · kLρ2+w . Thus, it can be near the
that the error kπ(fzǫ ) − fq k2L2ρ = O(T
X
X
X
optimal rate O(T −1) in L2ρX space if w is small enough.
q+w

1

p+1

When 1 < q < 2, the learning error will be O(T − q+w min{β, 2(q+w−1) , p+2 } ) with choice η ≥ β,

depending only on the HK ’s approximation ability (1.6) and noise condition (1.8). Specially,
1
when q goes to 1, it is the quantile regression [17, 18] and the best rate is O(T − 1+w ) in this
paper if ρ has a ∞-average type w with 0 < w ≤ 1 and fq ∈ HK .

2

Comparison and Perturbation Theorem

Approximation or learning ability of a regularized algorithm for regression problems can
usually be studied by estimating the excess generalization error E(f ) − E(fq ) for the learned
function fzǫ from the algorithm (1.4). However the following comparison theorem would yield
bounds for the error kf − fq kLrρX in the space LrρX when the noise condition is satisfied.
Theorem 3. If ρ has a p-average type w, then for any measurable function f : X → [−1, 1]
we have the inequality

kf − fq kLrρX ≤ Cr E(f ) − E(fq )
q−1

1

1

1

1
 q+w

where the constant Cr = 2 q+w q − q+w (q + w) q+w k(baw )−1 kLq+w
p .
ρ
X

7

(2.1)

Proof. For a measurable function f : X → [−1, 1], the generalization error E(f ) is rewritten
R
as E(f ) = X Cq,x (f (x))dρX where
Z
Z
Z
q
Cq,x (t) =
ψq (y − t)dρx (y) =
(y − t) dρx (y) +
(t − y)q dρx (y), x ∈ X.
Y

y>t

y<t

Denote t∗x = mint∈IR Cq,x (t). It is obvious that the minimizer fq (x) of E(f ) takes the value
of t∗x for each x ∈ X. Noting that the conditional distribution ρx (·) is supported on [− 21 , 21 ],

the minimizer t∗x can be on [− 21 , 21 ]. Consider the case q > 1. Since the loss function ψq is
(y−t)
| ≤ q|y − t|q−1 ≤ q for all y, t ∈ [− 12 , 21 ], by the corollary of Lebesgue
differential and | dψqdt

control convergence theorem, we can exchange the order of of integration and derivation of
R
R
(y−t)
′
′
(t) as Cq,x
(t) = dtd Y ψq (y − t)dρx (y) = Y dψqdt
Cq,x
dρx (y). This together with the fact
′
Cq,x
(t∗x ) = 0, ∀x ∈ X, we have
Z
Z
′
∗
∗
q−1
Cq,x (tx ) = q
(tx − y) dρx (y) − q
y<t∗x

y>t∗x

(y − t∗x )q−1 dρx (y) = 0,

which means that
Z

y<t∗x

(t∗x

− y)

q−1

dρx (y) =

Z

y>t∗x

(y − t∗x )q−1 dρx (y)

(2.2)

Rt ′
Let t∗x = 0 for simply, then we have Cq,x (t) − Cq,x (0) = 0 Cq,x
(s)ds, ∀t > 0. Noting that for
s > 0,
Z
Z

q−1
′
(s − y) dρx (y) −
(y − s)q−1 dρx (y)
Cq,x (s) = q
y<s
y>s
Z
Z

Z
q−1
q−1
=q
(s − y) dρx (y) +
(s − y) dρx (y) −
(y − s)q−1 dρx (y)
y<0
Z 0≤y<s
Z y>s
Z

q−1
q−1
q−1
≥q
(−y) dρx (y) +
(s − y) dρx (y) −
(y − s) dρx (y) .
y<0

0≤y<s

y>s

8

The above first term together with (2.2), then
Z
Z
Z

′
q−1
q−1
Cq,x (s) ≥ q
y dρx (y) +
(s − y) dρx (y) −
(y − s)q−1 dρx (y)
y>0
0≤y<s
y>s
Z
Z
Z

≥q
y q−1 dρx (y) +
(s − y)q−1dρx (y) −
y q−1dρx (y)
y>0
0≤y<s
y>s
Z
Z

=q
y q−1 dρx (y) +
(s − y)q−1dρx (y)
0≤y<s
Z 0<y≤s

q−1
q−1
=q
y
+ (s − y)
dρx (y) ≥ 21−q qsq−1 ρx ({y : 0 ≤ y ≤ s}).
0≤y≤s

Thus,

Cq,x (t) − Cq,x (0) ≥ 2

1−q

·q

Z

0

t

sq−1 ρx ({y : 0 ≤ y ≤ s})ds.

Let us consider the first case t ∈ [0, a(x)]. Noting the noise condition (1.8) and a(x) ≤ 1, we
obtain that

Cq,x (t) − Cq,x (0) ≥ 2

1−q

·q

Z

t

sq−1 b(x)sw ds =

0

21−q q
21−q q
b(x)tq+w ≥
b(x)a(x)w tq+w .
q+w
q+w

For the second case t ∈ [a(x), 1], we have
Z
 Z a(x)
1−q
q−1
Cq,x (t) − Cq,x (0) ≥ 2
·q
s ρx ({y : 0 ≤ y ≤ s})ds +
0

≥2

1−q

·q

Z

t

s

q−1

a(x)

a(x)

s

q−1

w

b(x)s ds +

0

Z

t

s

q−1

w

b(x)a(x) ds

a(x)
q+w 

ρx ({y : 0 ≤ y ≤ s})ds





wb(x)a(x)w tq 
wb(x)a(x)
≥ 21−q b(x)a(x)w tq −
q
q(q + w)
q+w
1−q
1−q
2 q
2 q
b(x)a(x)w tq ≥
b(x)a(x)w tq+w .
=
q+w
q+w
= 21−q · q

 b(x)a(x)w tq

−

In general, we can see that for any 0 < t ≤ 1,
Cq,x (t) − Cq,x (0) ≥
By similarity, if −1 ≤ t < 0, we also have
Cq,x (t) − Cq,x (0) ≥

21−q q
b(x)a(x)w tq+w .
q+w

(2.3)

21−q q
b(x)a(x)w tq+w .
q+w

(2.4)

9

Applying the two above inequalities (2.3) and (2.4) with t = f (x) and t∗x = fq (x), we have
that

By

p
p+1


|f (x) − fq (x)|q+w ≤ 2q−1 q −1 (q + w)(b(x)a(x)w )−1 Cq,x (f (x)) − Cq,x (fq (x)) .

power and integration,
Z
p(q−1)
p(q+w)
p
p
|f (x) − fq (x)| p+1 dρX ≤ 2 p+1 q − p+1 (q + w) p+1
ZX

 p
 p
(b(x)a(x)w )−1 p+1 Cq,x (f (x)) − Cq,x (fq (x)) p+1 dρX .
X

This with Holder inequality k · kL1ρ
p+1
,
p

X

≤ k · kLpρ∗ k · kLqρ∗ , p1∗ +
X

X

1
q∗

= 1, we obtain that for

p∗ = p + 1 and q ∗ =
Z
p
p
p(q−1)
 p+1
p(q+w)
p
p
E(f
)
−
E(f
)
|f (x) − fq (x)| p+1 dρX ≤ 2 p+1 q − p+1 (q + w) p+1 k(baw )−1 kLp+1
.
p
q
ρ
X

X

Then the desired conclusion (2.1) holds. For q = 1, (2.1) also holds and the proof can be
found in [18].
It yields a variance-expectation bound which will be applied in the next section.

Lemma 1. Under the same conditions as Theorem 3, for any measurable function f : X →
[−1, 1], we have the inequality

θ
E (ψq (f (x) − y) − ψq (fq (x) − y))2 ≤ Cθ (E(f ) − E(fq )

r
where the power index θ is defined as (1.10) and Cθ = Cr2 + 22−r (1 + kfq k2−r
∞ )Cr .

Proof. By the continuity of ψq (u) and |y| ≤ 21 , we see that
q−1
q−1
|ψq (f (x) − y) − ψq (fq (x) − y)| ≤ q(kf k∞
+ kfq k∞
+ 1)|f (x) − fq (x)|
q−1
≤ q(2 + kfq k∞
)|f (x) − fq (x)|.

It implies that

q−1
E (ψq (f (x) − y) − ψq (fq (x) − y))2 ≤ q 2 (kfq k∞
+ 2)2 E|f (x) − fq (x)|2 .
10

(2.5)

If r > 2, then

E|f (x) − fq (x)|2 ≤ E|f (x) − fq (x)|r

Else,

2
r

≤ Cr2 (E(f ) − E(fq )

2
 q+w

.


E|f (x) − fq (x)|2 ≤ E |f (x) − fq (x)|2−r · |f (x) − fq (x)|r
2−r
r
≤ 22−r (kf k∞
+ kfq k2−r
∞ )E|f (x) − fq (x)|
 p
2−r
≤ 22−r (1 + kfq k∞
)Crr (E(f ) − E(fq ) p+1 .

Combining the above two cases, we can get the conclusion (2.5).
The threshold ǫ changes with the sample size ǫ = ǫ(T ) and plays a crucial role in the
design of algorithm (1.4). By Taylor expansion, we have the following relation
ψqǫ (u) ≤ ψ(u) ≤ ψqǫ (u) + q|u|q−1ǫ,

∀u ∈ IR.

(2.6)

When the threshold ǫ → 0, the ǫ-insensitive q-norm loss ψqǫ converges to the q-norm function
ψq almost surely. In the following, we shall study the approximation of the target function
R
fq by fqǫ which is the minimizer of the ǫ-generalization error E ǫ (f ) = Z ψqǫ (f (x) − y)dρ for
ǫ > 0. Denote
Z
Z
Z
ǫ
q
ǫ
Cq,x (t) =
ψq (y−t)dρx (y) =
(y−t−ǫ) dρx (y)+
(t−y−ǫ)q dρx (y), x ∈ X. (2.7)
Y

y>t+ǫ

y<t−ǫ

ǫ
and tǫx is the minimizer of Cq,x
(t). By the same proof procedure as (2.2) in Theorem 3, we
also get
Z
Z
ǫ
q−1
(y − tx − ǫ) dρx (y) =
(tǫx − ǫ − y)q−1dρx (y)
y>tǫx +ǫ

y<tǫx −ǫ

(2.8)

and fqǫ takes the value of tǫx at each x ∈ X. Then the perturbation properties hold. We use
some ideas from [3] in the proof.

11

Proposition 1. For ǫ > 0, then
kfqǫ − fq k∞ ≤ ǫ.

(2.9)

For any measurable function f on X, we have
q−1
E(f ) − E(fq ) ≤ E ǫ (f ) − E ǫ (fqǫ ) + q(kf k∞
+ 1)ǫ

(2.10)

Proof. Suppose that there exist a x ∈ X satisfying fqǫ (x) − fq (x) > ǫ. Consider the case
q > 1. Together with the fact (2.2) and t∗x = fq (x), we note that
Z
Z
ǫ
q−1
(fq (x) − ǫ − y) dρx (y) ≥
(fqǫ (x) − ǫ − y)q−1dρx (y)
y<fqǫ (x)−ǫ

≥

Z

y<fq (x)

y<fq (x)

(fq (x) − y)q−1dρx (y) =

Z

y>fq (x)

(y − fq (x))q−1 dρx (y)

(2.11)

It is obvious that fqǫ (x) + ǫ > fq (x) by the hypothesis that fqǫ (x) − fq (x) > ǫ for any ǫ > 0.
By (2.8) with tǫx = fqǫ (x), we also get
Z
Z
q−1
(y − fq (x)) dρx (y) ≥
(y − fq (x))q−1 dρx (y)
y>fqǫ (x)+ǫ

y>fq (x)

≥

Z

y>fqǫ (x)+ǫ

(y −

fqǫ (x)

− ǫ)

q−1

dρx (y) =

Z

y<fqǫ (x)−ǫ

(fqǫ (x) − ǫ − y)q−1 dρx (y).

Combining (2.12) with (2.11), we know that
Z
Z
ǫ
q−1
(fq (x) − ǫ − y) dρx (y) =
(fqǫ (x) − ǫ − y)q−1dρx (y)
ǫ
y<fq (x)−ǫ
y<fq (x)
Z
Z
=
(fq (x) − y)q−1dρx (y) =
(y − fq (x))q−1 dρx (y)
y<f (x)
y>fq (x)
Z q
Z
q−1
=
(y − fq (x)) dρx (y) =
(y − fqǫ (x) − ǫ)q−1 dρx (y)
y>fqǫ (x)+ǫ

(2.12)

(2.13)

y>fqǫ (x)+ǫ

The above equalities hold if and only if ρx ({y : y > fq (x)}) = 0 and ρx ({y : y <
fqǫ (x) − ǫ}) = 0 at the same time. Immediately, we see that ρx ({y : y ≤ fq (x)}) = 1 − ρx ({y :
y > fq (x)}) = 1. By the hypothesis fqǫ (x) − fq (x) > ǫ, it follows that
ρx ({y : y ≤ fq (x)}) ≤ ρx ({y : y < fqǫ (x) − ǫ}) = 0.
12

This is contradiction. By similarity, we get that fqǫ (x) − fq (x) < −ǫ for each x ∈ X. Then
the desired conclusion (2.9) holds. By the relation (2.6) and |y| ≤ 21 , we can see that
q−1
q−1
E(f ) − E(fq ) ≤ E ǫ (f ) − E ǫ (fq ) + qkf − yk∞
ǫ ≤ E ǫ (f ) − E ǫ (fq ) + q(kf k∞
+ 1)ǫ.

Then the desired conclusion (2.10) holds.
We recall the fact that the conditional distribution ρx (·) is non-degenerate for each x ∈ X,

then the uniqueness of the minimizer fqǫ is stated as following. For simply, we denote fqǫ as
the target function fq and E ǫ (f ) as the generalization error E(f ) with the q-norm loss ψq
when ǫ = 0 in the next proposition.

Proposition 2. For 0 ≤ ǫ ≤ 12 , the function fqǫ is the unique minimizer of the ǫ-generalization
error E ǫ (f ).

Proof. Suppose that fqǫ is not the unique minimizer. For some x ∈ X, there exists t1 (x) <

ǫ
t2 (x) such that they are both the minimizers of Cq,x
(t) by (2.7) and satisfy the equality (2.8)
with tǫx = t1 (x) or tǫx = t2 (x) . Applying (2.8) with tǫx = t1 (x) and t1 (x) < t2 (x), it follows
that
Z
Z
q−1
(t2 (x) − ǫ − y) dρx (y) ≥
(t2 (x) − ǫ − y)q−1 dρx (y)
y<t2 (x)−ǫ
y<t1 (x)−ǫ
Z
Z
q−1
(t1 (x) − ǫ − y) dρx (y) =
(y − t1 (x) − ǫ)q−1 dρx (y)
≥
y<t (x)−ǫ
y>t (x)+ǫ
Z 1
Z 1
≥
(y − t1 (x) − ǫ)q−1 dρx (y) ≥
(y − t2 (x) − ǫ)q−1 dρx (y).
y>t2 (x)+ǫ

y>t2 (x)+ǫ

Applying (2.8) with tǫx = t2 (x) again, we see that the first term of the above inequality
R
R
q−1
(t
(x)
−
ǫ
−
y)
dρ
(y)
is
equal
to
the
last
term
(y − t2 (x) − ǫ)q−1 dρx (y).
2
x
y<t2 (x)−ǫ
y>t2 (x)+ǫ
This implies
Z

y<t2 (x)−ǫ

=

(t2 (x) − ǫ − y)

Z

y<t1 (x)−ǫ

=

Z

y>t2 (x)+ǫ

q−1

(t1 (x) − ǫ − y)

dρx (y) =

Z

y<t1 (x)−ǫ

q−1

dρx (y) =

(y − t1 (x) − ǫ)q−1 dρx (y) =
13

Z

Z

(t2 (x) − ǫ − y)q−1 dρx (y)

y>t1 (x)+ǫ

(y − t1 (x) − ǫ)q−1 dρx (y)

y>t2 (x)+ǫ

(y − t2 (x) − ǫ)q−1 dρx (y).

The above equalities hold if and only if ρx ({y : y < t2 (x) − ǫ}) = 0 and ρx ({y : y >
t1 (x) + ǫ}) = 0 simultaneously . Since ρx (·) is non-degenerate and supported on [− 21 , 21 ],
then the values of t1 (x) and t2 (x) must satisfy t2 (x) − ǫ ≤ − 12 and t1 (x) + ǫ ≥ 21 . By the
hypothesis t1 (x) < t2 (x), we get ǫ > 12 . This is contradict with 0 ≤ ǫ ≤ 12 . The proof is
completed.

3

Error Decomposition and Sample Error

Now we can conduct an error decomposition.
Lemma 2. Define fλ by (1.5). Let 0 ≤ ǫ ≤ 12 , then
E(π(fzǫ)) − E(fq ) + λkfzǫ k2K ≤ S1 + S2 + D(λ) + q2q−1ǫ,

(3.1)


 

S1 = E(π(fzǫ )) − E(fq ) − Ez(π(fzǫ )) − Ez (fq ) ,

 

S2 = Ez (fλ ) − Ez (fq ) − E(fλ) − E(fq ) .

(3.2)

where

(3.3)

Proof. By the same procedure in [11, 14, 15, 16], E(π(fzǫ)) −E(fq ) + λkfzǫ k2K can be expressed
as


E(π(fzǫ )) − Ez (π(fzǫ )) + [Ez (π(fzǫ )) + λkfzǫ k2K ] − [Ez (fλ ) + λkfλ k2K ]


+ Ez(fλ ) − E(fλ) + E(fλ) − E(fq ) + λkfλ k2K .

The relation (2.6) yields

Ez (π(fzǫ )) =

T
1X
ψq (π(fzǫ )(xi ) − yi )
T i=1

T
1X ǫ
ψq (π(fzǫ )(xi ) − yi ) + q(kπ(fzǫ )k∞ + |y|)q−1ǫ
≤
T i=1

≤ Ezǫ (π(fzǫ )) + q2q−1ǫ

14

(3.4)

and
Ezǫ (fλ )

T
T
1X ǫ
1X
=
ψ (fλ (xi ) − yi ) ≤
ψq (fλ (xi ) − yi ) = Ez (fλ ).
T i=1 q
T i=1

The restriction 0 ≤ ǫ ≤

1
2

(3.5)

implies Ezǫ (π(fzǫ )) ≤ Ezǫ (fzǫ ). By (3.4) and (3.5), then we have

[Ez (π(fzǫ )) + λkfzǫ k2K ] − [Ez (fλ ) + λkfλ k2K ]

≤ [Ezǫ (π(fzǫ )) + λkfzǫ k2K ] − [Ez (fλ ) + λkfλ k2K ] + q2q−1 ǫ
≤ [Ezǫ (fzǫ ) + λkfzǫ k2K ] − [Ez (fλ ) + λkfλ k2K ] + q2q−1ǫ

≤ [Ezǫ (fzǫ ) + λkfzǫ k2K ] − [Ezǫ (fλ ) + λkfλ k2K ] + q2q−1 ǫ.

Since [Ezǫ (fzǫ ) + λkfzǫ k2K ] − [Ezǫ (fλ ) + λkfλ k2K ] ≤ 0, we have
[Ez (π(fzǫ )) + λkfzǫ k2K ] − [Ez (fλ ) + λkfλ k2K ] ≤ q2q−1 ǫ.
Then the desired conclusion holds.
In the above error decomposition, the first two terms S1 and S2 are called sample error.
For the second term S2 , we get the following estimation.
Corollary 2. Assume that (2.5), there exists a subset Z1,δ of Z T with measure at least 1 − 2δ3
such that for any z ∈ Z1,δ ,

S2 ≤

1
2q+1 log 3δ
2Cθ log 3δ  2−θ
7q(1 + 5kfλ kq∞ ) log 3δ
+ D(λ).
+
+
6T
3T
T

(3.6)

Proof. we can decompose S2 into two parts S2 = S2,1 + S2,2 , where


 

S2,1 = Ez (fλ ) − Ez (π(fλ )) − E(fλ ) − E(π(fλ )) ,

 

S2,2 = Ez (π(fλ )) − Ez (fq ) − E(π(fλ)) − E(fq ) .

For S2,1 , we apply the one-side Bernstein inequality [2] to the random variable ξ(z) =
ψq (fλ (x) − y) − ψq (π(fλ )(x) − y). For the continuity of the loss ψq (u), it satisfies 0 ≤ ξ ≤
15

q−1
q(kfλ k∞ +kπ(fλ )k∞ +|y|)q−1|π(fλ )(x)−fλ (x)| ≤ q(2kfλk∞
+1)(1+kfλ k∞ ) ≤ q(1+5kfλkq∞ ).
Noting that |ξ − E(ξ)| ≤ q(1 + 5kfλ kq∞ ) and E(ξ − E(ξ))2 ≤ q(1 + 5kfλ kq∞ )E(ξ), then there
′
exists a subset Z1,δ
of Z T with measure at least 1 −

δ
3

′
such that for any z ∈ Z1,δ
,

7q(1 + 5kfλ kq∞ ) log 3δ
S2,1 ≤
+ E(fλ) − E(π(fλ )).
(3.7)
6T
For S2,2 , we take the random variable ξ(z) = ψq (π(fλ )(x) − y) − ψq (fq (x) − y) which is

bounded by 2q and estimate the variance by Lemma 1 with f = π(fλ ). Applying the oneside Bernstein inequality again, we find that there exists a subset z′′1,δ of Z T with measure
at least 1 −

δ
3

′′
such that for any z ∈ Z1,δ
,

1
2q+1 log 3δ
2Cθ log 3δ  2−θ
+ E(π(fλ )) − E(fq )
+
3T
T
Combing the bound (3.7) and (3.8), we get the desired conclusion (3.6).
p
Denote κ = supx∈X K(x, x). For R ≥ 1, let BR = {z ∈ Z T : kf kK ≤ R}.

S2,2 ≤

(3.8)

Corollary 3. Assume that (1.9) and (2.5). For any f ∈ BR , there exists a subset Z2,δ of

Z T with measure at least 1 −

S1 ≤
where

δ
3

such that for all z ∈ Z2,δ ,


1
E(π(f ) − E(fq ) + 12ε∗(R, T, δ/3)
2



1
1
3
ε∗ (R, T, δ/3) ≤ 2q+3 + (8Cθ ) 2−θ log T − 2−θ
δ
 k

1
1
q+3
k
k(q−1)
k
k(q−1) 2+k−θ
R k+1 T − 2+k−θ .
+ 2 Ck q (2 + kfq k∞ )
+ (8Cθ Ck q (2 + kfq k∞ )
)

(3.9)

Proof. Consider the function set

G = ψq (π(f )(x) − y) − ψq (fq (x) − y) : kf kK ≤ R .

A function from this set g(z) = ψq (π(f )(x)−y)−ψq (fq (x)−y) satisfies Eg ≥ 0, |g(z)| ≤ 2q and
θ
Eg 2 ≤ Cθ Eg by (2.5). The continuity of the loss implies |ψq (π(f )(x)−y)−ψq (fq (x)−y)| ≤
q(2 + kfq k∞ )q−1 |π(f )(x) − fq (x)|. Then


ε
.
N (G, ε) ≤ N B1 ,
q(2 + kfq k∞ )q−1 R
16

We apply the ratio probability inequality with the covering number in [16],



 



E(π(f ) − E(fq ) − Ez (π(f ) − Ez (fq )
1−θ/2
q
Probz∈Z
sup
≤ 4ε
θ
kf kK ≤R

E(π(f ) − E(fq ) + εθ




ε
T ε2−θ
≥ 1 − N B,
exp −
q(2 + kfq k∞ )q−1 R
2Cθ + 2q+1 ε1−θ
)
( 
k
T ε2−θ
q(2 + kfq k∞ )q−1 R
−
.
≥ 1 − exp Ck
ε
2Cθ + 2q+1 ε1−θ
We take ε∗ (R, T, δ/3) to be the positive solution to the equation
k

δ
T ε2−θ
q(2 + (kfq k∞ )R
=
log
.
−
Ck
ε
2Cθ + 2q+1 ε1−θ/2
3
It can be expressed as

2q+1
3
2Cθ
3
2q+1 Ck q k (2 + kfq k∞ )k(q−1) Rk 1−θ
log ε1+k−θ −
log εk −
ε
T
δ
T
δ
T
2Cθ Ck q k (2 + kfq k∞ )k(q−1) Rk
−
= 0.
T
The positive solution ε∗ (R, T, δ/3) to this equation can be bounded as
 1

 2q+3
3 8Cθ
3 2−θ
∗
ε (R, T, δ/3) ≤ max
,
log ,
log
T
δ
T
δ
 1 
 1
 q+3
2 Ck q k (2 + kfq k∞ )k(q−1) Rk 1+k
8Cθ Ck q k (2 + kfq k∞ )k(q−1) Rk 2+k−θ
,
.
(3.10)
T
T
ε2+k−θ −

Then there exists a subset Z2,δ of Z T with measure at least 1 − 3δ such that for all z ∈ Z2,δ ,

 

E(π(f ) − E(fq ) − Ez (π(f ) − Ez (fq )
≤ 4(ε∗ (R, T, δ/3))1−θ/2.
sup q

θ
kf kK ≤R
E(π(f ) − E(fq ) + (ε∗ (R, T, δ/3))θ
T
For any z ∈ B(R) Z2,δ , we have
q
θ
∗
1−θ/2
S1 ≤ 4(ε (R, T, δ/3))
E(π(f ) − E(fq ) + (ε∗ (R, T, δ/3))θ

θ
θ
≤ E(π(f ) − E(fq ) + (1 − )41/(1−θ/2) ε∗ (R, T, δ/3) + 4ε∗ (R, T, δ/3)
2
2

1
∗
≤ E(π(f ) − E(fq ) + 12ε (R, T, δ/3).
2
17

Putting the above bounds into (3.10), then we get the desired conclusion (3.9).

4

Estimating Total Error by Iteration

This section is devoted to estimating total error kπ(fzǫ ) − fq kLrρX . To apply Corollary 2 and
Corollary 3 for error analysis, we get the rough bound
1

kfzǫ kK ≤ λ− 2 ,

∀z ∈ Z T

by taking f = 0 in (1.4). This bound will be improved by iteration technique used in [14].
For R > 0, denote
W(R) = {z ∈ Z T : kfzǫ kK ≤ R}.
Lemma 3. Take λ = T −α , ǫ = T −η with 0 < α ≤ 1, 0 < η ≤ ∞. Let 0 < ξ < 1. If ρ satisfy
the noise condition (1.8) and (1.6), (1.9) hold, then for any 0 < δ < 1, with confidence 1 − δ,

there exists a subset VR of Z T with measure at most δ such that holds
r
q
p
p
p
2
3
3
q/2
ǫ
log T ϑ , ∀z ∈ W(R) \ V (R),
kfz kK ≤ 4A2 (1 + q2q + 2 D0 + 12qD0 + A1 ) log
ξ
δ
(4.1)
 [α(2+k−θ)−1](1+k)
q(1−β)α
α−η α(1−β) α
1 α
1
+ ξ, 2 , 2 , 2 + 4 − 2 , 2 − 2(2−θ) .
where ϑ = max
(2+k−θ)(2+k)
Proof. Applying Corollary 2 and Corollary 3 with Lemma 2, we know that for any z ∈
T
T
W(R) Z1,δ Z2,δ , R > 1,
E(π(fzǫ )) − E(fq ) + λkfzǫ k2K ≤ q2q ǫ + 4D(λ) + 12qkfλkq∞ T −1 log
1

+ A1 T − 2−θ log

1
k
3
+ A2 R k+1 T − 2+k−θ .
δ

3
δ

where A1 and A2 is given by
1

1

1

A1 = 106 + 20Cθ2−θ , A2 = 2q+4 (Ck q k (2 + kfq k∞ )k(q−1) ) 1+k + 16(Cθ Ck q k (2 + kfq k∞ )k(q−1) ) 2+k−θ .

18

Let VR be a set whose measure is at most δ. Putting λ = T −α , ǫ = T −η with 0 < α ≤ 1,
0 < η ≤ ∞ and (1.6) into the above bound, then for any R > 1 we have
k

kfzǫ kK ≤ aT R 2+2k + bT ,

z ∈ W(R) \ VR ,

where the constants aT and bT are given by
(
)
r
r
p
p
p
1
α
3
3
q/2
aT = A2 T 2 − 2(2+k−θ) , bT =
Tζ
q2q + 2 D0 + 12qD0 log + A1 log
δ
δ
with ζ = max

n

α−η α(1−β) α
, 2 ,2
2

+

q(1−β)α
4

− 12 , α2 −

1
2(2−θ)
k

o

. It follows that

W(R) ⊆ W(aT R 2+2k + bT ) ∪ VR ,
1

Let us apply the above relation iteratively to a sequence {R(j) }Jj=0 defined by R(0) = λ− 2
 k
and R(j) = aT R(j−1) 2+2k + bT where J ∈ IN will be determined later. Then W(R(j−1) ) ⊆

W(R(j) ) ∪ VR(j−1) . Noting that W(R(0) ) = Z T , then


Z T = W(R(0) ) ⊆ W(R(1) ) ∪ VR(0) ⊆ · · · W(R(J) ) ∪ ∪J−1
j=0 VR(j) .

As the measure of VR(j) is at most δ, we know that the measure of ∪J−1
j=0 VR(j) is at most Jδ.
(J)
Hence W(R ) has measure at least 1 − Jδ.
Denote ∆ =
R

k
2+2k

(J)

=

≤ 12 . The definition of the sequence {R(j) }Jj=0 implies that

2 +···+∆J −1
a1+∆+∆
T

R

 J
(0) ∆

+

J−1
X

a1+∆+∆
T

2 +···+∆j−1

j

b∆
m + bm .

j=1

The first term
2 +···+∆J −1
a1+∆+∆
T

R

 J
(0) ∆

= (A2 )
≤ A2 T

1−∆J
2(1−∆)

T

α
1
− 2(2+k−θ)
2

[α(2+k−θ)−1](1+k)
(2+k−θ)(2+k)



1

1−∆J
1−∆

α

T 2∆

J

−J

T 2+k−θ 2 .

Taking J be the smallest integer greater than or equal to log 1ξ / log 2. Then the upper bound

19

is estimated by A2 T
J−1
X

[α(2+k−θ)−1](1+k)
+ξ
(2+k−θ)(2+k)

2 +···+∆j−1 ∆j
bm
a1+∆+∆
T

j=1

≤ A2 b1 T
where b1 =
If ζ >

√

q2q

√

A2 b1 JT

[α(2+k−θ)−1](1+k)
(2+k−θ)(2+k)

+ bm ≤ A2 T

[α(2+k−θ)−1](1+k)
(2+k−θ)(2+k)

+ 2 D0 +

[α(2+k−θ)−1](1+k)
,
(2+k−θ)(2+k)

. The second term

J−1
X

T

ζ−

α
1
− 2(2+k−θ)
2



[α(2+k−θ)−1](1+k)
(2+k−θ)(2+k)

j=0

q

q/2
12qD0 log 3δ

+

1−∆j
1−∆

q
A1 log 3δ .

it is bounded by A2 b1 JT ζ . If ζ ≤



j

j

ζ∆
b∆
+ b1 mζ
1 m

kj
(2+2k)j

.

[α(2+k−θ)−1](1+k)
,
(2+k−θ)(2+k)

it is bounded by

.

Thus we have
R(J) ≤ (A2 + A2 b1 J)T ϑ ,
+ ξ, ζ}. With confidence 1 − Jδ, there holds
where ϑ = max{ [α(2+k−θ)−1](1+k)
(2+k−θ)(2+k)
kfzǫ kK

≤R

(J)

≤ A2 (1 +

p

r
q
p
p
3
q/2
q2q + 2 D0 + 12qD0 + A1 ) log JT ϑ .
δ

Noting J ≤ 2 log 3ξ , then we can get (4.1) by replacing δ by δ/J.
Now we can prove Theorem 2.

Proof of Theorem 2. By Lemma 3, there exists a subset VR′ ⊂ Z T with measure at most
δ such that Z T \ VR′ ⊆ W(R). Let R be the right side of (4.1). Applying Corollary 2 and
Corollary 3 to R, then there exists another subset VR ⊂ Z T with measure at most δ such
that

1
3
3
E(π(f )) − E(fq ) ≤ q2q ǫ + 4D(λ) + 12qkfλ kq∞ T −1 log + A1 T − 2−θ log
δ
δ
r

1
3 2
3 k
+ A3 log
log T 1+k ϑ− 2+k−θ .
ξ
δ
q
√
√
√ q
k
q/2
k+1
where A3 = A2 (4A2 ) (1 + q2 + 2 D0 + 12qD0 + A1 ). By (2.1), we obtain that

kπ(fzǫ ) − fq kLrρX ≤ C ∗ T −Λ
20

where
q/2

C ∗ = Cr q2q + 4D0 + 12qD0 + A1 + A3

1
 q+w

and Λ is given by (2). The restriction (1.12) ensures that Λ > 0. Replacing δ with δ/2, we
complete the proof of Theorem 2.
Now we are in the state of proving Theorem 1.
Proof of Theorem 1. We shall prove Theorem 1 by Theorem 2. First, we check the noise
condition (1.8). Let the function a(x) =
[0, 14 ], then

1
4

and b(x) = 22ϕ+1 , ∀x ∈ X. For s ∈ [0, a(x)] =

ρx ({y : fq (x) ≤ y ≤ fq (x) + s}) =

Z

fq (x)+s
fq (x)

dρx (y)
dy = 22ϕ+1 sϕ+1 .
dy

By similarity, ∀s ∈ [0, 41 ],
ρx ({y : fq (x) − s ≤ y ≤ fq (x)}) = 22ϕ+1 sϕ+1 .
So we say that ρ has a ∞-average type ϕ + 1.

Since fq ∈ HK and K ∈ C ∞ (X × X), then (1.6) and (1.9) hold with β = 1 and k = 0. Thus,
2
and r = q + ϕ + 1. Noting that the choice of λ and ǫ satisfy (1.12) and Λ > 0.
θ = q+ϕ+1
This complements our Theorem 1.
Proof of Corollary 1. It is an easy consequence of Theorem 2.

References
[1] D. R. Chen, Q. Wu, Y. M. Ying and D. X. Zhou, Support vector machine soft margin
classifiers: error analysis, Journal of Machine Learning Research 2 (2004) 1143–1175.
[2] L. Devroye, L. Györfi and G. Lugosi, A Probabilistic Theory of Pattern Recognition,
Springer-Verlag, New York, 1997.
[3] T. Hu, J. Fan, Q. Wu and D. X. Zhou, Regularization schemes for minimum error entropy principle, Analysis and Applications 13, 437, 2015, DOI:
10.1142/S0219530514500110.
21

[4] P. J. Huber, Robust Statistics, Wiley, 1981.
[5] T. Hu, D. H. Xiang and D. X. Zhou, Online learning for quantile regression and support
vector regression, Journal of Statistical Planning and Inference 142 (2012), 3107–3122.
[6] R. Koenker and G. Bassett, Regression quantiles, Econometrica 46 (1978), 33–50.
[7] S. Smale and D. X. Zhou, Estimating the approximation error in learning theory, Anal.
Appl. 1 (2003), 17–41.
[8] I. Steinwart, How to compare different loss functions and their risks, Constr. Approx.
26 (2007) 225–287.
[9] I. Steinwart and A. Christmann, Estimating conditional quantiles with the help of the
pinball loss, Bernoulli 17 (2011), 211–225.
[10] I. Steinwart and A. Christmann, How support vector machines can estimate quantiles
and the median, Advances in Neural Information Processing Systems 20 (2008), 305–
312.
[11] H. W. Sun and Q. Wu, Indefinite kernel network with dependent sampling, Analysis
and Applications 11 (2013), DOI: 10.1142/S0219530513500206.
[12] H. Z. Tong, D. R. Chen and L. Z. Peng, Analysis of support vector machines regression,
Found. Comput. Math. 9 (2009), 243–257.
[13] V. Vapnik, Statistical Learning Theory, Wiley, New York, 1998.
[14] Q. Wu and D. X. Zhou, Analysis of support vector machine classication, J. Comput.
Anal. Appl. 8 (2008), 99–119.
[15] Q. Wu, Y. Ying and D. X. Zhou, Learning rates of least-square regularized regression,
Foundations of Computational Mathematics 6 (2006) 171–192.
[16] Q. Wu, Y. Ying and D. X. Zhou, Multi-kernel regularized classifiers, J. Complexity. 23
(2007), 108–134.
22

[17] D. H. Xiang, T. Hu, and D. X. Zhou, Learning with varying insensitive loss, Appl. Math.
Letters 24 (2011), 2107-2109.
[18] D. H. Xiang, T. Hu, and D. X. Zhou, Approximation analysis of learning algorithms
for support vector regression and quantile regression, Journal of Applied Mathematics
2012, 2012.
[19] D. H. Xiang and D. X. Zhou, Classification with gaussians and convex loss, Journal of
Machine Learning Research 10 (2009), 1447–1468.
[20] Y. Yao, On Some Problems in the Mathematical Foundation of Learning, M.Phil. Thesis,
City Unversity of Hong Kong, 2002.
[21] T. Zhang, Covering number bounds of certain regularized linear function classes, Journal
of Machine Learning Research, 2 (2002), 527–550.
[22] D. X. Zhou, The covering number in learning theory, J. Complexity 18 (2002), 739–767.
[23] D. X. Zhou, Capacity of reproducing kernenl spaces in learning theory, IEEE Trans.
Inform. Theory. 49 (2003), 1743–1752.

23

