# Convergence Analysis of an Empirical Eigenfunction-Based Ranking Algorithm with Truncated Sparsity

Authors: Min Xu; Qin Fang; Shaofan Wang
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We study an empirical eigenfunction-based algorithm for ranking with a data dependent hypothesis space. The space is spanned by certain empirical eigenfunctions which we select by using a
truncated parameter. We establish the representer theorem and convergence analysis of the algorithm. In particular, we show that under a mild condition, the algorithm produces a satisfactory convergence rate as well as sparse representations with respect to the empirical eigenfunctions.


---

## Body

## 1. Introduction

Motivated by various applications including problems related to information retrieval, user-preference modeling, and computational biology, the problem of ranking has recently gained much attention in machine learning (see, e.g., [1–4]). This paper proposes a kernel-based ranking algorithm to search a ranking function in a data dependent hypothesis space. The space is spanned by certain empirical eigenfunctions which we select by using a truncated parameter. The notion of empirical eigenfunctions, first studied for learning algorithms in [5], has been used to develop classification and regression algorithms which are shown to have strong learning ability [6, 7]. We will use such an idea to develop learning algorithms for ranking.


### 1.1. The Ranking Problem

The problem of ranking is distinct from both classification and regression. In ranking, one learns a real-valued function that assigns scores to instances, but the scores themselves do not matter; instead, what is important is the relative ranking of instances induced by those scores.Formally, the problem of ranking may be modeled in the framework of statistical learning theory (see, e.g., [8] for more details). Assume ρ is a Borel probability measure on Z
=
X
×
Y, where X is a compact metric space (input or instance space) and Y
=
[
0
,
M
] (output space) for some M
>
0. Let ρ
X be its marginal distribution on X and let ρ
(
·
∣
x
) be the conditional distribution on Y at given x. The learner is given a set of samples z
=
{
z
i
}
i
=
1
m
=
{
(
x
i
,
y
i
)
}
i
=
1
m
∈
Z
m drawn independently and identically according to ρ and the goal is to find a function f
z
:
X
→
R that ranks future instances with larger labels higher than those with smaller labels. In other words, x is to be ranked as preferred over x
′ if f
z
(
x
)
>
f
z
(
x
′
) and lower than x
′ if f
z
(
x
)
<
f
z
(
x
′
) (f
z
(
x
)
=
f
z
(
x
′
) indicates that there is no difference in ranking preference between the two instances). In this setting, the penalty of a ranking function f on a pair of instances (
x
,
x
′
) with corresponding labels y and y
′ can be taken to be the least squares ranking loss:
(1)
L
(
f
,
(
x
,
y
)
,
(
x
′
,
y
′
)
)
=
(
(
y
-
y
′
)
-
(
f
(
x
)
-
f
(
x
′
)
)
)
2
,
and, as a result, the quality of f can be measured by its expected ranking error:
(2)
E
(
f
)
=
∫
Z
∫
Z
(
y
-
y
′
-
(
f
(
x
)
-
f
(
x
′
)
)
)
2
d
ρ
(
x
,
y
)
d
ρ
(
x
′
,
y
′
)
.LetL
ρ
X
2 be the space of square integrable functions on X with respect to the measure d
ρ
X. Let G be the collection of target functions which are defined to be the functions minimizing the error E
(
f
) over L
ρ
X
2; that is, G
=
{
f
∈
L
ρ
X
2
:
f
=
arg
min
⁡
f
∈
L
ρ
X
2
E
(
f
)
}. It is apparent from (2) that the error of any ranking function of the form f
+
c is the same as that of f, where c
∈
R is some constant. Therefore, unlike the target function in classification or regression, the target function in ranking is not unique in general. It is easy to show that the regression function of ρ defined by
(3)
f
ρ
(
x
)
=
∫
Y
‍
y
d
ρ
(
y
∣
x
)
,
x
∈
X
is a minimizer of the error (2), which indicates that any function of the form f
ρ
+
c is also a target function. On the other hand, any target function in L
ρ
X
2 must has the form f
ρ
+
c, which can be checked from Lemma 11 in [9]. Thus we conclude that the collection G consists exactly of functions that have the form f
ρ
(
x
)
+
c with c
∈
R being an arbitrary constant; that is, G
=
{
f
∈
L
ρ
X
2
:
f
=
f
ρ
(
x
)
+
c
,
c
∈
R
}.


### 1.2. The Mercer Kernel and Empirical Eigenpair

Our algorithm is based on a Mercer kernel and we need to introduce some notions related to kernels (see [10, 11] for more details). Recall that a Mercer kernel is defined to be a symmetric continuous function K
:
X
×
X
→
R such that, for any finite subset {
x
i
}
i
=
1
l of X, the l
×
l matrix (
K
(
x
i
,
x
j
)
)
i
,
j
=
1
l is positive semidefinite. The reproducing kernel Hilbert space H
K associated with a Mercer kernel K is the Hilbert space completed by the span of {
K
x
=
K
(
·
,
x
)
:
x
∈
X
} under the norm ∥
·
∥
K induced by the inner product 〈
·
,
·
〉
K satisfying 〈
K
x
,
K
x
′
〉
K
=
K
(
x
,
x
′
). The reproducing property in H
K takes the form f
(
x
)
=
〈
f
,
K
x
〉
K for all x
∈
X, f
∈
H
K, which indicates that
(4)
∥
f
∥
∞
≤
κ
∥
f
∥
K
,
∀
f
∈
H
K
,
where κ
=
sup
⁡
x
∈
X
|
K
(
x
,
x
)
|.LetK be a Mercer kernel. The integral operator L
K
:
H
K
→
H
K given by
(5)
L
K
f
=
∫
X
∫
X
f
(
x
)
(
K
x
-
K
x
′
)
d
ρ
X
(
x
)
d
ρ
X
(
x
′
)
is introduced in [12] to analyze the following regularized ranking algorithm:
(6)
f
γ
z
=
arg
min
⁡
f
∈
H
K
{
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
f
(
x
i
)
-
f
(
x
j
)
)
)
2
00000000000
+
γ
∥
f
∥
K
2
∑
i
,
j
=
1
m
‍
}
.
This operator is compact, positive, and self-adjoint. In particular, it has at most countably many nonzero eigenvalues and all of these eigenvalues are nonnegative. Let us arrange these eigenvalues {
λ
i
} (with multiplicities) as a nonincreasing sequence tending to 0 and take an associated sequence of eigenfunctions {
ϕ
i
} to be an orthonormal basis of H
K. In the remainder of this paper, we will use a general assumption that
(7)
f
ρ
=
L
K
r
(
g
ρ
)
for
some
r
>
0
and
g
ρ
∈
H
K
,
where the power L
K
r of L
K is defined in terms of {
λ
i
} and {
ϕ
i
} by
(8)
L
K
r
(
∑
i
=
1
∞
‍
c
i
ϕ
i
)
=
∑
i
=
1
∞
‍
λ
i
r
c
i
ϕ
i
.
The assumption (7) is equivalent to f
ρ
=
∑
i
=
1
∞
‍
λ
i
r
d
i
ϕ
i, where {
d
i
} are the Fourier coefficients of g
ρ with respect to {
ϕ
i
}; that is, g
ρ
=
∑
i
=
1
∞
‍
d
i
ϕ
i. Note from (8) that the exponent r measures the decay of the coefficients {
λ
i
r
d
i
} of f
ρ with respect to the orthonormal basis {
ϕ
i
} of H
K. Thus it can be regarded as a measurement for the regularity of the regression function f
ρ.Letx
=
{
x
i
}
i
=
1
m be the unlabeled part of the samples z
=
{
(
x
i
,
y
i
)
}
i
=
1
m. An empirical version of the operator L
K with respect to x is given by
(9)
L
K
x
(
f
)
=
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
f
(
x
i
)
(
K
x
i
-
K
x
j
)
,
f
∈
H
K
.
The operator L
K
x
:
H
K
→
H
K is self-adjoint and positive with rank at most m. We denote its eigensystem to be {
(
λ
i
x
,
ϕ
i
x
)
}, where the eigenvalues {
λ
i
x
} are arranged in nonincreasing order with λ
i
x
=
0 whenever i
>
m and the corresponding eigenfunctions {
ϕ
i
x
} form an orthonormal basis of H
K. It can be proved that E
x
(
L
K
x
)
=
L
K, which means that the eigenfunctions {
ϕ
i
} can be approximated by the empirical eigenfunctions {
ϕ
i
x
}. This fact indicates that the first m eigenfunctions are reasonably promising for ranking.


### 1.3. The Computation of Empirical Eigenpair

Before proceeding further, we need to show how the empirical eigenpairs{
(
λ
i
x
,
ϕ
i
x
)
} can be found explicitly. The main difficulty here is that the kernel of L
K is not symmetric even though it is a self-adjoint operator on H
K, which makes the computations of empirical eigenfunctions relatively difficult (We refer the readers to [13] for some results on regression learning with indefinite kernels.)Denote the symmetric matrix(
K
(
x
i
,
x
j
)
)
i
,
j
=
1
m by K and define A
=
(
1
/
m
)
(
m
I
-
1
1
T
)
K and B
=
(
1
/
m
)
A
(
m
I
-
1
1
T
), where I is the mth-order unit matrix and 1
=
(
1
,
…
,
1
)
T
∈
R
m. The proofs of Lemmas 1–5 can be found in [14].Lemma 1.
Let(
λ
,
v
) be an eigenpair of B. If λ
≠
0; then (
λ
,
(
m
I
-
1
1
T
)
v
) is an eigenpair of A.It is easy to see thatB is a positive semidefinite matrix. Denote its eigenvalues as λ
~
1
x
≥
⋯
≥
λ
~
t
x
x
>
λ
~
t
x
+
1
x
=
⋯
=
λ
~
m
x
=
0 with t
x being the rank of B and the corresponding orthonormal eigenvectors as v
~
1
,
…
,
v
~
t
x
,
v
~
t
x
+
1
,
…
,
v
~
m.Lemma 2.
Let{
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
m be eigenpairs of B. Then, for 1
≤
l
≤
m, one has
(10)
L
K
x
(
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
)
=
λ
~
l
x
m
-
1
(
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
)
.Lemma 3.
Let{
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
m be eigenpairs of B. Then, for 1
≤
p, q
≤
m, one has
(11)
〈
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
p
)
j
K
x
j
,
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
q
)
j
K
x
j
〉
K
=
m
2
δ
p
,
q
λ
~
q
x
.It follows from Lemmas2 and 3 that the numbers {
λ
~
l
x
/
(
m
-
1
)
}
l
=
1
t
x are eigenvalues of the operator L
K
x and the functions {
(
m
λ
~
l
x
)
-
1
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
}
l
=
1
t
x are the corresponding orthonormal eigenfunctions. Moreover, we have d
x
≥
t
x, where d
x denotes the rank of L
K
x.Lemma 4.
Let{
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
m be eigenpairs of L
K
x. Then, for 1
≤
l
≤
m, one has
(12)
B
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
=
(
m
-
1
)
λ
l
x
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
,
where ϕ
l
x
|
x is the vector in R
m obtained by restricting the function ϕ
l
x onto the sampling points.Lemma 5.
Let{
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
m be eigenpairs of L
K
x. Then, for 1
≤
p, q
≤
m, one has
(13)
〈
(
m
I
-
1
1
T
)
ϕ
p
x
|
x
,
(
m
I
-
1
1
T
)
ϕ
q
x
|
x
〉
l
2
=
m
2
(
m
-
1
)
δ
p
,
q
λ
p
x
.By using Lemmas4 and 5, we come to a conclusion that the numbers {
(
m
-
1
)
λ
l
x
}
l
=
1
d
x are eigenvalues of the matrix B, the vectors {
(
m
(
m
-
1
)
λ
p
x
)
-
1
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
}
l
=
1
d
x are corresponding orthonormal eigenvectors, and d
x
≤
t
x.Based on the above arguments, we are now confident that the following theorem can be proved, which yields a method for computing the empirical eigenpairs{
(
λ
i
x
,
ϕ
i
x
)
}
l
=
1
d
x explicitly.Theorem 6.
The number of positive eigenvalues ofL
K
x is equal to that of B. Moreover, the empirical eigenpairs {
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
d
x of L
K
x can be computed by using the eigenpairs {
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
d
x of B as follows:
(14)
λ
l
x
=
λ
~
l
x
m
-
1
,
ϕ
l
x
=
(
m
λ
~
l
x
)
-
1
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
,
for l
=
1
,
…
,
d
x with d
x denoting the rank of L
K
x.


### 1.4. The Ranking Algorithm

Prompted by the above analysis, we propose a learning algorithm for ranking as follows. Letϵ be a positive number (called a truncated parameter) and let D
m
,
ϵ denote the set of empirical eigenfunctions such that their corresponding eigenvalues are less than or equal to ϵ; that is, D
m
,
ϵ
=
{
ϕ
i
x
:
1
≤
i
≤
m
,
λ
i
x
≥
ϵ
}. Let s be the number of eigenfunctions in D
m
,
ϵ. Our ranking algorithm now takes the form
(15)
c
ϵ
z
=
arg
min
⁡
c
∈
R
s
{
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2

1
m
2
∑
i
,
j
=
1
m
‍

(
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
y
i
-
y
j
000000000000000000
-
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)

-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2

}
,
and the output function is
(16)
f
ϵ
z
=
∑
l
=
1
s
‍
c
ϵ
,
l
z
ϕ
l
x
.We are concerned in this paper with the representer theorem, that is, the explicit solution to problem (15), and the convergence analysis in the H
K-norm of the above algorithm. Previous work on error analysis of ranking algorithms, such as [3, 8], deals only with generalization properties of the algorithms. Though convergence analysis of classification and regression algorithms has been well studied (see, e.g., [15, 16]), little research has been conducted in establishing similar results in the setting of ranking. Perhaps the first work is that of Chen [12], who derives the convergence rate of a regularized ranking algorithm by means of the technique of operator approximation. Our results can be considered as another attempt in this direction. It should be pointed out that, for the sake of simplicity, rather than taking all target functions into consideration, we will here restrict ourselves to the regression function f
ρ. In other words, we will consider the convergence bounds for ∥
f
ϵ
z
-
f
ρ
∥
K, instead of inf
⁡
f
∈
G
∥
f
ϵ
z
-
f
∥
K.Notice that, compared with classification or regression problems, the main difference in the formulation of ranking problems is that its performance or loss is measured on pairs of examples, rather than on individual examples. This results in the double-index summation in algorithm (15), which prevents us from directly applying the standard Hoeffding inequality used to obtain convergence bounds for classification and regression. We will tackle this problem by a McDiarmid-Bernstein type probability inequality for vector-valued random variables [17] as is done in [8, 12]. Finally, we show that when the eigenvalues decay polynomially, the algorithm produces sparse representations with respect to the empirical eigenfunctions by choosing a suitable parameter ϵ.


## 1.1. The Ranking Problem

The problem of ranking is distinct from both classification and regression. In ranking, one learns a real-valued function that assigns scores to instances, but the scores themselves do not matter; instead, what is important is the relative ranking of instances induced by those scores.Formally, the problem of ranking may be modeled in the framework of statistical learning theory (see, e.g., [8] for more details). Assume ρ is a Borel probability measure on Z
=
X
×
Y, where X is a compact metric space (input or instance space) and Y
=
[
0
,
M
] (output space) for some M
>
0. Let ρ
X be its marginal distribution on X and let ρ
(
·
∣
x
) be the conditional distribution on Y at given x. The learner is given a set of samples z
=
{
z
i
}
i
=
1
m
=
{
(
x
i
,
y
i
)
}
i
=
1
m
∈
Z
m drawn independently and identically according to ρ and the goal is to find a function f
z
:
X
→
R that ranks future instances with larger labels higher than those with smaller labels. In other words, x is to be ranked as preferred over x
′ if f
z
(
x
)
>
f
z
(
x
′
) and lower than x
′ if f
z
(
x
)
<
f
z
(
x
′
) (f
z
(
x
)
=
f
z
(
x
′
) indicates that there is no difference in ranking preference between the two instances). In this setting, the penalty of a ranking function f on a pair of instances (
x
,
x
′
) with corresponding labels y and y
′ can be taken to be the least squares ranking loss:
(1)
L
(
f
,
(
x
,
y
)
,
(
x
′
,
y
′
)
)
=
(
(
y
-
y
′
)
-
(
f
(
x
)
-
f
(
x
′
)
)
)
2
,
and, as a result, the quality of f can be measured by its expected ranking error:
(2)
E
(
f
)
=
∫
Z
∫
Z
(
y
-
y
′
-
(
f
(
x
)
-
f
(
x
′
)
)
)
2
d
ρ
(
x
,
y
)
d
ρ
(
x
′
,
y
′
)
.LetL
ρ
X
2 be the space of square integrable functions on X with respect to the measure d
ρ
X. Let G be the collection of target functions which are defined to be the functions minimizing the error E
(
f
) over L
ρ
X
2; that is, G
=
{
f
∈
L
ρ
X
2
:
f
=
arg
min
⁡
f
∈
L
ρ
X
2
E
(
f
)
}. It is apparent from (2) that the error of any ranking function of the form f
+
c is the same as that of f, where c
∈
R is some constant. Therefore, unlike the target function in classification or regression, the target function in ranking is not unique in general. It is easy to show that the regression function of ρ defined by
(3)
f
ρ
(
x
)
=
∫
Y
‍
y
d
ρ
(
y
∣
x
)
,
x
∈
X
is a minimizer of the error (2), which indicates that any function of the form f
ρ
+
c is also a target function. On the other hand, any target function in L
ρ
X
2 must has the form f
ρ
+
c, which can be checked from Lemma 11 in [9]. Thus we conclude that the collection G consists exactly of functions that have the form f
ρ
(
x
)
+
c with c
∈
R being an arbitrary constant; that is, G
=
{
f
∈
L
ρ
X
2
:
f
=
f
ρ
(
x
)
+
c
,
c
∈
R
}.


## 1.2. The Mercer Kernel and Empirical Eigenpair

Our algorithm is based on a Mercer kernel and we need to introduce some notions related to kernels (see [10, 11] for more details). Recall that a Mercer kernel is defined to be a symmetric continuous function K
:
X
×
X
→
R such that, for any finite subset {
x
i
}
i
=
1
l of X, the l
×
l matrix (
K
(
x
i
,
x
j
)
)
i
,
j
=
1
l is positive semidefinite. The reproducing kernel Hilbert space H
K associated with a Mercer kernel K is the Hilbert space completed by the span of {
K
x
=
K
(
·
,
x
)
:
x
∈
X
} under the norm ∥
·
∥
K induced by the inner product 〈
·
,
·
〉
K satisfying 〈
K
x
,
K
x
′
〉
K
=
K
(
x
,
x
′
). The reproducing property in H
K takes the form f
(
x
)
=
〈
f
,
K
x
〉
K for all x
∈
X, f
∈
H
K, which indicates that
(4)
∥
f
∥
∞
≤
κ
∥
f
∥
K
,
∀
f
∈
H
K
,
where κ
=
sup
⁡
x
∈
X
|
K
(
x
,
x
)
|.LetK be a Mercer kernel. The integral operator L
K
:
H
K
→
H
K given by
(5)
L
K
f
=
∫
X
∫
X
f
(
x
)
(
K
x
-
K
x
′
)
d
ρ
X
(
x
)
d
ρ
X
(
x
′
)
is introduced in [12] to analyze the following regularized ranking algorithm:
(6)
f
γ
z
=
arg
min
⁡
f
∈
H
K
{
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
f
(
x
i
)
-
f
(
x
j
)
)
)
2
00000000000
+
γ
∥
f
∥
K
2
∑
i
,
j
=
1
m
‍
}
.
This operator is compact, positive, and self-adjoint. In particular, it has at most countably many nonzero eigenvalues and all of these eigenvalues are nonnegative. Let us arrange these eigenvalues {
λ
i
} (with multiplicities) as a nonincreasing sequence tending to 0 and take an associated sequence of eigenfunctions {
ϕ
i
} to be an orthonormal basis of H
K. In the remainder of this paper, we will use a general assumption that
(7)
f
ρ
=
L
K
r
(
g
ρ
)
for
some
r
>
0
and
g
ρ
∈
H
K
,
where the power L
K
r of L
K is defined in terms of {
λ
i
} and {
ϕ
i
} by
(8)
L
K
r
(
∑
i
=
1
∞
‍
c
i
ϕ
i
)
=
∑
i
=
1
∞
‍
λ
i
r
c
i
ϕ
i
.
The assumption (7) is equivalent to f
ρ
=
∑
i
=
1
∞
‍
λ
i
r
d
i
ϕ
i, where {
d
i
} are the Fourier coefficients of g
ρ with respect to {
ϕ
i
}; that is, g
ρ
=
∑
i
=
1
∞
‍
d
i
ϕ
i. Note from (8) that the exponent r measures the decay of the coefficients {
λ
i
r
d
i
} of f
ρ with respect to the orthonormal basis {
ϕ
i
} of H
K. Thus it can be regarded as a measurement for the regularity of the regression function f
ρ.Letx
=
{
x
i
}
i
=
1
m be the unlabeled part of the samples z
=
{
(
x
i
,
y
i
)
}
i
=
1
m. An empirical version of the operator L
K with respect to x is given by
(9)
L
K
x
(
f
)
=
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
f
(
x
i
)
(
K
x
i
-
K
x
j
)
,
f
∈
H
K
.
The operator L
K
x
:
H
K
→
H
K is self-adjoint and positive with rank at most m. We denote its eigensystem to be {
(
λ
i
x
,
ϕ
i
x
)
}, where the eigenvalues {
λ
i
x
} are arranged in nonincreasing order with λ
i
x
=
0 whenever i
>
m and the corresponding eigenfunctions {
ϕ
i
x
} form an orthonormal basis of H
K. It can be proved that E
x
(
L
K
x
)
=
L
K, which means that the eigenfunctions {
ϕ
i
} can be approximated by the empirical eigenfunctions {
ϕ
i
x
}. This fact indicates that the first m eigenfunctions are reasonably promising for ranking.


## 1.3. The Computation of Empirical Eigenpair

Before proceeding further, we need to show how the empirical eigenpairs{
(
λ
i
x
,
ϕ
i
x
)
} can be found explicitly. The main difficulty here is that the kernel of L
K is not symmetric even though it is a self-adjoint operator on H
K, which makes the computations of empirical eigenfunctions relatively difficult (We refer the readers to [13] for some results on regression learning with indefinite kernels.)Denote the symmetric matrix(
K
(
x
i
,
x
j
)
)
i
,
j
=
1
m by K and define A
=
(
1
/
m
)
(
m
I
-
1
1
T
)
K and B
=
(
1
/
m
)
A
(
m
I
-
1
1
T
), where I is the mth-order unit matrix and 1
=
(
1
,
…
,
1
)
T
∈
R
m. The proofs of Lemmas 1–5 can be found in [14].Lemma 1.
Let(
λ
,
v
) be an eigenpair of B. If λ
≠
0; then (
λ
,
(
m
I
-
1
1
T
)
v
) is an eigenpair of A.It is easy to see thatB is a positive semidefinite matrix. Denote its eigenvalues as λ
~
1
x
≥
⋯
≥
λ
~
t
x
x
>
λ
~
t
x
+
1
x
=
⋯
=
λ
~
m
x
=
0 with t
x being the rank of B and the corresponding orthonormal eigenvectors as v
~
1
,
…
,
v
~
t
x
,
v
~
t
x
+
1
,
…
,
v
~
m.Lemma 2.
Let{
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
m be eigenpairs of B. Then, for 1
≤
l
≤
m, one has
(10)
L
K
x
(
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
)
=
λ
~
l
x
m
-
1
(
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
)
.Lemma 3.
Let{
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
m be eigenpairs of B. Then, for 1
≤
p, q
≤
m, one has
(11)
〈
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
p
)
j
K
x
j
,
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
q
)
j
K
x
j
〉
K
=
m
2
δ
p
,
q
λ
~
q
x
.It follows from Lemmas2 and 3 that the numbers {
λ
~
l
x
/
(
m
-
1
)
}
l
=
1
t
x are eigenvalues of the operator L
K
x and the functions {
(
m
λ
~
l
x
)
-
1
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
}
l
=
1
t
x are the corresponding orthonormal eigenfunctions. Moreover, we have d
x
≥
t
x, where d
x denotes the rank of L
K
x.Lemma 4.
Let{
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
m be eigenpairs of L
K
x. Then, for 1
≤
l
≤
m, one has
(12)
B
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
=
(
m
-
1
)
λ
l
x
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
,
where ϕ
l
x
|
x is the vector in R
m obtained by restricting the function ϕ
l
x onto the sampling points.Lemma 5.
Let{
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
m be eigenpairs of L
K
x. Then, for 1
≤
p, q
≤
m, one has
(13)
〈
(
m
I
-
1
1
T
)
ϕ
p
x
|
x
,
(
m
I
-
1
1
T
)
ϕ
q
x
|
x
〉
l
2
=
m
2
(
m
-
1
)
δ
p
,
q
λ
p
x
.By using Lemmas4 and 5, we come to a conclusion that the numbers {
(
m
-
1
)
λ
l
x
}
l
=
1
d
x are eigenvalues of the matrix B, the vectors {
(
m
(
m
-
1
)
λ
p
x
)
-
1
(
m
I
-
1
1
T
)
ϕ
l
x
|
x
}
l
=
1
d
x are corresponding orthonormal eigenvectors, and d
x
≤
t
x.Based on the above arguments, we are now confident that the following theorem can be proved, which yields a method for computing the empirical eigenpairs{
(
λ
i
x
,
ϕ
i
x
)
}
l
=
1
d
x explicitly.Theorem 6.
The number of positive eigenvalues ofL
K
x is equal to that of B. Moreover, the empirical eigenpairs {
(
λ
l
x
,
ϕ
l
x
)
}
l
=
1
d
x of L
K
x can be computed by using the eigenpairs {
(
λ
~
l
x
,
v
~
l
)
}
l
=
1
d
x of B as follows:
(14)
λ
l
x
=
λ
~
l
x
m
-
1
,
ϕ
l
x
=
(
m
λ
~
l
x
)
-
1
∑
j
=
1
m
‍
(
(
m
I
-
1
1
T
)
v
~
l
)
j
K
x
j
,
for l
=
1
,
…
,
d
x with d
x denoting the rank of L
K
x.


## 1.4. The Ranking Algorithm

Prompted by the above analysis, we propose a learning algorithm for ranking as follows. Letϵ be a positive number (called a truncated parameter) and let D
m
,
ϵ denote the set of empirical eigenfunctions such that their corresponding eigenvalues are less than or equal to ϵ; that is, D
m
,
ϵ
=
{
ϕ
i
x
:
1
≤
i
≤
m
,
λ
i
x
≥
ϵ
}. Let s be the number of eigenfunctions in D
m
,
ϵ. Our ranking algorithm now takes the form
(15)
c
ϵ
z
=
arg
min
⁡
c
∈
R
s
{
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2

1
m
2
∑
i
,
j
=
1
m
‍

(
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
y
i
-
y
j
000000000000000000
-
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)

-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2

}
,
and the output function is
(16)
f
ϵ
z
=
∑
l
=
1
s
‍
c
ϵ
,
l
z
ϕ
l
x
.We are concerned in this paper with the representer theorem, that is, the explicit solution to problem (15), and the convergence analysis in the H
K-norm of the above algorithm. Previous work on error analysis of ranking algorithms, such as [3, 8], deals only with generalization properties of the algorithms. Though convergence analysis of classification and regression algorithms has been well studied (see, e.g., [15, 16]), little research has been conducted in establishing similar results in the setting of ranking. Perhaps the first work is that of Chen [12], who derives the convergence rate of a regularized ranking algorithm by means of the technique of operator approximation. Our results can be considered as another attempt in this direction. It should be pointed out that, for the sake of simplicity, rather than taking all target functions into consideration, we will here restrict ourselves to the regression function f
ρ. In other words, we will consider the convergence bounds for ∥
f
ϵ
z
-
f
ρ
∥
K, instead of inf
⁡
f
∈
G
∥
f
ϵ
z
-
f
∥
K.Notice that, compared with classification or regression problems, the main difference in the formulation of ranking problems is that its performance or loss is measured on pairs of examples, rather than on individual examples. This results in the double-index summation in algorithm (15), which prevents us from directly applying the standard Hoeffding inequality used to obtain convergence bounds for classification and regression. We will tackle this problem by a McDiarmid-Bernstein type probability inequality for vector-valued random variables [17] as is done in [8, 12]. Finally, we show that when the eigenvalues decay polynomially, the algorithm produces sparse representations with respect to the empirical eigenfunctions by choosing a suitable parameter ϵ.


## 2. The Representer Theorem

In this section we provide the representer theorem for algorithm (15). The key point in proving the representer theorem is an equality involving the empirical eigenfunctions and eigenvalues.Theorem 7.
The solution to problem (15) is given by
(17)
c
ϵ
,
l
z
=
S
l
z
2
m
(
m
-
1
)
λ
l
x
,
1
≤
l
≤
s
,
where S
l
z
=
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
(
ϕ
l
x
(
x
i
)
-
ϕ
l
x
(
x
j
)
).Proof.
The empirical error part takes the form(18)
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2
=
1
m
2
∑
i
,
j
=
1
m
‍
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
2
-
2
m
2
∑
l
=
1
s
‍
c
l
S
l
z
+
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
2
=
2
m
2
∑
p
,
q
=
1
s
‍
c
p
c
q
∑
i
,
j
=
1
m
‍
ϕ
p
x
(
x
i
)
(
ϕ
q
x
(
x
i
)
-
ϕ
q
x
(
x
j
)
)
-
2
m
2
∑
l
=
1
s
‍
c
l
S
l
z
+
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
2
.
A routine computation gives rise to
(19)
∑
i
,
j
=
1
m
‍
ϕ
p
x
(
x
i
)
(
ϕ
q
x
(
x
i
)
-
ϕ
q
x
(
x
j
)
)
=
m
(
m
-
1
)
δ
p
,
q
λ
p
x
.
By using (19), one can carry on with the above equality chain as follows:
(20)
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
i
)
-
∑
l
=
1
s
‍
c
l
ϕ
l
x
(
x
j
)
)
)
2
=
2
(
m
-
1
)
m
∑
p
,
q
=
1
s
‍
c
p
c
q
δ
p
,
q
λ
p
x
-
2
m
2
∑
l
=
1
s
‍
c
l
S
l
z
+
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
2
=
2
(
m
-
1
)
m
∑
l
=
1
s
‍
c
l
2
λ
l
x
-
2
m
2
∑
l
=
1
s
‍
c
l
S
l
z
+
1
m
2
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
2
.
Hence we have an equivalent form of (15) as
(21)
c
ϵ
z
=
arg
min
⁡
c
∈
R
s
∑
l
=
1
s
‍
{
c
l
2
-
1
m
(
m
-
1
)
S
l
z
λ
l
x
c
l
}
.
The component c
ϵ
,
l
z can be found by solving the following optimization problem:
(22)
c
ϵ
,
l
z
=
arg
min
⁡
c
∈
R
{
c
l
2
-
1
m
(
m
-
1
)
S
l
z
λ
l
x
c
l
}
,
which has the solution given by (17). This proves the theorem.


## 3. The Error Analysis

In order to derive an error bound for algorithm (15), we need some preliminary inequalities. The following Hoffman-Wielandt inequality establishes the relationship between λ
i
-
λ
i
x and L
K
-
L
K
x, which has been investigated in [18–21].Lemma 8.
One has(23)
∑
l
=
1
∞
‍
(
λ
l
-
λ
l
x
)
2
≤
∥
L
K
-
L
K
x
∥
H
S
2
,
where ∥
L
K
-
L
K
x
∥
H
S is the Hilbert-Schmidt norm of H
S
(
H
K
), the Hilbert space of all Hilbert-Schmidt operators on H
K, with inner product 〈
A
,
B
〉
H
S
=
Tr
⁡
(
B
T
A
). Here Tr
⁡ denotes the trace of a linear operator.The inner product inHS
(
H
K
) can also be defined by 〈
A
,
B
〉
HS
=
∑
j
‍
〈
A
e
j
,
B
e
j
〉
K, where {
e
j
} is an orthonormal basis of H
K. The space HS
(
H
K
) is a subspace of the space of bounded linear operators on H
K, denoted as (
H
K
,
∥
·
∥
), with the norm relations ∥
A
∥
≤
∥
A
∥
HS and ∥
A
B
∥
HS
≤
∥
A
∥
HS
∥
B
∥.To bound the quantity∥
L
K
-
L
K
x
∥
HS, we introduce the following McDiarmid-Bernstein type of probability inequality for vector-valued random variable established in [17].Lemma 9.
Letz
=
{
z
i
}
i
=
1
m be independently drawn according to a probability distribution ρ on Z, (
H
,
∥
·
∥
) a Hilbert space, and F
:
Z
m
→
H measurable. If there is M
~
>
0 such that ∥
F
(
z
)
-
E
z
i
(
F
(
z
)
)
∥
≤
M
~ for each 1
≤
i
≤
m and almost every z
∈
Z
m, then for every ϵ
>
0,
(24)
P
r
o
b
{
∥
F
(
z
)
-
E
z
(
F
(
z
)
)
∥
>
ϵ
}
≤
2
exp
⁡

{
-
ϵ
2
2
(
M
~
ϵ
+
σ
2
)
}
,
where σ
2
=
∑
i
=
1
m
‍
sup
⁡
z
∖
{
z
i
}
∈
Z
m
-
1
E
z
i
{
∥
F
(
z
)
-
E
z
i
(
F
(
z
)
)
∥
2
}. For any 0
<
δ
<
1, with confidence 1
-
δ, there holds
(25)
∥
F
(
z
)
-
E
z
(
F
(
z
)
)
∥
≤
2
(
M
~
+
σ
2
)
log
⁡
2
δ
.From the factTr
⁡
(
〈
·
,
K
x
〉
K
K
x
′
)
=
K
(
x
,
x
′
) (see [22]) and after tedious calculations, one can derive that, for each l
∈
{
1
,
…
,
m
}, ∥
L
K
x
-
E
x
l
(
L
K
x
)
∥
HS
≤
(
6
/
m
)
κ
2. By Lemma 9, we obtain the following.Lemma 10.
For any0
<
δ
<
1, with confidence 1
-
δ, there holds
(26)
∥
L
K
-
L
K
x
∥
H
S
≤
24
κ
2
log
⁡
⁡
(
2
/
δ
)
m
.Define a vector-valued functionF
:
Z
m
→
H
K by
(27)
F
(
z
)
=
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
f
ρ
(
x
i
)
-
f
ρ
(
x
j
)
)
)
K
x
i
.
It is easy to show that E
z
(
F
(
z
)
)
=
0 and for each l
∈
{
1
,
…
,
m
}, ∥
F
(
z
)
-
E
z
l
(
F
(
z
)
)
∥
K
≤
8
M
κ
/
m. By Lemma 9, one has the following.Lemma 11.
For any0
<
δ
<
1, with confidence 1
-
δ, there holds
(28)
∥
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
f
ρ
(
x
i
)
-
f
ρ
(
x
j
)
)
)
K
x
i
∥
K
≤
32
m
(
m
-
1
)
M
κ
log
⁡
⁡
2
δ
.With the help of the preceding five lemmas, we are now in a position to derive an error estimate for the algorithm. We will conduct analysis for the error in theH
k-metric, which makes the corresponding error estimate stronger than that performed in the L
ρ
X
2-metric [16].Theorem 12.
Assume (7). For any 0
<
δ
<
1, with confidence 1
-
δ, one has
(29)
∥
f
ϵ
z
-
f
ρ
∥
K
≤
∥
g
ρ
∥
K
λ
s
r
+
C
1
log
⁡
⁡
(
4
/
δ
)
ϵ
m
+
λ
s
min
⁡
{
1
,
r
-
1
}
C
3
log
⁡
⁡
(
4
/
δ
)
m
+
C
2
λ
s
min
⁡
{
1
,
r
-
1
}
(
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
⁡
{
2
r
,
2
}
)
1
/
2
,
where C
1, C
2, and C
3 are constants independent of m and δ (given explicitly in the proof).Proof.
By Lemmas10 and 11, we know that for any 0
<
δ
<
1
/
2 there exists a subset Z
δ of Z
m of measure at least 1
-
2
δ such that both (26) and (28) hold for each z
∈
Z
δ.
Letz
∈
Z
δ. It follows from the orthogonal expansion in terms of the orthonormal basis {
ϕ
l
x
} that
(30)
∥
f
ϵ
z
-
f
ρ
∥
K
2
=
∑
l
=
s
+
1
∞
‍
〈
f
ρ
,
ϕ
l
x
〉
K
2
+
∑
l
=
1
s
‍
(
〈
f
ρ
,
ϕ
l
x
〉
K
-
c
ϵ
,
l
z
)
2
=
:
Δ
1
+
Δ
2
.
We bound the first term Δ
1 on the right-hand side of (30) by decomposing it further into two parts with f
ρ
=
∑
j
=
1
s
‍
λ
j
r
d
j
ϕ
j
+
∑
j
=
s
+
1
∞
‍
λ
j
r
d
j
ϕ
j:
(31)
Δ
1
≤
(
∑
l
=
s
+
1
∞
‍
〈
∑
j
=
1
s
‍
λ
j
r
d
j
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
+
(
∑
l
=
s
+
1
∞
‍
〈
∑
j
=
s
+
1
∞
‍
λ
j
r
d
j
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
.
The part with ∑
j
=
s
+
1
∞
‍ is easy to deal with since {
ϕ
l
x
} is an orthonormal basis; we have
(32)
(
∑
l
=
s
+
1
∞
‍
〈
∑
j
=
s
+
1
∞
‍
λ
j
r
d
j
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
=
∥
∑
j
=
s
+
1
∞
‍
λ
j
r
d
j
ϕ
j
∥
K
≤
∥
g
ρ
∥
K
λ
s
r
,
where the last inequality follows from ∥
{
d
i
}
∥
l
2
=
∥
g
ρ
∥
K. The part with ∑
j
=
1
s
‍ can be estimated by the Schwarz inequality as
(33)
(
∑
l
=
s
+
1
∞
‍
〈
∑
j
=
1
s
‍
λ
j
r
d
j
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
≤
(
∑
l
=
s
+
1
∞
‍
∥
{
d
j
}
∥
l
2
2
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
≤
∥
g
ρ
∥
K
(
∑
l
=
s
+
1
∞
‍
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2
.
We continue to bound(
∑
l
=
s
+
1
∞
‍
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
)
1
/
2 in two cases.
Case  1
(
r
≥
1
). For l
≥
s
+
1, we observe that
(34)
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
≤
∑
j
=
1
s
‍
2
2
r
-
1
(
λ
l
2
r
+
(
λ
j
-
λ
l
)
2
r
)
〈
ϕ
j
,
ϕ
l
x
〉
K
2
≤
2
2
r
-
1
∑
j
=
1
s
‍
(
λ
l
2
r
+
λ
1
2
r
-
2
(
λ
j
-
λ
l
)
2
)
〈
ϕ
j
,
ϕ
l
x
〉
K
2
≤
2
2
r
-
1
∑
j
=
1
s
‍
(
e
e
λ
l
2
r
+
2
λ
1
2
r
-
2
(
λ
j
-
λ
l
x
)
2
0000000000
+
2
λ
1
2
r
-
2
(
λ
l
x
-
λ
l
)
2
e
e
)
〈
ϕ
j
,
ϕ
l
x
〉
K
2
.
From the definition of the Hilbert-Schmidt norm, we have
(35)
∥
L
K
-
L
K
x
∥
HS
2
=
∑
l
=
1
∞
‍
∥
(
L
K
-
L
K
x
)
ϕ
l
x
∥
K
2
=
∑
j
,
l
=
1
∞
‍
(
λ
j
-
λ
l
x
)
2
〈
ϕ
j
,
ϕ
l
x
〉
K
2
.
By Lemma 8, we get
(36)
∑
l
=
s
+
1
∞
‍
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
≤
2
2
r
-
1
∑
l
=
s
+
1
∞
‍
λ
l
2
r
+
2
2
r
+
1
λ
1
2
r
-
2
∥
L
K
-
L
K
x
∥
HS
2
.
Case  2
(
r
<
1
). We notice that λ
j
2
r
≤
λ
s
2
r
-
2
λ
j
2 and obtain from the above estimate
(37)
∑
l
=
s
+
1
∞
‍
∑
j
=
1
s
‍
λ
j
2
r
〈
ϕ
j
,
ϕ
l
x
〉
K
2
≤
2
λ
s
2
r
-
2
∑
l
=
s
+
1
∞
‍
λ
l
2
+
8
λ
s
2
r
-
2
∥
L
K
-
L
K
x
∥
HS
2
.
The bounds for the two cases together with (32) give a bound for Δ
1 as
(38)
Δ
1
≤
{
∥
g
p
∥
K
λ
s
r
+
τ
1
,
if
r
≥
1
,
∥
g
p
∥
K
λ
s
r
+
τ
2
,
if
r
<
1
.
Here
(39)
τ
1
=
2
r
∥
g
ρ
∥
K
(
(
∑
l
=
s
+
1
∞
‍
λ
l
2
r
)
1
/
2
+
2
λ
1
r
-
1
∥
L
K
-
L
K
x
∥
HS
)
,
τ
2
=
2
∥
g
ρ
∥
K
λ
s
r
-
1
(
(
∑
l
=
s
+
1
∞
‍
λ
l
2
)
1
/
2
+
2
∥
L
K
-
L
K
x
∥
HS
)
.
Now we turn to the second termΔ
2 on the right-hand side of (30). Note that
(40)
Δ
2
=
(
∑
l
=
1
s
‍
(
〈
f
ρ
,
ϕ
l
x
〉
K
-
c
ϵ
,
l
z
)
2
)
1
/
2
≤
1
ϵ
(
∑
l
=
1
s
‍
(
λ
l
x
〈
f
ρ
,
ϕ
l
x
〉
K
-
λ
l
x
c
ϵ
,
l
z
)
2
)
1
/
2
.
By Theorem 7, we have
(41)
∑
l
=
1
s
‍
(
λ
l
x
〈
f
ρ
,
ϕ
l
x
〉
K
-
λ
l
x
c
ϵ
,
l
z
)
2
=
∑
l
=
1
s
‍
(
〈
f
ρ
,
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
ϕ
l
x
(
x
i
)
(
K
x
i
-
K
x
j
)
〉
K
000000000
-
S
l
z
2
m
(
m
-
1
)
〈
f
ρ
,
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
ϕ
l
x
(
x
i
)
(
K
x
i
-
K
x
j
)
〉
K
)
2
=
∑
l
=
1
s
‍
(
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
ϕ
l
x
(
x
i
)
(
f
ρ
(
x
i
)
-
f
ρ
(
x
j
)
)
0000000000
-
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
)
ϕ
l
x
(
x
i
)
)
2
≤
∥
1
m
(
m
-
1
)
∑
i
,
j
=
1
m
‍
(
y
i
-
y
j
-
(
f
ρ
(
x
i
)
-
f
ρ
(
x
j
)
)
)
K
x
i
∥
K
2
≤
32
M
κ
log
⁡
⁡
(
2
/
δ
)
m
.
Thus, for any 0
<
δ
<
1, with confidence 1
-
δ, we have
(42)
Δ
2
≤
32
M
κ
log
⁡
⁡
(
2
/
δ
)
ϵ
m
.
Putting the bounds for Δ
1 and Δ
2 into (26), we know that, with confidence 1
-
δ, ∥
f
ϵ
z
-
f
ρ
∥
K can be bounded by
(43)
32
M
κ
log
⁡
⁡
(
2
/
δ
)
ϵ
m
+
∥
g
ρ
∥
K
λ
s
r
+
{
τ
1
,
if
r
≥
1
,
τ
2
,
if
r
<
1
.
Let C
1
=
32
M
κ, C
2
=
2
max
⁡
{
r
,
1
}
∥
g
ρ
∥
K, and C
3
=
24
κ
2
2
max
⁡
{
r
+
1,2
}
λ
1
max
⁡
{
r
-
1,0
}
∥
g
ρ
∥
K. Then the conclusion of Theorem 12 follows by scaling 2
δ to δ.To illustrate the error estimate, we establish learning rate for the algorithm (15) in a special case when the eigenvalues {
λ
l
} decay polynomially.Theorem 13.
Assume (7) and for some 1
/
2
r
<
α
2
≤
α
1
<
(
1
+
r
)
α
2
-
(
1
/
2
) and D
1, D
2
>
0, the eigenvalues {
λ
l
} decay polynomially as
(44)
D
1
l
-
α
1
≤
λ
l
≤
D
2
l
-
α
2
.
Let ϵ
>
0 such that s
=
⌊
m
1
/
(
2
r
α
2
-
1
)
⌋ for r
≥
1 or s
=
⌊
m
1
/
(
2
α
2
-
1
)
⌋ for 0
<
r
<
1. Then, for any 0
<
δ
<
1, with confidence 1
-
δ, we have
(45)
∥
f
γ
z
-
f
ρ
∥
K
≤
{
C
~
1
log
⁡
⁡
4
δ
m
-
1
/
2
,
i
f
r
≥
1
,
C
~
2
log
⁡
⁡
4
δ
m
(
(
α
1
(
1
-
r
)
)
/
(
2
α
2
-
1
)
)
-
(
1
/
2
)
,
i
f
r
<
1
,
where C
~
1 and C
~
2 are constants independent of m and δ (given explicitly in the proof).Proof.
It follows from the asymptotic behavior of the eigenvalues that(46)
∥
g
ρ
∥
K
λ
s
r
+
C
1
log
⁡
⁡
(
4
/
δ
)
ϵ
m
≤
∥
g
ρ
∥
K
D
2
r
s
-
α
2
r
+
C
1
log
⁡
⁡
(
4
/
δ
)
ϵ
m
.
For r
≥
1, we have
(47)
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
{
2
r
,
2
}
=
∑
l
=
s
+
1
∞
‍
λ
l
2
r
≤
D
2
2
r
∑
l
=
s
+
1
∞
‍
l
-
2
r
α
2
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
{
2
r
,
2
}
≤
D
2
2
r
∫
s
∞
‍
x
-
2
r
α
2
d
x
=
D
2
2
r
s
1
-
2
r
α
2
2
r
α
2
-
1
,
(48)
λ
s
min
⁡
{
1
,
r
-
1
}
{
C
2
(
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
⁡
{
2
r
,
2
}
)
1
/
2
+
C
3
log
⁡
(
4
/
δ
)
m
}
≤
C
2
λ
s
D
2
r
s
(
1
-
2
r
α
2
)
/
2
2
r
α
2
-
1
+
C
3
λ
s
log
⁡
(
4
/
δ
)
m
≤
C
2
λ
1
D
2
r
2
r
α
2
-
1
s
(
1
-
2
r
α
2
)
/
2
+
C
3
λ
1
log
⁡
(
4
/
δ
)
ϵ
m
.
Combining (46) and (48), we see that
(49)
∥
f
ϵ
z
-
f
ρ
∥
K
≤
(
∥
g
ρ
∥
K
D
2
r
+
C
2
λ
1
D
2
r
2
r
α
2
-
1
)
s
(
1
-
2
r
α
2
)
/
2
+
(
C
1
+
C
3
λ
1
)
log
⁡
(
4
/
δ
)
ϵ
m
.
By choosing ϵ
>
0 such that s
=
⌊
ϵ
2
/
(
2
r
α
2
-
1
)
m
1
/
(
2
r
α
2
-
1
)
⌋
=
⌊
m
1
/
(
2
r
α
2
-
1
)
⌋, we have
(50)
∥
f
ϵ
z
-
f
ρ
∥
K
≤
(
∥
g
ρ
∥
K
D
2
r
+
C
2
λ
1
D
2
r
2
r
α
2
-
1
+
C
1
+
C
3
λ
1
)
×
log
⁡
⁡
(
4
/
δ
)
ϵ
m
.
Similarly, for0
<
r
<
1, we have
(51)
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
{
2
r
,
2
}
≤
D
2
2
s
1
-
2
α
2
2
α
2
-
1
,
λ
s
min
⁡
{
1
,
r
-
1
}
{
C
2
(
∑
l
=
s
+
1
∞
‍
λ
l
max
⁡
⁡
{
2
r
,
2
}
)
1
/
2
+
C
3
log
⁡
⁡
(
4
/
δ
)
m
}
≤
C
2
D
1
r
-
1
D
2
2
α
2
-
1
s
-
α
1
(
r
-
1
)
+
(
(
1
-
2
α
2
)
/
2
)
+
C
3
s
-
α
1
(
r
-
1
)
log
⁡
⁡
(
4
/
δ
)
m
.
Thus, we have, in light of 1
/
2
r
<
α
2
≤
α
1
<
(
1
+
r
)
α
2
-
(
1
/
2
),
(52)
∥
f
ϵ
z
-
f
ρ
∥
K
≤
(
∥
g
ρ
∥
K
D
2
r
+
C
2
D
1
r
-
1
D
2
2
α
2
-
1
)
s
α
1
(
1
-
r
)
+
(
(
1
-
2
α
2
)
/
2
)
+
(
C
1
+
C
3
)
s
α
1
(
1
-
r
)
log
⁡
⁡
(
4
/
δ
)
ϵ
m
.
By choosing ϵ
>
0 such that s
=
⌊
ϵ
2
/
(
2
α
2
-
1
)
m
1
/
(
2
α
2
-
1
)
⌋
=
⌊
m
1
/
(
2
α
2
-
1
)
⌋, we have
(53)
∥
f
ϵ
z
-
f
ρ
∥
K
≤
(
∥
g
ρ
∥
K
D
2
r
+
C
2
D
1
r
-
1
D
2
2
α
2
-
1
+
C
1
+
C
3
)
×
(
log
⁡
4
δ
)
ϵ
(
2
α
1
(
1
-
r
)
/
(
2
α
2
-
1
)
)
-
1
×
m
(
α
1
(
1
-
r
)
/
(
2
α
2
-
1
)
)
-
(
1
/
2
)
.
This completes the proof of the theorem with C
~
1
=
(
∥
g
ρ
∥
K
D
2
r
+
(
C
2
λ
1
D
2
r
/
2
r
α
2
-
1
)
+
C
1
+
C
3
λ
1
)
ϵ
-
1 and C
~
2
=
(
∥
g
ρ
∥
K
D
2
r
+
(
C
2
D
1
r
-
1
D
2
/
2
α
2
-
1
)
+
C
1
+
C
3
)
ϵ
(
2
α
1
(
1
-
r
)
/
(
2
α
2
-
1
)
)
-
1.Remark 14.
The truncated parameterϵ in algorithm (15) plays a role of the regularization parameter instead of γ. Thus error bounds for our algorithm are closely related to the truncated parameter. Note that our learning rates are given in terms of special choices of the truncated parameter which depends on a priori condition (7). However, methods for determining directly the truncated parameter by the data are more preferrable to practical learners. This will be our future research direction.Remark 15.
Note that whenr is large enough (meaning that f
ρ has high regularity), the learning rate behaves like m
-
1
/
2. Moreover, the nonzero coefficients in f
ϵ
z
=
∑
l
=
1
s
‍
c
ϵ
,
l
z
ϕ
l
x are at most s
=
⌊
m
1
/
(
2
r
α
2
-
1
)
⌋, which is much smaller than the sample size m when r
α
2 is large. Thus, our algorithm produces sparse representations with respect to the empirical eigenfunctions under a mild condition.



---

*Source: 197476-2014-07-21.xml*