# A Simpler Approach to Coefficient Regularized Support Vector Machines Regression

Authors: Hongzhi Tong; Di-Rong Chen; Fenghong Yang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We consider a kind of support vector machines regression (SVMR) algorithms associated withl
q
(
1
≤
q
<
∞
) coefficient-based regularization and data-dependent hypothesis space. Compared with former literature, we provide here a simpler convergence analysis for those algorithms. The novelty of our analysis lies in the estimation of the hypothesis error, which is implemented by setting a stepping stone between the coefficient regularized SVMR and the classical SVMR. An explicit learning rate is then derived under very mild conditions.


---

## Body

## 1. Introduction

Recall the regression setting in learning theory, and letX be a compact subset of R
n, Y
⊂
[
-
M
,
M
], for some M
>
0. ρ is an unknown probability distribution endowed on Z
:
=
X
×
Y, and z
:
=
{
z
i
}
i
=
1
m
=
{
(
x
i
,
y
i
)
}
i
=
1
m
∈
Z
m is a set of samples independently drawn according to ρ. Given samples z
, the regression problem aims to find a function f
z
:
X
→
R, such that f
z
(
x
) is a satisfactory estimate of output y when a new input x is given.Support vector machines regression (SVMR) is a kind of kernel-based regression algorithms with theɛ-insensitive loss defined by V
(
y
,
t
)
=
max
⁡
{
0
,
|
y
-
t
|
-
ɛ
} for some fixed ɛ
≥
0. A function K
:
X
×
X
→
R is called a Mercer kernel if it is continuous, symmetric, and positive semidefinite; that is, for any finite set of distinct points {
x
1
,
x
2
,
…
,
x
l
}
⊂
X, the matrix (
K
(
x
i
,
x
j
)
)
i
,
j
=
1
l is positive semidefinite. The reproducing kernel Hilbert space (RKHS) H
K associated with a Mercer kernel K is defined (see [1]) to be the completion of the linear span of the set of functions {
K
x
:
=
K
(
x
,
·
)
:
x
∈
X
} with the inner product 〈
·
,
·
〉
K satisfying
(1)
〈
K
x
,
K
u
〉
K
=
K
(
x
,
u
)
,
and the reproducing property is given by
(2)
〈
K
x
,
f
〉
K
=
f
(
x
)
,
∀
x
∈
X
,
f
∈
H
K
.
Let
(3)
κ
:
=
sup
⁡
x
∈
X
K
(
x
,
x
)
<
∞
,
and then the reproducing property tells us the following:
(4)
∥
f
∥
∞
≤
κ
∥
f
∥
K
,
∀
f
∈
H
K
.The classical SVMR proposed by Vapnik and his coworkers [2, 3] is given by the following regularization scheme:
(5)
f
~
z
,
μ
:
=
arg
min
⁡
f
∈
H
K
{
E
z
(
f
)
+
μ
∥
f
∥
K
2
}
,
where E
z
(
f
)
:
=
(
1
/
m
)
∑
i
=
1
m
‍
V
(
y
i
,
f
(
x
i
)
) is the empirical error with respect to z and μ is a regularization parameter. It is well known, see for example, [4, Proposition 6.21], that the solution is of the form
(6)
f
~
z
,
μ
=
∑
i
=
1
m
‍
α
~
i
K
(
x
i
,
·
)
,
where the coefficients α
~
i are a solution of the optimization problem
(7)
maximize
∑
i
=
1
m
‍
α
i
y
i
-
ɛ
∑
i
=
1
m
‍
|
α
i
|
-
1
2
∑
i
,
j
=
1
m
‍
α
i
α
j
K
(
x
i
,
x
j
)
subject
to
|
α
i
|
≤
1
2
μ
m
∀
i
=
1,2
,
…
,
m
.Remark 1.
The equality constraint∑
i
=
1
m
‍
α
i
=
0 needed in [4, Proposition 6.21] is superfluous since we do not include an offset term b in the primal problem (5).The mathematical analysis of algorithm (5) has been well understood with various techniques in extensive literature; see, for example, [5–7]. In this paper, we are interested in a different regularized SVMR algorithm. In our setting, the regularizer is not the RKHS norm but an l
q-norm of the coefficients in the kernel ensembles.Definition 2.
For1
≤
q
<
∞, let
(8)
H
K
,
z
:
=
{
∑
i
=
1
m
‍
α
i
K
x
i
:
α
i
∈
R
,
i
=
1,2
,
…
,
m
}
,
Ω
z
(
f
)
=
inf
⁡
⁡
{
∑
i
=
1
m
‍
|
α
i
|
q
:
f
=
∑
i
=
1
m
‍
α
i
K
x
i
}
.
Then, the SVMR with l
q-coefficient regularization learning algorithm that we study in this paper takes the form
(9)
f
z
,
λ
:
=
arg
min
⁡
f
∈
H
K
,
z
{
E
z
(
f
)
+
λ
Ω
z
(
f
)
}
.Remark 3.
The regularization parameterλ in (9) may be different from μ in scheme (5), but a relationship between λ and μ will be given in Section 3 as we derive the learning rate of algorithm (9).Learning with coefficient-based regularization has attracted a considerable amount of attention in recent years, on both theoretical analysis and applications. It was pointed out in [8] that by taking q
<
2, and especially for the limit value q
=
1, the proposed minimization procedure in (9) can promote the sparsity of the solution; that is, it tends to result in a solution with a few nonzero coefficients [9]. This phenomenon has been also observed in the LASSO algorithm [10] and the literature of compressed sensing [11].However, it should be noticed that there are essential differences between the learning schemes (9) and (5). On one hand, the regularizer Ω
z
(
f
) is not a Hilbert space norm, which causes a technical difficulty for mathematical analysis. On the other hand, both hypothesis space H
K
,
z and regularizer Ω
z
(
f
) depend on samples z, and this increases the flexibility and adaptivity of algorithm (9) but causes the standard error analysis methods for scheme (5) which are not appropriate to scheme (9) any longer. To overcome these difficulties, [12] introduces a Banach space H of all functions of the form
(10)
f
(
x
)
=
∑
j
=
1
∞
‍
α
j
K
(
u
j
,
x
)
,
u
j
∈
X
,
with norm
(11)
∥
f
∥
=
inf
⁡
{
∑
j
=
1
∞
‍
|
α
j
|
:
f
=
∑
j
=
1
∞
‍
α
j
K
u
j
}
.
An error analysis framework is established and then a series of papers start to investigate the performance of kernel learning scheme with coefficient regularization (see [13–16]). In those literatures, an L
τ condition imposed on the marginal distribution of ρ on X plays a critical role in the error analysis. A probability measure ρ
X on X is said to satisfy L
τ condition if there exist some τ
>
0 and c
τ
>
0 such that
(12)
ρ
X
(
{
u
∈
X
:
|
u
-
x
|
<
r
}
)
≥
c
τ
r
τ
,
∀
x
∈
X
,
0
<
r
≤
1
.
In general, the index τ is hard to estimate. If X satisfies some regularity conditions (such as an interior cone condition) and ρ
X is uniform distribution on X, then (12) holds with τ
=
n. It leads to a low convergence rate and depends on n, the dimension of the input space X, which is often large in learning problem.In this paper, we succeed to removeL
τ condition (12) and provide a simpler error analysis for scheme (9). The novelty of our analysis is a stepping stone technique applied to bound the hypothesis error. As a result, we derive an explicit learning rate of (9) under very mild conditions.


## 2. Error Decomposition and Hypothesis Error

The main purpose of this paper is to provide a convergence analysis of the learning scheme (9). With respect to the ɛ-insensitive loss V, the prediction ability of a measurable function f is measured by the following generalization error:
(13)
E
(
f
)
:
=
∫
Z
‍
V
(
y
,
f
(
x
)
)
d
ρ
=
∫
X
‍
∫
Y
‍
V
(
y
,
f
(
x
)
)
d
ρ
(
y
∣
x
)
d
ρ
X
(
x
)
,
where ρ
X is the marginal distribution on X and ρ
(
·
∣
x
) is the conditional probability measure at x induced by ρ. Let f
* be a minimizer of E
(
f
) among all measurable functions on X. It was proved in [6] that |
f
*
(
x
)
|
≤
M
+
ɛ for almost every x
∈
X. To make full use of the feature of the target function f
*, one can introduce a projection operator, which was extensively used to the error analysis of learning algorithm; see, for example, [17, 18].Definition 4.
The projection operatorπ
=
π
M
+
ɛ is defined on the space of measurable functions f
:
X
→
R as
(14)
π
(
f
)
(
x
)
=
{
M
+
ɛ
,
if
f
(
x
)
>
M
+
ɛ
,
-
M
-
ɛ
,
if
f
(
x
)
<
-
M
-
ɛ
,
f
(
x
)
,
if
-
M
-
ɛ
≤
f
(
x
)
≤
M
+
ɛ
.It is easy to see thatV
(
y
,
π
(
f
)
(
x
)
)
≤
V
(
y
,
f
(
x
)
), so
(15)
E
(
π
(
f
)
)
≤
E
(
f
)
,
E
z
(
π
(
f
)
)
≤
E
z
(
f
)
.
We thus take π
(
f
z
,
λ
) instead of f
z
,
λ as our empirical target function and analyze the related learning rates.


### 2.1. Error Decomposition

The error decomposition is a useful approach to the error analysis for the regularized learning schemes. With sample-dependent hypothesis spaceH
K
,
z, [12] proposes a modified error decomposition with an extra hypothesis error term, by introducing a regularization function as
(16)
f
μ
:
=
arg
min
⁡
f
∈
H
K
{
E
(
f
)
+
μ
∥
f
∥
K
2
}
,
μ
>
0
.
We can conduct the error decomposition for scheme (9) with the same underlying idea of [12].Proposition 5.
Letf
z
,
λ, f
μ be defined in (9) and (16). Then,
(17)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
S
(
z
,
λ
,
μ
)
+
P
(
z
,
λ
,
μ
)
+
D
(
μ
)
.
Here,
(18)
S
(
z
,
λ
,
μ
)
:
=
{
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
}
+
{
E
z
(
f
μ
)
-
E
(
f
μ
)
}
,
P
(
z
,
λ
,
μ
)
:
=
{
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
}
-
{
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
}
,
D
(
μ
)
:
=
E
(
f
μ
)
-
E
(
f
*
)
+
μ
∥
f
μ
∥
K
2
=
inf
⁡
f
∈
H
K
{
E
(
f
)
-
E
(
f
*
)
+
μ
∥
f
∥
K
2
}
.Proof.
A direct computation shows that(19)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
+
λ
Ω
z
(
f
z
,
λ
)
=
{
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
}
+
{
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
}
+
{
E
z
(
f
μ
)
-
E
(
f
μ
)
}
-
{
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
}
+
{
E
(
f
μ
)
-
E
(
f
*
)
+
μ
∥
f
μ
∥
K
2
}
=
S
(
z
,
λ
,
μ
)
+
P
(
z
,
λ
,
μ
)
+
D
(
μ
)
.
This proves the proposition.S
(
z
,
λ
,
μ
) is usually called the sample error; it will be estimated by some concentration inequality in the next section. D
(
μ
) is independent of the sample and is often called the approximation error, the decay of D
(
μ
), as μ
→
0 characterizes the approximation ability of H
K. We will assume that, for some 0
<
β
≤
1 and c
β
>
0,
(20)
D
(
μ
)
≤
c
β
μ
β
,
∀
μ
>
0
.Remark 6.
SinceE
(
f
)
-
E
(
f
*
)
≤
∥
f
-
f
*
∥
L
ρ
X
1, D
(
μ
) concerns the approximation of f
* in L
ρ
X
1 by functions from H
K. In fact, (20) can be satisfied when f
* is in some interpolation spaces of the pair (
L
ρ
X
1
,
H
K
) (see, e.g., [19, 20]).P
(
z
,
λ
,
μ
) is called hypothesis error since the regularization function f
μ may not be in the hypothesis space H
K
,
z. The major contribution we make in this paper is to give a simpler estimation of P
(
z
,
λ
,
μ
) by a stepping stone between f
z
,
λ and f
~
z
,
μ.


### 2.2. Hypothesis Error Estimate

The solutionf
z
,
λ of scheme (9) has a representation similar to f
~
z
,
μ in scheme (5); it is reasonable to expect close relations between the two schemes. So, the latter may play roles in the analysis of the former.Theorem 7.
Letλ, μ
>
0, 1
≤
q
<
∞, and then
(21)
P
(
z
,
λ
,
μ
)
≤
m
λ
(
2
m
μ
)
q
.Proof.
Letf
~
z
,
μ
=
∑
i
=
1
m
‍
α
~
i
K
x
i be the solution to (5). By (7), we have
(22)
Ω
z
(
f
~
z
,
μ
)
≤
∑
i
=
1
m
‍
|
α
~
i
|
q
≤
m
(
2
m
μ
)
q
.
Noting that f
~
z
,
μ
∈
H
K
,
z, it can be derived from (15), (9), and (22) that
(23)
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
z
,
λ
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
~
z
,
μ
)
+
λ
Ω
z
(
f
~
z
,
μ
)
≤
E
z
(
f
~
z
,
μ
)
+
m
λ
(
2
m
μ
)
q
≤
E
z
(
f
~
z
,
μ
)
+
μ
∥
f
~
z
,
μ
∥
K
2
+
m
λ
(
2
m
μ
)
q
.
By taking f
=
f
μ in (5), one can get
(24)
E
z
(
f
~
z
,
μ
)
+
μ
∥
f
~
z
,
μ
∥
K
2
≤
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
.
Putting (24) into (23), one then has
(25)
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
+
m
λ
(
2
m
μ
)
q
.
This proves the theorem.Remark 8.
The stepping stone method was first introduced in [21] to the error analysis of linear programming SVM classifiers. This technique was also used in [22, 23] to study l
q-coefficient regularized least square regression with q
∈
[
1,2
]. While, in this paper, we extend the index q to a large range [
1
,
+
∞
), it will be helpful to improve the understanding of those coefficient-based regularized algorithms.Remark 9.
Theorem7 presents a simpler approach for estimating the hypothesis error. Different from the former literature (see, e.g., [13–16]), we conduct the estimation without imposing any assumptions on the input space X, kernel K, and marginal distribution ρ
X.


## 2.1. Error Decomposition

The error decomposition is a useful approach to the error analysis for the regularized learning schemes. With sample-dependent hypothesis spaceH
K
,
z, [12] proposes a modified error decomposition with an extra hypothesis error term, by introducing a regularization function as
(16)
f
μ
:
=
arg
min
⁡
f
∈
H
K
{
E
(
f
)
+
μ
∥
f
∥
K
2
}
,
μ
>
0
.
We can conduct the error decomposition for scheme (9) with the same underlying idea of [12].Proposition 5.
Letf
z
,
λ, f
μ be defined in (9) and (16). Then,
(17)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
S
(
z
,
λ
,
μ
)
+
P
(
z
,
λ
,
μ
)
+
D
(
μ
)
.
Here,
(18)
S
(
z
,
λ
,
μ
)
:
=
{
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
}
+
{
E
z
(
f
μ
)
-
E
(
f
μ
)
}
,
P
(
z
,
λ
,
μ
)
:
=
{
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
}
-
{
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
}
,
D
(
μ
)
:
=
E
(
f
μ
)
-
E
(
f
*
)
+
μ
∥
f
μ
∥
K
2
=
inf
⁡
f
∈
H
K
{
E
(
f
)
-
E
(
f
*
)
+
μ
∥
f
∥
K
2
}
.Proof.
A direct computation shows that(19)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
+
λ
Ω
z
(
f
z
,
λ
)
=
{
E
(
π
(
f
z
,
λ
)
)
-
E
z
(
π
(
f
z
,
λ
)
)
}
+
{
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
}
+
{
E
z
(
f
μ
)
-
E
(
f
μ
)
}
-
{
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
}
+
{
E
(
f
μ
)
-
E
(
f
*
)
+
μ
∥
f
μ
∥
K
2
}
=
S
(
z
,
λ
,
μ
)
+
P
(
z
,
λ
,
μ
)
+
D
(
μ
)
.
This proves the proposition.S
(
z
,
λ
,
μ
) is usually called the sample error; it will be estimated by some concentration inequality in the next section. D
(
μ
) is independent of the sample and is often called the approximation error, the decay of D
(
μ
), as μ
→
0 characterizes the approximation ability of H
K. We will assume that, for some 0
<
β
≤
1 and c
β
>
0,
(20)
D
(
μ
)
≤
c
β
μ
β
,
∀
μ
>
0
.Remark 6.
SinceE
(
f
)
-
E
(
f
*
)
≤
∥
f
-
f
*
∥
L
ρ
X
1, D
(
μ
) concerns the approximation of f
* in L
ρ
X
1 by functions from H
K. In fact, (20) can be satisfied when f
* is in some interpolation spaces of the pair (
L
ρ
X
1
,
H
K
) (see, e.g., [19, 20]).P
(
z
,
λ
,
μ
) is called hypothesis error since the regularization function f
μ may not be in the hypothesis space H
K
,
z. The major contribution we make in this paper is to give a simpler estimation of P
(
z
,
λ
,
μ
) by a stepping stone between f
z
,
λ and f
~
z
,
μ.


## 2.2. Hypothesis Error Estimate

The solutionf
z
,
λ of scheme (9) has a representation similar to f
~
z
,
μ in scheme (5); it is reasonable to expect close relations between the two schemes. So, the latter may play roles in the analysis of the former.Theorem 7.
Letλ, μ
>
0, 1
≤
q
<
∞, and then
(21)
P
(
z
,
λ
,
μ
)
≤
m
λ
(
2
m
μ
)
q
.Proof.
Letf
~
z
,
μ
=
∑
i
=
1
m
‍
α
~
i
K
x
i be the solution to (5). By (7), we have
(22)
Ω
z
(
f
~
z
,
μ
)
≤
∑
i
=
1
m
‍
|
α
~
i
|
q
≤
m
(
2
m
μ
)
q
.
Noting that f
~
z
,
μ
∈
H
K
,
z, it can be derived from (15), (9), and (22) that
(23)
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
z
,
λ
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
~
z
,
μ
)
+
λ
Ω
z
(
f
~
z
,
μ
)
≤
E
z
(
f
~
z
,
μ
)
+
m
λ
(
2
m
μ
)
q
≤
E
z
(
f
~
z
,
μ
)
+
μ
∥
f
~
z
,
μ
∥
K
2
+
m
λ
(
2
m
μ
)
q
.
By taking f
=
f
μ in (5), one can get
(24)
E
z
(
f
~
z
,
μ
)
+
μ
∥
f
~
z
,
μ
∥
K
2
≤
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
.
Putting (24) into (23), one then has
(25)
E
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
μ
)
+
μ
∥
f
μ
∥
K
2
+
m
λ
(
2
m
μ
)
q
.
This proves the theorem.Remark 8.
The stepping stone method was first introduced in [21] to the error analysis of linear programming SVM classifiers. This technique was also used in [22, 23] to study l
q-coefficient regularized least square regression with q
∈
[
1,2
]. While, in this paper, we extend the index q to a large range [
1
,
+
∞
), it will be helpful to improve the understanding of those coefficient-based regularized algorithms.Remark 9.
Theorem7 presents a simpler approach for estimating the hypothesis error. Different from the former literature (see, e.g., [13–16]), we conduct the estimation without imposing any assumptions on the input space X, kernel K, and marginal distribution ρ
X.


## 3. Sample Error and Learning Rate

This section is devoted to estimating the sample errorS
(
z
,
λ
,
μ
) and deriving the learning rate of algorithm (9).


### 3.1. Sample Error Estimate

We will adopt some results from the literature to estimate the sample error. To this end, we need some definitions and assumptions. For a measurable functionf
:
Z
→
R, denote E
f
:
=
∫
Z
‍
f
(
z
)
d
ρ.Definition 10.
A variance powers of the pair (
V
,
ρ
) is a number in [
0,1
] such that for any f
:
X
→
[
-
M
-
ɛ
,
M
+
ɛ
], there exists some constant c
s
>
0 satisfying
(26)
E
[
V
(
y
,
f
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
]
2
≤
c
s
[
E
(
f
)
-
E
(
f
*
)
]
s
.Equation (26) is usually called a variance-expectation condition for the pair (
V
,
ρ
). It is easy to see that (26) always holds for s
=
0 and c
s
=
4
(
M
+
ɛ
)
2. When ɛ
=
0, the target function f
* becomes the median f
ρ
,
1
/
2 of ρ (see, [6]). In this case, as it points out in [24], if ρ has a median f
ρ
,
1
/
2 of a-average type b for some a
∈
(
0
,
∞
] and b
∈
[
1
,
∞
), then (26) can be satisfied with s
=
min
⁡
{
2
/
b
,
a
/
(
a
+
1
)
}
∈
(
0,1
]. Here, we say ρ has a median f
ρ
,
1
/
2 of a-average type b if, for every x
∈
X, there exist constants c
x
∈
(
0,2
] and d
x
>
0 such that, for all v
∈
[
0
,
c
x
],
(27)
ρ
(
{
y
∈
(
f
ρ
,
1
/
2
(
x
)
-
v
,
f
ρ
,
1
/
2
(
x
)
)
∣
x
}
)
≥
d
x
v
b
-
1
,
ρ
(
{
y
∈
(
f
ρ
,
1
/
2
(
x
)
,
f
ρ
,
1
/
2
(
x
)
+
v
)
∣
x
}
)
≥
d
x
v
b
-
1
,
and that the function on X taking value (
d
x
c
x
b
-
1
)
-
1 at x
∈
X lies in L
ρ
X
a. But for ɛ
>
0, as we know, it is still open to find a meaningful condition for ρ to guarantee that (26) holds with a positive index s
>
0.Definition 11.
LetF be a class of functions on Z and let z
=
{
z
i
}
i
=
1
m
∈
Z
m. The l
2-metric d
2
,
z is defined on F by
(28)
d
2
,
z
(
f
,
g
)
:
=
{
1
m
∑
i
=
1
m
‍
|
f
(
z
i
)
-
g
(
z
i
)
|
2
}
1
/
2
,
∀
f
,
g
∈
F
.
For every η
>
0, the covering number of F with respect to d
2
,
z is
(29)
N
2
,
z
(
F
,
η
)
:
=
inf
⁡
{
l
∈
N
:
∃
{
f
i
}
i
=
1
l
such
that
F
=
⋂
i
=
1
l
{
f
∈
F
:
d
2
,
z
(
f
,
f
i
)
≤
η
}
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
F
=
⋃
i
=
1
l
{
f
∈
F
:
d
2
,
z
(
f
,
f
i
)
≤
η
}
}
.LetB
R
:
=
{
f
∈
H
K
:
∥
f
∥
K
≤
R
}. The l
2-empirical covering number of the unit ball B
1 is defined as
(30)
N
(
B
1
,
η
)
:
=
sup
⁡
m
∈
N
sup
⁡
x
∈
X
m
N
2
,
x
(
B
1
,
η
)
.
We assume that H
K satisfies the following capacity assumption.There exists an exponentp with 0
<
p
<
2 and a constant c
p
>
0 such that
(31)
log
⁡
⁡
N
(
B
1
,
η
)
≤
c
p
η
-
p
,
∀
η
>
0
.
We now set out to bound the sample error. Write S
(
z
,
λ
,
μ
) as
(32)
S
(
z
,
λ
,
μ
)
=
{
[
E
z
(
f
μ
)
-
E
z
(
f
*
)
]
-
[
E
(
f
μ
)
-
E
(
f
*
)
]
}
+
{
[
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
]
h
h
h
-
[
E
z
(
π
(
f
z
,
λ
)
)
-
E
z
(
f
*
)
]
}
=
:
S
1
(
z
,
μ
)
+
S
2
(
z
,
λ
)
.
Applying [6, Proposition 4.1], we yield the following estimation for S
1
(
z
,
μ
).Lemma 12.
For anyt
>
0, under the assumption (26), with confidence 1
-
2
e
-
t, one has
(33)
S
1
(
z
,
μ
)
≤
7
κ
t
6
m
D
(
μ
)
μ
+
8
(
M
+
ɛ
)
t
3
m
+
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
D
(
μ
)
.The estimation forS
2
(
z
,
λ
) is based on the following concentration inequality which can be found in [25].Lemma 13.
LetF be a set of measurable functions on Z, and let B
,
c
>
0, and s
∈
[
0,1
] be constants such that each f
∈
F satisfies ∥
f
∥
∞
≤
B and E
(
f
2
)
≤
c
(
E
f
)
s. If, for some A
>
0 and p
∈
(
0,2
),
(34)
sup
⁡
m
∈
N
sup
⁡
z
∈
Z
m
log
⁡
N
2
,
z
(
F
,
η
)
≤
A
η
-
p
,
∀
η
>
0
,
then there exists a constant c
p
′ depending only on p such that for any t
>
0, with probability 1
-
e
-
t, there holds
(35)
E
f
-
1
m
∑
i
=
1
m
‍
f
(
z
i
)
≤
1
2
θ
1
-
s
(
E
f
)
s
+
c
p
′
θ
+
2
(
c
t
m
)
1
/
(
2
-
s
)
+
18
B
t
m
,
∀
f
∈
F
,
where θ
=
max
⁡
⁡
{
c
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
A
/
m
)
2
/
(
4
-
2
s
+
p
s
)
,
B
(
2
-
p
)
/
(
2
+
p
)
(
A
/
m
)
2
/
(
2
+
p
)
}.We may apply Lemma13 to a set of functions F
R with R
>
0, where
(36)
F
R
:
=
{
V
(
y
,
π
(
f
)
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
:
f
∈
B
R
}
.Proposition 14.
If assumptions (26) and (31) are satisfied, then for any t
>
0, with confidence 1
-
e
-
t, there holds
(37)
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
-
[
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
]
≤
1
2
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
+
(
1
2
+
c
p
′
)
θ
R
+
2
(
c
s
t
m
)
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
t
m
for all f
∈
B
R, where
(38)
θ
R
=
max
⁡
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
R
p
m
)
2
/
(
4
-
2
s
+
p
s
)
,
h
h
h
h
h
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
R
p
m
)
2
/
(
2
+
p
)
}
.Proof.
Each functiong
∈
F
R has a form
(39)
g
(
z
)
=
V
(
y
,
π
(
f
)
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
with some f
∈
B
R. We can easily see that ∥
g
∥
∞
≤
2
(
M
+
ɛ
) and
(40)
E
g
=
E
(
π
(
f
)
)
-
E
(
f
*
)
,
1
m
∑
i
=
1
m
‍
g
(
z
i
)
=
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
.
The assumption (26) tells us that E
(
g
2
)
≤
c
(
E
g
)
s with c
=
c
s. Moreover, for any f
1
,
f
2
∈
B
R, and (
x
,
y
)
∈
Z,
(41)
|
V
(
y
,
π
(
f
1
)
(
x
)
)
-
V
(
y
,
π
(
f
2
)
(
x
)
)
|
≤
|
π
(
f
1
)
(
x
)
-
π
(
f
2
)
(
x
)
|
≤
|
f
1
(
x
)
-
f
2
(
x
)
|
,
we get
(42)
N
2
,
z
(
F
R
,
η
)
≤
N
2
,
x
(
B
R
,
η
)
=
N
2
,
x
(
B
1
,
η
R
)
.
This together with (31) implies
(43)
sup
⁡
m
∈
N
sup
⁡
z
∈
Z
m
log
⁡
N
2
,
z
(
F
R
,
η
)
≤
log
⁡
⁡
N
(
B
1
,
η
R
)
≤
c
p
R
p
η
-
p
.
Hence, all the conditions in Lemma 13 hold, and we know that, for any t
>
0, with confidence 1
-
e
-
t, there holds, for every f
∈
B
R,
(44)
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
-
[
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
]
≤
1
2
θ
R
1
-
s
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
s
+
c
p
′
θ
R
+
2
(
c
s
t
m
)
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
t
m
.
Here,
(45)
θ
R
=
max
⁡
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
R
p
m
)
2
/
(
4
-
2
s
+
p
s
)
,
h
h
h
h
h
h
h
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
R
p
m
)
2
/
(
2
+
p
)
}
.
Recall an elementary inequality
(46)
1
ι
+
1
ν
=
1
,
with
ι
,
ν
>
1
⟹
ψ
ω
≤
1
ι
ψ
ι
+
1
ν
ω
ν
,
∀
ψ
,
ω
>
0
.
Applying it with ψ
=
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
s, ω
=
θ
R
1
-
s, ι
=
1
/
s to the first term of (44), we can derive the conclusion.It remains to find a ball containingf
z
,
λ for all z
∈
Z
m.Lemma 15.
Let1
≤
q
<
∞, f
z
,
λ be defined by (9). Then, for any z
∈
Z
m, one has
(47)
∥
f
z
,
λ
∥
K
≤
κ
m
1
-
(
1
/
q
)
(
M
λ
)
1
/
q
.Proof.
For anyζ
>
0, there exists {
α
i
}
i
=
1
m
∈
R
m, such that f
z
,
λ
=
∑
i
=
1
m
‍
α
i
K
x
i and
(48)
∑
i
=
1
m
‍
|
α
i
|
q
≤
Ω
z
(
f
z
,
λ
)
+
ζ
.
Taking f
=
0 in (9), we can see that
(49)
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
z
,
λ
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
0
)
≤
M
.
It follows that
(50)
∑
i
=
1
m
‍
|
α
i
|
q
≤
M
λ
+
ζ
.
When q
>
1, by the Hölder inequality, we can see that
(51)
∥
f
z
,
λ
∥
K
=
∥
∑
i
=
1
m
‍
α
i
K
x
i
∥
K
≤
κ
∑
i
=
1
m
‍
|
α
i
|
≤
κ
m
1
-
(
1
/
q
)
{
∑
i
=
1
m
‍
|
α
i
|
q
}
1
/
q
≤
κ
m
1
-
(
1
/
q
)
{
M
λ
+
ζ
}
1
/
q
.
It is easy to check that (51) still holds for q
=
1. Let ζ
→
0; we then get the assertion.From Lemma15 and Proposition 14, we can get the following.Corollary 16.
If assumptions (26) and (31) hold, then, for any t
>
1, with confidence 1
-
e
-
t, there holds
(52)
S
2
(
z
,
λ
)
≤
1
2
[
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
]
+
C
1
t
{
(
m
p
-
(
p
/
q
)
-
1
λ
-
p
/
q
)
2
/
(
4
-
2
s
+
p
s
)
h
h
h
h
h
h
+
(
m
p
-
(
p
/
q
)
-
1
λ
-
p
/
q
)
2
/
(
2
+
p
)
+
m
1
/
(
s
-
2
)
}
,
where
(53)
C
1
:
=
(
1
2
+
c
p
′
)
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
κ
p
M
p
/
q
)
2
/
(
4
-
2
s
+
p
s
)
h
h
h
h
h
h
h
h
h
+
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
κ
p
M
p
/
q
)
2
/
(
2
+
p
)
}
+
2
c
s
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
.


### 3.2. Deriving Learning Rates

Combining the estimation in Sections2.2 and 3.1, we can derive an explicit learning rate for scheme (9) by suitably selecting the regularization parameters λ and μ.Theorem 17.
Suppose that assumptions (20), (26), and (31) are satisfied, for any 0
<
δ
<
1, by taking λ
=
m
q
-
1
μ
β
+
q, μ
=
(
1
/
m
)
min
⁡
{
2
/
(
1
+
β
)
,
2
q
/
(
(
4
-
2
s
+
p
s
)
β
q
+
2
p
(
β
+
q
)
)
}, and we have, with confidence 1
-
δ,
(54)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
C
log
⁡
3
δ
(
1
m
)
min
⁡
{
2
β
/
(
1
+
β
)
,
2
q
β
/
(
(
4
-
2
s
+
p
s
)
β
q
+
2
p
(
β
+
q
)
)
}
,
where C is a constant independent of m or δ.Proof.
Putting Theorem7, Lemma 12, Corollary 16, and assumption (20) into Proposition 5, by taking λ
=
m
q
-
1
μ
β
+
q, we find that, for any t
>
1, with confidence 1
-
3
e
-
t,
(55)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
2
{
C
1
t
[
(
m
-
1
μ
-
(
p
β
/
q
)
-
p
)
2
/
(
4
-
2
s
+
p
s
)
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
2
c
β
μ
β
+
μ
β
2
q
h
h
h
h
h
h
h
+
(
m
-
1
μ
-
(
p
β
/
q
)
-
p
)
2
/
(
2
+
p
)
+
m
1
/
(
s
-
2
)
]
h
h
h
h
+
7
κ
t
c
β
6
m
μ
(
β
-
1
)
/
2
+
8
(
M
+
ɛ
)
t
3
m
h
h
h
h
+
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
2
c
β
μ
β
+
μ
β
2
q
}
≤
C
2
t
{
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
h
h
h
h
+
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
2
+
p
)
q
h
h
h
h
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
+
(
1
m
)
1
/
(
2
-
s
)
+
μ
(
β
-
1
)
/
2
m
+
μ
β
}
.
Here, C
2
:
=
2
[
C
1
+
(
7
/
6
)
κ
c
β
+
8
(
M
+
ɛ
)
/
3
+
(
2
c
s
)
1
/
(
2
-
s
)
+
2
c
β
+
2
-
q
]. According to the choice of μ, we can easily check that
(56)
(
1
m
)
1
/
(
2
-
s
)
≤
μ
β
,
μ
(
β
-
1
)
/
2
m
≤
μ
β
,
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
2
+
p
)
q
≤
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
≤
μ
β
.
So, our theorem follows by taking C
=
5
C
2 and t
=
log
⁡
⁡
(
3
/
δ
).Remark 18.
Theorem17 provides an explicit learning rate for l
q  (
1
≤
q
<
∞
) coefficient-based regularized SVMR. This learning rate is independent of the dimension n of the input space X. We do not require the marginal distribution ρ
X and the kernel K to satisfy any additional regularity condition, such as the L
τ condition.Remark 19.
Another advantage of coefficient-based regularization scheme is its flexibility in choosing the kernel. For instance, [26, 27] consider the least square regression with indefinite kernels and an l
2-coefficient regularization, where they relax the requirement of the kernel to be only continuous and uniformly bounded bivariate function on X. It will be a very interesting topic in future work to extend the method in this paper to the indefinite kernel setting.Let us end this paper by comparing our result with the learning rate presented in [7] in a special case ɛ
=
0. To this end, we reformulate [7, Theorem 2.3] for ɛ
=
0 as follows.Proposition 20.
IfK
∈
C
∞
(
X
×
X
), f
ρ
,
1
/
2
∈
H
K, and f
ρ
,
1
/
2 is of a-average of type 2 for some a
∈
(
0
,
∞
], taking μ
=
m
-
(
a
+
1
)
/
(
a
+
2
), 0
<
ς
<
(
a
+
1
)
/
2
(
a
+
2
), then, with a
*
=
2
a
/
(
a
+
1
), for any 0
<
δ
<
1, with confidence 1
-
δ, one has
(57)
∥
π
(
f
~
z
,
μ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
C
~
1
log
⁡
⁡
3
δ
m
ς
-
(
a
+
1
)
/
2
(
a
+
2
)
,
where C
~
1 is a constant independent of m or δ.By Theorem17, we can see the following.Corollary 21.
Under the same conditions of Proposition20, for ɛ
=
0, by taking λ
=
m
(
q
-
2
a
-
3
)
/
(
a
+
2
), one has, for any 0
<
δ
<
1, with confidence 1
-
δ,
(58)
∥
π
(
f
z
,
λ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
C
~
2
log
⁡
3
δ
m
-
(
a
+
1
)
/
2
(
a
+
2
)
,
where C
~
2 is a constant independent of m or δ.Proof.
Note thatf
*
=
f
ρ
,
1
/
2 when ɛ
=
0. From [24, Theorem 2.7], we know that
(59)
∥
π
(
f
z
,
λ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
c
ρ
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
,
1
/
2
)
)
1
/
2
,
and here c
ρ is a constant independent of m or δ.
Sincef
ρ
,
1
/
2
∈
H
K, we know that (20) holds with β
=
1.  f
ρ
,
1
/
2 is a-average type 2 which implies that (26) is satisfied with s
=
a
/
(
a
+
1
). Since X
⊂
R
n and K
∈
C
∞
(
X
×
X
), we know from [28] that (31) holds true for any p
>
0. Therefore, let p
→
0; according to Theorem 17, by taking λ
=
m
q
-
1
μ
1
+
q, μ
=
m
-
(
a
+
1
)
/
(
a
+
2
), we have, for any 0
<
δ
<
1, with confidence 1
-
δ,
(60)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
,
1
/
2
)
≤
C
log
⁡
⁡
3
δ
(
1
m
)
(
a
+
1
)
/
(
a
+
2
)
.
This together with (59) proves the corollary with the constant C
~
2
=
c
ρ
C.Corollary21 shows us that the learning rate presented in Theorem 17 for l
q-coefficient regularized SVMR is faster than the one given in [7] for RKHS norm regularized learning schemes at least in the case of ɛ
=
0.


## 3.1. Sample Error Estimate

We will adopt some results from the literature to estimate the sample error. To this end, we need some definitions and assumptions. For a measurable functionf
:
Z
→
R, denote E
f
:
=
∫
Z
‍
f
(
z
)
d
ρ.Definition 10.
A variance powers of the pair (
V
,
ρ
) is a number in [
0,1
] such that for any f
:
X
→
[
-
M
-
ɛ
,
M
+
ɛ
], there exists some constant c
s
>
0 satisfying
(26)
E
[
V
(
y
,
f
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
]
2
≤
c
s
[
E
(
f
)
-
E
(
f
*
)
]
s
.Equation (26) is usually called a variance-expectation condition for the pair (
V
,
ρ
). It is easy to see that (26) always holds for s
=
0 and c
s
=
4
(
M
+
ɛ
)
2. When ɛ
=
0, the target function f
* becomes the median f
ρ
,
1
/
2 of ρ (see, [6]). In this case, as it points out in [24], if ρ has a median f
ρ
,
1
/
2 of a-average type b for some a
∈
(
0
,
∞
] and b
∈
[
1
,
∞
), then (26) can be satisfied with s
=
min
⁡
{
2
/
b
,
a
/
(
a
+
1
)
}
∈
(
0,1
]. Here, we say ρ has a median f
ρ
,
1
/
2 of a-average type b if, for every x
∈
X, there exist constants c
x
∈
(
0,2
] and d
x
>
0 such that, for all v
∈
[
0
,
c
x
],
(27)
ρ
(
{
y
∈
(
f
ρ
,
1
/
2
(
x
)
-
v
,
f
ρ
,
1
/
2
(
x
)
)
∣
x
}
)
≥
d
x
v
b
-
1
,
ρ
(
{
y
∈
(
f
ρ
,
1
/
2
(
x
)
,
f
ρ
,
1
/
2
(
x
)
+
v
)
∣
x
}
)
≥
d
x
v
b
-
1
,
and that the function on X taking value (
d
x
c
x
b
-
1
)
-
1 at x
∈
X lies in L
ρ
X
a. But for ɛ
>
0, as we know, it is still open to find a meaningful condition for ρ to guarantee that (26) holds with a positive index s
>
0.Definition 11.
LetF be a class of functions on Z and let z
=
{
z
i
}
i
=
1
m
∈
Z
m. The l
2-metric d
2
,
z is defined on F by
(28)
d
2
,
z
(
f
,
g
)
:
=
{
1
m
∑
i
=
1
m
‍
|
f
(
z
i
)
-
g
(
z
i
)
|
2
}
1
/
2
,
∀
f
,
g
∈
F
.
For every η
>
0, the covering number of F with respect to d
2
,
z is
(29)
N
2
,
z
(
F
,
η
)
:
=
inf
⁡
{
l
∈
N
:
∃
{
f
i
}
i
=
1
l
such
that
F
=
⋂
i
=
1
l
{
f
∈
F
:
d
2
,
z
(
f
,
f
i
)
≤
η
}
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
F
=
⋃
i
=
1
l
{
f
∈
F
:
d
2
,
z
(
f
,
f
i
)
≤
η
}
}
.LetB
R
:
=
{
f
∈
H
K
:
∥
f
∥
K
≤
R
}. The l
2-empirical covering number of the unit ball B
1 is defined as
(30)
N
(
B
1
,
η
)
:
=
sup
⁡
m
∈
N
sup
⁡
x
∈
X
m
N
2
,
x
(
B
1
,
η
)
.
We assume that H
K satisfies the following capacity assumption.There exists an exponentp with 0
<
p
<
2 and a constant c
p
>
0 such that
(31)
log
⁡
⁡
N
(
B
1
,
η
)
≤
c
p
η
-
p
,
∀
η
>
0
.
We now set out to bound the sample error. Write S
(
z
,
λ
,
μ
) as
(32)
S
(
z
,
λ
,
μ
)
=
{
[
E
z
(
f
μ
)
-
E
z
(
f
*
)
]
-
[
E
(
f
μ
)
-
E
(
f
*
)
]
}
+
{
[
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
]
h
h
h
-
[
E
z
(
π
(
f
z
,
λ
)
)
-
E
z
(
f
*
)
]
}
=
:
S
1
(
z
,
μ
)
+
S
2
(
z
,
λ
)
.
Applying [6, Proposition 4.1], we yield the following estimation for S
1
(
z
,
μ
).Lemma 12.
For anyt
>
0, under the assumption (26), with confidence 1
-
2
e
-
t, one has
(33)
S
1
(
z
,
μ
)
≤
7
κ
t
6
m
D
(
μ
)
μ
+
8
(
M
+
ɛ
)
t
3
m
+
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
D
(
μ
)
.The estimation forS
2
(
z
,
λ
) is based on the following concentration inequality which can be found in [25].Lemma 13.
LetF be a set of measurable functions on Z, and let B
,
c
>
0, and s
∈
[
0,1
] be constants such that each f
∈
F satisfies ∥
f
∥
∞
≤
B and E
(
f
2
)
≤
c
(
E
f
)
s. If, for some A
>
0 and p
∈
(
0,2
),
(34)
sup
⁡
m
∈
N
sup
⁡
z
∈
Z
m
log
⁡
N
2
,
z
(
F
,
η
)
≤
A
η
-
p
,
∀
η
>
0
,
then there exists a constant c
p
′ depending only on p such that for any t
>
0, with probability 1
-
e
-
t, there holds
(35)
E
f
-
1
m
∑
i
=
1
m
‍
f
(
z
i
)
≤
1
2
θ
1
-
s
(
E
f
)
s
+
c
p
′
θ
+
2
(
c
t
m
)
1
/
(
2
-
s
)
+
18
B
t
m
,
∀
f
∈
F
,
where θ
=
max
⁡
⁡
{
c
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
A
/
m
)
2
/
(
4
-
2
s
+
p
s
)
,
B
(
2
-
p
)
/
(
2
+
p
)
(
A
/
m
)
2
/
(
2
+
p
)
}.We may apply Lemma13 to a set of functions F
R with R
>
0, where
(36)
F
R
:
=
{
V
(
y
,
π
(
f
)
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
:
f
∈
B
R
}
.Proposition 14.
If assumptions (26) and (31) are satisfied, then for any t
>
0, with confidence 1
-
e
-
t, there holds
(37)
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
-
[
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
]
≤
1
2
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
+
(
1
2
+
c
p
′
)
θ
R
+
2
(
c
s
t
m
)
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
t
m
for all f
∈
B
R, where
(38)
θ
R
=
max
⁡
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
R
p
m
)
2
/
(
4
-
2
s
+
p
s
)
,
h
h
h
h
h
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
R
p
m
)
2
/
(
2
+
p
)
}
.Proof.
Each functiong
∈
F
R has a form
(39)
g
(
z
)
=
V
(
y
,
π
(
f
)
(
x
)
)
-
V
(
y
,
f
*
(
x
)
)
with some f
∈
B
R. We can easily see that ∥
g
∥
∞
≤
2
(
M
+
ɛ
) and
(40)
E
g
=
E
(
π
(
f
)
)
-
E
(
f
*
)
,
1
m
∑
i
=
1
m
‍
g
(
z
i
)
=
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
.
The assumption (26) tells us that E
(
g
2
)
≤
c
(
E
g
)
s with c
=
c
s. Moreover, for any f
1
,
f
2
∈
B
R, and (
x
,
y
)
∈
Z,
(41)
|
V
(
y
,
π
(
f
1
)
(
x
)
)
-
V
(
y
,
π
(
f
2
)
(
x
)
)
|
≤
|
π
(
f
1
)
(
x
)
-
π
(
f
2
)
(
x
)
|
≤
|
f
1
(
x
)
-
f
2
(
x
)
|
,
we get
(42)
N
2
,
z
(
F
R
,
η
)
≤
N
2
,
x
(
B
R
,
η
)
=
N
2
,
x
(
B
1
,
η
R
)
.
This together with (31) implies
(43)
sup
⁡
m
∈
N
sup
⁡
z
∈
Z
m
log
⁡
N
2
,
z
(
F
R
,
η
)
≤
log
⁡
⁡
N
(
B
1
,
η
R
)
≤
c
p
R
p
η
-
p
.
Hence, all the conditions in Lemma 13 hold, and we know that, for any t
>
0, with confidence 1
-
e
-
t, there holds, for every f
∈
B
R,
(44)
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
-
[
E
z
(
π
(
f
)
)
-
E
z
(
f
*
)
]
≤
1
2
θ
R
1
-
s
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
s
+
c
p
′
θ
R
+
2
(
c
s
t
m
)
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
t
m
.
Here,
(45)
θ
R
=
max
⁡
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
R
p
m
)
2
/
(
4
-
2
s
+
p
s
)
,
h
h
h
h
h
h
h
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
R
p
m
)
2
/
(
2
+
p
)
}
.
Recall an elementary inequality
(46)
1
ι
+
1
ν
=
1
,
with
ι
,
ν
>
1
⟹
ψ
ω
≤
1
ι
ψ
ι
+
1
ν
ω
ν
,
∀
ψ
,
ω
>
0
.
Applying it with ψ
=
[
E
(
π
(
f
)
)
-
E
(
f
*
)
]
s, ω
=
θ
R
1
-
s, ι
=
1
/
s to the first term of (44), we can derive the conclusion.It remains to find a ball containingf
z
,
λ for all z
∈
Z
m.Lemma 15.
Let1
≤
q
<
∞, f
z
,
λ be defined by (9). Then, for any z
∈
Z
m, one has
(47)
∥
f
z
,
λ
∥
K
≤
κ
m
1
-
(
1
/
q
)
(
M
λ
)
1
/
q
.Proof.
For anyζ
>
0, there exists {
α
i
}
i
=
1
m
∈
R
m, such that f
z
,
λ
=
∑
i
=
1
m
‍
α
i
K
x
i and
(48)
∑
i
=
1
m
‍
|
α
i
|
q
≤
Ω
z
(
f
z
,
λ
)
+
ζ
.
Taking f
=
0 in (9), we can see that
(49)
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
f
z
,
λ
)
+
λ
Ω
z
(
f
z
,
λ
)
≤
E
z
(
0
)
≤
M
.
It follows that
(50)
∑
i
=
1
m
‍
|
α
i
|
q
≤
M
λ
+
ζ
.
When q
>
1, by the Hölder inequality, we can see that
(51)
∥
f
z
,
λ
∥
K
=
∥
∑
i
=
1
m
‍
α
i
K
x
i
∥
K
≤
κ
∑
i
=
1
m
‍
|
α
i
|
≤
κ
m
1
-
(
1
/
q
)
{
∑
i
=
1
m
‍
|
α
i
|
q
}
1
/
q
≤
κ
m
1
-
(
1
/
q
)
{
M
λ
+
ζ
}
1
/
q
.
It is easy to check that (51) still holds for q
=
1. Let ζ
→
0; we then get the assertion.From Lemma15 and Proposition 14, we can get the following.Corollary 16.
If assumptions (26) and (31) hold, then, for any t
>
1, with confidence 1
-
e
-
t, there holds
(52)
S
2
(
z
,
λ
)
≤
1
2
[
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
]
+
C
1
t
{
(
m
p
-
(
p
/
q
)
-
1
λ
-
p
/
q
)
2
/
(
4
-
2
s
+
p
s
)
h
h
h
h
h
h
+
(
m
p
-
(
p
/
q
)
-
1
λ
-
p
/
q
)
2
/
(
2
+
p
)
+
m
1
/
(
s
-
2
)
}
,
where
(53)
C
1
:
=
(
1
2
+
c
p
′
)
{
c
s
(
2
-
p
)
/
(
4
-
2
s
+
p
s
)
(
c
p
κ
p
M
p
/
q
)
2
/
(
4
-
2
s
+
p
s
)
h
h
h
h
h
h
h
h
h
+
[
2
(
M
+
ɛ
)
]
(
2
-
p
)
/
(
2
+
p
)
(
c
p
κ
p
M
p
/
q
)
2
/
(
2
+
p
)
}
+
2
c
s
1
/
(
2
-
s
)
+
36
(
M
+
ɛ
)
.


## 3.2. Deriving Learning Rates

Combining the estimation in Sections2.2 and 3.1, we can derive an explicit learning rate for scheme (9) by suitably selecting the regularization parameters λ and μ.Theorem 17.
Suppose that assumptions (20), (26), and (31) are satisfied, for any 0
<
δ
<
1, by taking λ
=
m
q
-
1
μ
β
+
q, μ
=
(
1
/
m
)
min
⁡
{
2
/
(
1
+
β
)
,
2
q
/
(
(
4
-
2
s
+
p
s
)
β
q
+
2
p
(
β
+
q
)
)
}, and we have, with confidence 1
-
δ,
(54)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
C
log
⁡
3
δ
(
1
m
)
min
⁡
{
2
β
/
(
1
+
β
)
,
2
q
β
/
(
(
4
-
2
s
+
p
s
)
β
q
+
2
p
(
β
+
q
)
)
}
,
where C is a constant independent of m or δ.Proof.
Putting Theorem7, Lemma 12, Corollary 16, and assumption (20) into Proposition 5, by taking λ
=
m
q
-
1
μ
β
+
q, we find that, for any t
>
1, with confidence 1
-
3
e
-
t,
(55)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
*
)
≤
2
{
C
1
t
[
(
m
-
1
μ
-
(
p
β
/
q
)
-
p
)
2
/
(
4
-
2
s
+
p
s
)
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
2
c
β
μ
β
+
μ
β
2
q
h
h
h
h
h
h
h
+
(
m
-
1
μ
-
(
p
β
/
q
)
-
p
)
2
/
(
2
+
p
)
+
m
1
/
(
s
-
2
)
]
h
h
h
h
+
7
κ
t
c
β
6
m
μ
(
β
-
1
)
/
2
+
8
(
M
+
ɛ
)
t
3
m
h
h
h
h
+
(
2
c
s
t
m
)
1
/
(
2
-
s
)
+
2
c
β
μ
β
+
μ
β
2
q
}
≤
C
2
t
{
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
h
h
h
h
+
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
2
+
p
)
q
h
h
h
h
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
+
(
1
m
)
1
/
(
2
-
s
)
+
μ
(
β
-
1
)
/
2
m
+
μ
β
}
.
Here, C
2
:
=
2
[
C
1
+
(
7
/
6
)
κ
c
β
+
8
(
M
+
ɛ
)
/
3
+
(
2
c
s
)
1
/
(
2
-
s
)
+
2
c
β
+
2
-
q
]. According to the choice of μ, we can easily check that
(56)
(
1
m
)
1
/
(
2
-
s
)
≤
μ
β
,
μ
(
β
-
1
)
/
2
m
≤
μ
β
,
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
2
+
p
)
q
≤
(
1
m
q
μ
p
(
β
+
q
)
)
2
/
(
4
-
2
s
+
p
s
)
q
≤
μ
β
.
So, our theorem follows by taking C
=
5
C
2 and t
=
log
⁡
⁡
(
3
/
δ
).Remark 18.
Theorem17 provides an explicit learning rate for l
q  (
1
≤
q
<
∞
) coefficient-based regularized SVMR. This learning rate is independent of the dimension n of the input space X. We do not require the marginal distribution ρ
X and the kernel K to satisfy any additional regularity condition, such as the L
τ condition.Remark 19.
Another advantage of coefficient-based regularization scheme is its flexibility in choosing the kernel. For instance, [26, 27] consider the least square regression with indefinite kernels and an l
2-coefficient regularization, where they relax the requirement of the kernel to be only continuous and uniformly bounded bivariate function on X. It will be a very interesting topic in future work to extend the method in this paper to the indefinite kernel setting.Let us end this paper by comparing our result with the learning rate presented in [7] in a special case ɛ
=
0. To this end, we reformulate [7, Theorem 2.3] for ɛ
=
0 as follows.Proposition 20.
IfK
∈
C
∞
(
X
×
X
), f
ρ
,
1
/
2
∈
H
K, and f
ρ
,
1
/
2 is of a-average of type 2 for some a
∈
(
0
,
∞
], taking μ
=
m
-
(
a
+
1
)
/
(
a
+
2
), 0
<
ς
<
(
a
+
1
)
/
2
(
a
+
2
), then, with a
*
=
2
a
/
(
a
+
1
), for any 0
<
δ
<
1, with confidence 1
-
δ, one has
(57)
∥
π
(
f
~
z
,
μ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
C
~
1
log
⁡
⁡
3
δ
m
ς
-
(
a
+
1
)
/
2
(
a
+
2
)
,
where C
~
1 is a constant independent of m or δ.By Theorem17, we can see the following.Corollary 21.
Under the same conditions of Proposition20, for ɛ
=
0, by taking λ
=
m
(
q
-
2
a
-
3
)
/
(
a
+
2
), one has, for any 0
<
δ
<
1, with confidence 1
-
δ,
(58)
∥
π
(
f
z
,
λ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
C
~
2
log
⁡
3
δ
m
-
(
a
+
1
)
/
2
(
a
+
2
)
,
where C
~
2 is a constant independent of m or δ.Proof.
Note thatf
*
=
f
ρ
,
1
/
2 when ɛ
=
0. From [24, Theorem 2.7], we know that
(59)
∥
π
(
f
z
,
λ
)
-
f
ρ
,
1
/
2
∥
L
ρ
X
a
*
≤
c
ρ
(
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
,
1
/
2
)
)
1
/
2
,
and here c
ρ is a constant independent of m or δ.
Sincef
ρ
,
1
/
2
∈
H
K, we know that (20) holds with β
=
1.  f
ρ
,
1
/
2 is a-average type 2 which implies that (26) is satisfied with s
=
a
/
(
a
+
1
). Since X
⊂
R
n and K
∈
C
∞
(
X
×
X
), we know from [28] that (31) holds true for any p
>
0. Therefore, let p
→
0; according to Theorem 17, by taking λ
=
m
q
-
1
μ
1
+
q, μ
=
m
-
(
a
+
1
)
/
(
a
+
2
), we have, for any 0
<
δ
<
1, with confidence 1
-
δ,
(60)
E
(
π
(
f
z
,
λ
)
)
-
E
(
f
ρ
,
1
/
2
)
≤
C
log
⁡
⁡
3
δ
(
1
m
)
(
a
+
1
)
/
(
a
+
2
)
.
This together with (59) proves the corollary with the constant C
~
2
=
c
ρ
C.Corollary21 shows us that the learning rate presented in Theorem 17 for l
q-coefficient regularized SVMR is faster than the one given in [7] for RKHS norm regularized learning schemes at least in the case of ɛ
=
0.



---

*Source: 206015-2014-05-27.xml*