# Constructive Analysis for Least Squares Regression with GeneralizedK-Norm Regularization

Authors: Cheng Wang; Weilin Nie
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We introduce a constructive approach for the least squares algorithms with generalizedK-norm regularization. Different from the previous studies, a stepping-stone function is constructed with some adjustable parameters in error decomposition. It makes the analysis flexible and may be extended to other algorithms. Based on projection technique for sample error and spectral theorem for integral operator in regularization error, we finally derive a learning rate.


---

## Body

## 1. Introduction

In learning theory, we are always given a sample setz
:
=
{
z
i
}
i
=
1
m
=
{
(
x
i
,
y
i
)
}
i
=
1
m, which is drawn from a joint distribution ρ on the sample space Z
:
=
X
×
Y. Here, the input space X is a compact metric space and Y
=
R for a regression problem. For a function f obtained via some algorithm, a loss functional L
(
f
(
x
)
,
y
) is defined to measure its performance on a sample point (
x
,
y
). In regression problem, least square loss L
(
f
(
x
)
,
y
)
=
(
f
(
x
)
-
y
)
2 is most widely used. Then, we can use the generalization error to evaluate f over the whole sample space:
(1)
E
(
f
)
=
∫
Z
‍
(
f
(
x
)
-
y
)
2
d
ρ
.From [1], we know the goal function is f
ρ
=
∫
Z
‍
y
d
ρ
(
y
∣
x
), which is called the regression function, minimizing the generalization error. Since ρ is always unknown in practice, we have to find another function close to f
ρ based on the sample. The famous empirical risk minimization (ERM) algorithm is introduced in [2, 3]. To avoid overfitting, a penalty term Ω
(
f
) related to f is added into this algorithm, which is usually called regularization. While the squared K-norm regularization term is extensively studied in [4], and so forth, in this paper, we consider a more general model:
(2)
f
z
,
λ
=
arg
min
⁡
f
∈
H
K
1
m
(
f
(
x
i
)
-
y
i
)
2
+
λ
∥
f
∥
K
p
,
with some p
>
0. In this algorithm, minimization is restricted to a hypothesis space H
K which is a reproducing kernel Hilbert space (RKHS) on X. The RKHS [5] is defined as H
K
:
=
span
⁡
{
K
x
:
x
∈
X
}
¯ with K
x
(
y
)
=
K
(
x
,
y
), associated with a Mercer Kernel K
:
X
×
X
→
R which is continuous, symmetric, and positive definite. Since X is a compact metric space, Kernel K is bounded and we denote κ
=
sup
⁡
x
,
t
∈
X
K
(
x
,
t
) in the following.


## 2. Main Result

Though uniform bounded assumption was abandoned in previous work [6], we still assume
(3)
|
y
|
≤
M
almost surely for some constant M
>
0 throughout this paper for simplicity, since our analysis can be extended to the unbounded situation by choosing some different probability inequality.For the hypothesis space, a polynomial decay condition is given to control the capacity. To state this condition, we have to firstly recall covering number.Definition 1.
Let(
M
,
d
) be a pseudometric space and S
⊂
M. For ɛ
>
0, the covering number N
(
S
,
ɛ
,
d
) of the set S with respect to d is defined to be the minimal number of balls of radius ɛ whose union covers S. That is,
(4)
N
(
S
,
ɛ
,
d
)
=
min
⁡
{
n
∈
N
:
∃
{
f
i
}
i
=
1
n
⊂
M
such
that
S
⊂
⋃
i
=
1
n
‍
B
(
f
i
,
ɛ
)
}
,
where B
(
f
i
,
ɛ
)
=
{
f
∈
M
:
d
(
f
,
f
i
)
≤
ɛ
}.When metricd is chosen to be ∥
·
∥
∞, that is, d
(
f
,
g
)
=
∥
f
-
g
∥
∞, it is the classical uniform covering number. It is widely used in [4, 6–8], and so forth, and more detailed analysis can be found in [9, 10]. More recent references [11–14] use l
2-empirical covering number to obtain a sharper upper bound for the excess generalization error E
(
f
z
,
λ
)
-
E
(
f
ρ
).Definition 2.
Denote(5)
d
2
(
a
,
b
)
=
(
1
m
∑
i
=
1
m
‍
|
a
i
-
b
i
|
2
)
1
/
2
for some a
,
b
∈
R
m. For a set F of functions on X and ɛ
>
0, with notation z
=
(
z
i
)
i
=
1
m
⊂
X
m and F
|
z
=
{
(
f
(
z
i
)
)
i
=
1
m
:
f
∈
F
}, the l
2-empirical covering number of F is given by
(6)
N
2
(
F
,
ɛ
)
=
sup
⁡
m
∈
N
sup
⁡
z
∈
X
m
N
(
F
|
z
,
ɛ
,
d
2
)
.Now, we can describe the capacity condition of the hypothesis spaceH
K.Definition 3.
We say thatH
K has empirical polynomial complexity with exponent s, 0
<
s
<
2, if there exists a constant c
s
>
0 such that
(7)
log
⁡
N
2
(
B
1
(
H
K
)
,
ɛ
)
≤
c
s
ɛ
-
s
,
∀
ɛ
>
0
,
where B
R
(
H
K
)
=
{
f
∈
H
K
:
∥
f
∥
K
≤
R
} is the ball with radius R in H
K.The integral operatorL
K
:
L
ρ
X
2
→
L
ρ
X
2 defined by
(8)
L
K
f
(
x
)
=
∫
X
‍
f
(
t
)
K
(
x
,
t
)
d
ρ
X
(
t
)
is also important in learning theory and has been studied in [15]. In [1], the authors claim that, for a Mercer Kernel K, the associated L
K is a compact operator with nonincreasing positive eigenvalue sequence μ
i. And the induced fractional operator
(9)
L
K
r
f
(
x
)
=
∑
i
≥
1
‍
μ
i
r
ϕ
i
(
x
)
is well defined, for any f
=
∑
i
≥
1
‍
c
i
ϕ
i
∈
L
ρ
X
2 with orthogonal basis {
ϕ
i
}
i
≥
1 of L
ρ
X
2. In the following, we will make use of this notion in our construction analysis.We additionally introduce the projection operatorπ on the space of measurable function f
:
X
→
R:
(10)
π
(
f
(
x
)
)
=
{
M
f
(
x
)
>
M
f
(
x
)
M
≥
f
(
x
)
≥
-
M
-
M
f
(
x
)
<
-
M
.The main result is stated as follows which will be proved in Section6.Theorem 4.
Assume (3), (7) hold for sample distribution and hypothesis space H
K. The regression function satisfies f
ρ
∈
L
K
r
(
L
ρ
X
2
) for some r
>
0. f
z
,
λ is obtained from (2). Then, by choosing appropriate λ (explicit expression can be found in the proof) with confidence 1
-
δ for any 0
<
δ
<
1
/
2, we have
(11)
∥
π
(
f
z
,
λ
)
-
f
ρ
∥
ρ
2
≤
C
p
,
r
,
s
,
M
log
⁡
2
δ
m
-
2
p
ξ
/
(
2
s
+
(
s
+
2
)
p
ξ
)
for some constant C
p
,
r
,
s
,
M not depending on m or δ and
(12)
ξ
=
{
1
r
>
1
2
4
r
4
r
+
(
1
-
2
r
)
p
r
≤
1
2
.


## 3. Error Decomposition

Various error decomposition methods motivate our research, especially [7, 12, 14, 16, 17]. A general idea of error decomposition is to transform the excess generalization error E
(
f
z
,
λ
)
-
E
(
f
ρ
)
=
∥
f
z
,
λ
-
f
ρ
∥
ρ
2 (see [1] for details) to two parts, which can be bounded by some concentration inequality and approximation analysis. In our setting, let f
λ be a function to be determined in H
K; it can be expressed as
(13)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
≤
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
+
λ
∥
f
z
,
λ
∥
K
p
≤
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
+
E
z
(
π
(
f
z
,
λ
)
)
+
λ
∥
f
z
,
λ
∥
K
p
-
E
(
f
ρ
)
≤
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
+
E
z
(
f
z
,
λ
)
+
λ
∥
f
z
,
λ
∥
K
p
-
E
(
f
ρ
)
≤
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
+
E
z
(
f
λ
)
+
λ
∥
f
λ
∥
K
p
-
E
(
f
ρ
)
≤
S
1
+
S
2
+
D
(
λ
)
,
where
(14)
S
1
=
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
)
-
(
E
z
(
π
(
f
z
,
λ
)
)
-
E
z
(
f
ρ
)
)
,
S
2
=
(
E
z
(
f
λ
)
-
E
z
(
f
ρ
)
)
-
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
,
D
(
λ
)
=
E
(
f
λ
)
-
E
(
f
ρ
)
+
λ
∥
f
λ
∥
K
p
.
The first and second terms S
1 and S
2 are called sample error which will be studied in Section 5, while the third term D
(
λ
) is regularization error (or approximation error) which is our main work in this paper.It is known thatf
λ can be freely chosen in H
K which is close to f
ρ in some sense and in previous work f
λ is always naturally chosen to be the one minimizing D
(
λ
). However, we will encounter difficulties if the minimizer does not exist or the expression of the minimizer is not explicit. In this paper, we construct a special function in the form
(15)
f
λ
=
(
L
K
α
+
λ
β
I
)
-
1
L
K
α
f
ρ
with some α
,
β
>
0 to handle this problem.


## 4. Regularization Error

It is the main contribution of this section to conduct error analysis for the regularization error. Regularization error, also called approximation error, has already been studied in [18]. However, we will analyze this part of error in a different viewpoint. From [1], we know L
K is a compact self-adjoint and positive operator. By applying the spectral theorem for compact operators, we can bound a compact positive operator with its eigenvalues. Firstly, we have to introduce a useful lemma.Lemma 5.
Leta
,
b
,
c
,
d
>
0 and c
<
d; one has
(16)
a
c
a
d
+
b
≤
b
(
c
/
d
)
-
1
.Proof.
By simply taking derivative of the right-hand side with respect toa, we can find that it reaches its maximum when a
=
(
c
/
(
d
-
c
)
)
1
/
d
b
1
/
d; that is,
(17)
sup
⁡
a
>
0
a
c
a
d
+
b
=
c
d
(
c
d
-
c
)
(
c
/
d
)
-
1
b
(
c
/
d
)
-
1
.
Since (
c
/
d
)
(
c
/
(
d
-
c
)
)
(
c
/
d
)
-
1
=
r
r
(
1
-
r
)
1
-
r
<
1, where 0
<
r
=
c
/
d
<
1, the lemma is proved.Proposition 6.
Assumef
ρ
∈
L
K
r
(
L
ρ
X
2
) and (15); there holds
(18)
D
(
λ
)
≤
C
r
,
p
λ
ξ
with some constant C
r
,
p depending on r
,
p and
(19)
ξ
=
{
1
r
>
1
2
4
r
4
r
+
(
1
-
2
r
)
p
r
≤
1
2
by choosing appropriate α and β.Proof.
SinceD
(
λ
)
=
E
(
f
λ
)
-
E
(
f
ρ
)
+
λ
∥
f
λ
∥
K
p, we will analyze the two terms, respectively. Noting that E
(
f
)
-
E
(
f
ρ
)
=
∥
f
-
f
ρ
∥
ρ
2 and L
K
-
r
f
ρ
∈
L
ρ
X
2, we have
(20)
E
(
f
λ
)
-
E
(
f
ρ
)
=
∥
f
λ
-
f
ρ
∥
ρ
2
=
∥
(
(
L
K
α
+
λ
β
I
)
-
1
L
K
α
-
I
)
f
ρ
∥
ρ
2
=
λ
2
β
∥
(
L
K
α
+
λ
β
I
)
-
1
f
ρ
∥
ρ
2
≤
λ
2
β
∥
(
L
K
α
+
λ
β
I
)
-
1
L
K
r
∥
2
∥
L
K
-
r
f
ρ
∥
ρ
2
=
λ
2
β
(
sup
⁡
i
≥
1
μ
i
r
μ
i
α
+
λ
β
)
2
∥
L
K
-
r
f
ρ
∥
ρ
2
.
Recall that sup
⁡
i
≥
1
μ
i
=
∥
L
K
∥
≤
κ, combining with Lemma 5; there holds
(21)
sup
⁡
i
≥
1
μ
i
r
μ
i
α
+
λ
β
≤
{
κ
r
-
α
α
≤
r
λ
β
(
(
r
/
α
)
-
1
)
α
>
r
,
(22)
E
(
f
λ
)
-
E
(
f
ρ
)
≤
{
κ
2
(
r
-
α
)
∥
L
K
-
r
f
ρ
∥
ρ
2
λ
2
β
α
≤
r
∥
L
K
-
r
f
ρ
∥
ρ
2
λ
2
r
(
β
/
α
)
α
>
r
.
For the termλ
∥
f
λ
∥
K
p, we have the following inequality as ∥
f
∥
K
=
∥
L
K
-
1
/
2
f
∥
ρ:
(23)
∥
f
λ
∥
K
p
=
λ
∥
L
K
-
1
/
2
f
λ
∥
ρ
p
=
∥
L
K
-
1
/
2
(
L
K
α
+
λ
β
)
-
1
L
K
α
f
ρ
∥
ρ
p
≤
∥
(
L
K
α
+
λ
β
I
)
-
1
L
K
α
+
r
-
1
/
2
∥
p
∥
L
K
-
r
f
ρ
∥
ρ
p
=
∥
L
K
-
r
f
ρ
∥
ρ
p
(
sup
⁡
i
≥
1
⁡
μ
i
α
+
r
-
1
/
2
μ
i
α
+
λ
β
)
p
.
This means
(24)
λ
∥
f
λ
∥
K
p
≤
{
κ
(
r
-
1
/
2
)
p
∥
L
K
-
r
f
ρ
∥
ρ
p
λ
r
>
1
2
∥
L
K
-
r
f
ρ
∥
ρ
p
λ
(
r
-
1
/
2
)
p
(
α
/
β
)
+
1
r
≤
1
2
.
To minimize the sum of upper bounds (22) and (24) is the same to maximize the power of λ. We can choose
(25)
α
=
α
r
,
p
≤
r
,
β
=
β
r
,
p
≥
1
2
,
r
>
1
2
;
α
=
α
r
,
p
=
r
,
β
=
β
r
,
p
=
2
r
4
r
+
(
1
-
2
r
)
p
,
r
≤
1
2
.
Then,
(26)
D
(
λ
)
≤
{
(
κ
2
(
r
-
α
)
+
κ
(
r
-
1
/
2
)
p
)
×
(
∥
L
K
-
r
f
ρ
∥
ρ
2
+
∥
L
K
-
r
f
ρ
∥
ρ
p
)
λ
,
r
>
1
2
;
(
κ
2
(
r
-
α
)
+
1
)
×
(
∥
L
K
-
r
f
ρ
∥
ρ
2
+
∥
L
K
-
r
f
ρ
∥
ρ
p
)
λ
4
r
/
(
4
r
+
(
1
-
2
r
)
p
)
,
r
≤
1
2
.
This proves the result with
(27)
C
r
,
p
=
(
κ
2
(
r
-
α
)
+
κ
(
r
-
1
/
2
)
p
+
1
)
(
∥
L
K
-
r
f
ρ
∥
ρ
2
+
∥
L
K
-
r
f
ρ
∥
ρ
p
)
.Remark 7.
Another choice(28)
α
r
,
p
>
r
,
β
r
,
p
>
α
r
,
p
2
r
,
r
>
1
2
;
α
r
,
p
>
r
,
β
r
,
p
=
2
α
r
,
p
4
r
+
(
1
-
2
r
)
p
,
r
≤
1
2
can also lead to the same result except for the constants.Remark 8.
In the casep
=
2, our result turns to D
(
λ
)
≤
C
r
λ
min
⁡
{
2
r
,
1
} which is consistent with the classical one [4]. In fact, for a general p
≤
2 of interest, the bound is better than min
⁡
{
2
r
,
1
} since ξ
≥
2
r, while r
≤
1
/
2.
In [7], the authors construct a function based on the generalized Fourier expansion of f
ρ and derive that D
(
λ
)
≤
C
1
λ
2
r
/
(
r
+
2
) with some constant C
1 for any 0
<
r
≤
2. The rate is always much less than 2
r and cannot achieve 1 when 1
/
2
<
r
≤
2. On the other hand, our result is better than 2
r, while 0
<
r
<
1
/
2.
Compared with [19], we get the same rate of upper bound. There, the authors find a connection between inf
⁡
f
∈
H
K
E
(
f
)
-
E
(
f
ρ
)
+
λ
∥
f
∥
K
p and inf
⁡
f
∈
H
K
E
(
f
)
-
E
(
f
ρ
)
+
λ
∥
f
∥
K
p with different p
,
q. However, their analysis needs an existent result, while our method does not.


## 5. Sample Error

There are a vast number of literatures studying the sample error. Here, we will follow the analysis of [11]. Firstly, we should introduce the Bernstein inequality [20]. Denote E
g
=
∫
Z
‍
g
(
z
)
d
ρ, E
z
g
=
(
1
/
m
)
∑
i
=
1
m
‍
g
(
z
i
), and σ
2
(
g
)
=
E
g
2
-
(
E
g
)
2 for an integral function g on Z.Lemma 9.
Assume|
g
-
E
g
|
≤
M
g for some constant M
g almost surely. Then,
(29)
P
r
o
b
z
∈
Z
m
{
E
z
g
-
E
g
≥
ɛ
}
≤
exp
⁡
{
-
m
ɛ
2
2
(
σ
2
(
g
)
+
(
1
/
3
)
M
g
ɛ
)
}
for any ɛ
>
0.Now, we can obtain the sample error bound involvingf
λ.Proposition 10.
Assume (3), for any 0
<
δ
<
1, with confidence 1
-
(
δ
/
2
); there holds
(30)
S
2
=
(
E
z
(
f
λ
)
-
E
z
(
f
ρ
)
)
-
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
≤
32
M
2
+
3
3
m
log
⁡
⁡
2
δ
+
16
M
2
log
⁡
⁡
2
δ
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
.Proof.
Let(31)
g
λ
(
z
)
=
(
f
λ
(
x
)
-
y
)
2
-
(
f
ρ
(
x
)
-
y
)
2
=
(
f
λ
(
x
)
-
f
ρ
(
x
)
)
(
f
λ
(
x
)
+
f
ρ
(
x
)
-
2
y
)
;
we have S
2
=
E
z
g
λ
-
E
g
λ. Note that |
f
ρ
(
x
)
|
=
|
∫
Y
‍
y
d
ρ
(
y
∣
x
)
|
≤
M and
(32)
∥
f
λ
(
x
)
∥
∞
=
∥
(
L
K
α
+
λ
β
I
)
-
1
L
K
α
f
ρ
(
x
)
∥
∞
≤
∥
(
L
K
α
+
λ
β
I
)
-
1
L
K
α
∥
·
∥
f
ρ
∥
∞
=
sup
⁡
i
≥
1
μ
i
α
μ
i
α
+
λ
β
∥
f
ρ
∥
∞
≤
∥
f
ρ
∥
∞
≤
M
.
It is easy to see that
(33)
|
g
λ
(
z
)
|
=
|
f
λ
(
x
)
-
f
ρ
(
x
)
|
|
f
λ
(
x
)
+
f
ρ
(
x
)
-
2
y
|
≤
8
M
2
.
Then, |
g
λ
-
E
g
λ
|
≤
16
M
2 and
(34)
σ
2
(
g
λ
)
≤
E
g
λ
2
≤
16
M
2
∫
X
‍
(
f
λ
(
x
)
-
f
ρ
(
x
)
)
2
d
ρ
X
≤
16
M
2
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
.
By Bernstein inequality,
(35)
Pro
b
z
∈
Z
m
{
E
z
g
λ
-
E
g
λ
≥
ɛ
}
≤
exp
⁡
{
-
m
ɛ
2
2
(
σ
2
(
g
λ
)
+
(
1
/
3
)
16
M
2
ɛ
)
}
holds with M
g
=
16
M
2. Set the right-hand side to be δ
/
2; we can solve ɛ and the following bound
(36)
E
z
g
λ
-
E
g
λ
≤
32
M
2
3
m
log
⁡
2
δ
+
2
σ
2
(
g
λ
)
m
log
⁡
2
δ
≤
32
M
2
+
3
3
m
log
⁡
2
δ
+
16
M
2
log
⁡
2
δ
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
.
This proves the proposition.For the sample error termS
1, it is more difficult since it involves the function f
z
,
λ which varies, while the sample size m is different. So, we need a concentration inequality for a set of functions as in [21]. By setting τ
=
1, the inequality becomes as follows.Lemma 11.
LetF be a set of measurable functions on Z, and B
1
,
B
2
>
0 is constant such that each function f
∈
F satisfies ∥
f
∥
∞
≤
B
1 and E
(
f
2
)
≤
B
2
E
f. If for some a
>
0 and 0
<
s
<
2,
(37)
log
⁡
N
2
(
F
,
ɛ
)
≤
a
ɛ
-
s
,
∀
ɛ
>
0
,
then there exists a constant c
s
′ depending only on s such that, for any δ
>
0, with probability at least 1
-
δ, there holds
(38)
1
m
∑
i
=
1
m
‍
f
(
z
i
)
-
E
f
≤
1
2
E
f
+
c
s
′
η
′
(
a
m
)
2
/
(
2
+
s
)
+
2
B
2
+
18
B
1
m
log
⁡
1
δ
∀
f
∈
F
,
where η
′
∶
=
max
⁡
{
B
2
(
2
-
s
)
/
(
2
+
s
)
,
B
1
(
2
-
s
)
/
(
2
+
s
)
}.The result will be used to estimateS
1. We apply this lemma to the function set
(39)
G
=
{
g
π
,
f
(
z
)
=
(
f
ρ
(
x
)
-
π
(
f
(
x
)
)
)
×
(
π
(
f
(
x
)
)
+
f
ρ
(
x
)
-
2
y
)
:
f
∈
B
R
(
H
K
)
g
π
,
f
(
z
)
=
(
f
ρ
(
x
)
-
π
(
f
(
x
)
)
)
}
and have the following proposition.Proposition 12.
LetG be defined as above with some R
≥
1 satisfying ∥
f
z
,
λ
∥
K
≤
R, whose expression will be given in the next section. Assume (3) and (7) hold. Then, we have
(40)
S
1
≤
1
2
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
)
+
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
176
M
2
)
R
2
s
/
(
2
+
s
)
m
-
2
/
(
2
+
s
)
log
⁡
2
δ
for some constant c
s
′ depending only on s with confidence 1
-
(
δ
/
2
).Proof.
From definition, we know that(41)
S
1
=
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
)
-
(
E
z
(
π
(
f
z
,
λ
)
)
-
E
z
(
f
ρ
)
)
=
1
m
∑
i
=
1
m
‍
g
π
,
z
(
z
i
)
-
∫
Z
‍
g
π
,
z
(
z
)
d
ρ
,
where g
π
,
z
(
z
)
=
(
f
ρ
(
x
)
-
π
(
f
z
,
λ
(
x
)
)
)
(
f
ρ
(
x
)
+
π
(
f
z
,
λ
(
x
)
)
-
2
y
) is an element of G.
In the following, we verify the conditions forG in Lemma 11. For any function g
π
,
f
(
z
)
∈
G, it holds
(42)
|
g
π
,
f
(
z
)
|
≤
|
f
ρ
(
x
)
-
π
(
f
(
x
)
)
|
·
|
π
(
f
(
x
)
)
+
f
ρ
(
x
)
-
2
y
|
≤
8
M
2
,
E
g
π
,
f
2
≤
16
M
2
∫
X
‍
(
π
(
f
(
x
)
)
-
f
ρ
(
x
)
)
2
d
ρ
X
=
16
M
2
E
g
π
,
f
.
On the other hand, for any g
1
,
g
2
∈
G depending, respectively, on f
1
,
f
2
∈
H
K,
(43)
|
g
1
(
z
)
-
g
2
(
z
)
|
=
|
(
π
(
f
2
(
x
)
)
-
y
)
2
-
(
π
(
f
1
(
x
)
)
-
y
)
2
|
=
|
π
(
f
2
(
x
)
)
-
π
(
f
1
(
x
)
)
|
·
|
π
(
f
2
(
x
)
)
+
π
(
f
1
(
x
)
)
-
2
y
|
≤
4
M
|
π
(
f
2
(
x
)
)
-
π
(
f
1
(
x
)
)
|
≤
4
M
|
f
2
(
x
)
-
f
1
(
x
)
|
.
This means N
2
(
G
,
ɛ
)
≤
N
2
(
B
R
(
H
K
)
,
ɛ
/
4
M
) and
(44)
log
⁡
N
2
(
G
,
ɛ
)
≤
log
⁡
N
2
(
B
R
(
H
K
)
,
ɛ
4
M
)
≤
log
⁡
N
2
(
B
1
(
H
K
)
,
ɛ
4
M
R
)
≤
c
s
(
4
M
R
)
s
ɛ
-
s
.
Now, we can see from Lemma11 that, with confidence 1
-
(
δ
/
2
), there holds
(45)
S
1
≤
1
2
E
g
π
,
z
+
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
R
2
s
/
(
2
+
s
)
m
-
2
/
(
2
+
s
)
+
176
M
2
m
log
⁡
2
δ
≤
1
2
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
)
+
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
176
M
2
)
R
2
s
/
(
2
+
s
)
m
-
2
/
(
2
+
s
)
log
⁡
2
δ
.
This proves the proposition.


## 6. Total Error

Combining the regularization and sample error bounds, we can prove the main result as follows.Proof of Theorem4.
By substituting the regularization error and sample error (in the error decomposition formula) with obtained bounds in the above two sections, we have(46)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
≤
1
2
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
)
+
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
176
M
2
)
R
2
s
/
(
2
+
s
)
m
-
2
/
(
2
+
s
)
log
⁡
2
δ
+
32
M
2
+
3
3
m
log
⁡
2
δ
+
16
M
2
log
⁡
2
δ
(
E
(
f
λ
)
-
E
(
f
ρ
)
)
+
D
(
λ
)
.
Note that D
(
λ
)
=
E
(
f
λ
)
-
E
(
f
ρ
)
+
λ
∥
f
λ
∥
K
p and radius R is always larger than 1; the bound becomes
(47)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
≤
2
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
187
M
2
+
1
)
R
2
s
/
(
s
+
2
)
m
-
2
/
(
2
+
s
)
log
⁡
2
δ
+
2
(
16
M
2
+
1
)
log
⁡
2
δ
C
r
,
p
λ
ξ
,
where
(48)
ξ
=
{
1
r
>
1
2
4
r
4
r
+
(
1
-
2
r
)
p
r
≤
1
2
.
From λ
∥
f
z
,
λ
∥
K
p
≤
E
z
(
f
z
,
λ
)
+
λ
∥
f
z
,
λ
∥
K
p
≤
(
1
/
m
)
∑
i
=
1
m
‍
y
i
2
≤
M, we have the bound for the radius: R
≤
M
1
/
p
λ
-
1
/
p, and the above inequality is now
(49)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
)
≤
2
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
187
M
2
+
1
)
×
M
2
s
/
(
s
+
2
)
p
λ
-
2
s
/
(
s
+
2
)
p
m
-
2
/
(
2
+
s
)
log
⁡
2
δ
+
2
(
16
M
2
+
1
)
log
⁡
2
δ
C
r
,
p
λ
ξ
.
To balance the two terms, we choose
(50)
λ
=
m
-
2
p
/
(
2
s
+
(
s
+
2
)
p
ξ
)
and the result is proved with constant
(51)
C
p
,
r
,
s
,
M
=
2
(
c
s
′
(
16
c
s
M
s
)
2
/
(
2
+
s
)
+
187
M
2
+
1
)
M
2
s
/
(
s
+
2
)
p
+
2
(
16
M
2
+
1
)
C
r
,
p
.Remark 13.
In [11], the authors also use l
2-empirical covering number and derive an optimal rate (
1
/
m
)
min
⁡
{
2
r
,
1
}
/
(
s
+
2
). Compared with their classical rate for squared K-norm regularization, our result also can achieve the best one O
p
(
1
/
m
), while s tends to 0. Though when r
≥
1
/
2, that is, f
ρ
∈
H
K, our rate is worse than m
-
2
/
(
s
+
2
), we will get a better rate than (
1
/
m
)
2
r when r
≤
p
/
2
(
p
+
s
). Moreover, by the iteration technique [4], we can expect that the radius for f
z
,
λ is close to the upper bound of f
λ, which leads to a sharper learning rate m
-
2
ξ
2
/
(
2
r
(
1
-
2
r
)
s
+
ξ
2
(
s
+
2
)
). This is always better than m
2
r
/
(
s
+
2
) for any r
≤
1
/
2.



---

*Source: 458459-2014-07-22.xml*