# Learning Rates forl1-Regularized Kernel Classifiers

Authors: Hongzhi Tong; Di-Rong Chen; Fenghong Yang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We consider a family of classification algorithms generated from a regularization kernel scheme associated withl1-regularizer and convex loss function. Our main purpose is to provide an explicit convergence rate for the excess misclassification error of the produced classifiers. The error decomposition includes approximation error, hypothesis error, and sample error. We apply some novel techniques to estimate the hypothesis error and sample error. Learning rates are eventually derived under some assumptions on the kernel, the input space, the marginal distribution, and the approximation error.


---

## Body

## 1. Introduction

LetX be a compact subset of ℝn, Y={-1,1}. Classification algorithms produce binary classifiers 𝒞:X→Y, such a classifier 𝒞 labels a class 𝒞(x)∈Y for each point x∈X. The prediction power of the classifier 𝒞 is measured by its misclassification error. If ρ is a probability distribution on Z≔X×Y, then the misclassification error of 𝒞 is defined by
(1)ℛ(𝒞)≔Prob{𝒞(x)≠y}=∫X‍ρ(y≠𝒞(x)∣x)dρX.
Here ρX is the marginal distribution on X and ρ(·∣x) is the conditional probability measure at x induced by ρ. The classifier minimizing the misclassification error is called the Bayes rule fc and is given by
(2)fc(x)={1,ifρ(y=1∣x)≥ρ(y=-1∣x),-1,otherwise.The classifiers considered in this paper have the formsgn(f), defined as sgn(f)(x)=1, if f(x)≥0, and sgn(f)(x)=-1, if f(x)<0, induced by real-valued functions f:X→ℝ. Those functions are generated from a regularization scheme associated with convex loss function (see [1]).Definition 1.
A continuous functionV: ℝ→ℝ+ is called a classifying loss (function) if it is convex, differentiable at 0 with V′(0)<0, and 1 is the smallest real for which the value of V is zero.Typical examples of classifying loss include(1)
hinge lossVh(t)=(1-t)+=max{1-t,0} for the classical support vector machines (SVM) classifier; see [2–5];(2)
least square lossVls(t)=(1-t)2; see for example [6, 7];(3)
q-norm (q>1) SVM loss Vq(t)=(1-t)+q; see [8, 9].The following concept describes the increment ofV.Definition 2.
One says thatV has a increment exponent θ≥1, if there exists some cθ>0 such that
(3)|V(t)|≤cθ(1+|t|)θ,|V±′(t)|≤cθ(1+|t|)θ-1,∀t∈ℝ,
where V±′ denotes the right and left derivatives of V.It is easy to see thatVh,Vls, and Vq satisfy Definition 2 with increment exponent 1, 2, and q, respectively.Letz≔{zi}i=1m={(xi,yi)}i=1m∈Zm be a set of samples independently drawn according to ρ; we call
(4)ℰz(f)≔ℰzV(f)=1m∑i=1m‍V(yif(xi))
the empirical error with respect to z. Regularized learning schemes are implemented by minimizing a penalized version of empirical error over a set of functions, called a hypothesis space.Definition 3.
Given a classifying lossV and a hypothesis space ℋ, Ω:ℋ→ℝ+ is a penalty functional called regularizer that reflects the constrains imposed on functions from ℋ. The regularized classifier is then defined as sgn(fz), where fz is a minimizer of the following regularization scheme:
(5)fz≔argminf∈ℋ{ℰz(f)+λΩ(f)}.
Here λ is a regularization parameter which may depend on the sample size λ=λ(m) with limm→∞λ(m)=0.Choosing different hypothesis spaces and regularizers in (5) will lead to different regularization algorithms. These learning algorithms are often based on a kernel function K:X×X→ℝ (see, e.g., [10]). One way appears naturally when K is a Mercer kernel. Such a kernel is continuous, symmetric, and positive semidefinite on X×X. The reproducing kernel Hilbert spaces (RKHS) ℋK associated with the Mercer kernel K is defined [11] to be the completion of the linear span of functions {Kx≔K(x,·):x∈X} with the inner product:
(6)〈Kx,Ku〉K=K(x,u),
and the reproducing property is given by
(7)〈Kx,f〉K=f(x),∀x∈X,f∈ℋK.
By setting ℋ=ℋK, Ω(f)=∥f∥K2, (5) becomes the classical regularized classification scheme:
(8)f~z,λ≔argminf∈ℋK{ℰz(f)+λ∥f∥K2}.
Its mathematical analysis has been well understood with various techniques in extensive literature (see, e.g., [4, 5, 8, 12–15]). In this paper we will consider a different regularization scheme in RKHS for classification; in our setting, the regularizer is l1-norm of the coefficients in the kernel expansions over the sample points.Definition 4.
Let(9)ℋK,z≔{∑i=1m‍aiKxi:ai∈ℝ},Ωz(f)≔inf{∑i=1m‍|ai|:f=∑i=1m‍aiKxi}.
Then the l1-regularized classification scheme is given as
(10)fz,λ≔argminf∈ℋK,z{ℰz(f)+λΩz(f)}.Algorithm (10) can be efficiently computed because it reduces to solve a convex optimization problem in a finite dimensional space ℋK,z, containing linear combinations of kernels centered on the training points.In the last ten years, learning withl1-regularization has attracted much attention. The increasing interest is mainly brought by the progress of the Lasso algorithm [16–18] and compressive sensing [19, 20], in which l1-regularizer is able to yield sparse representation of the resulting minimizer. Kernel methods formulate learning and estimation problems in RKHS of functions expanded in terms of kernels. There have been a series of papers to investigate the learning ability of coefficient-based regularization kernel regression methods (see, e.g., [21–25]). However, as we know, there are currently a few results on classification based on kernel designing. For example, [26] studies classification problem with hinge loss Vh and l1 complexity regularization in a finite-dimensional hypothesis space spanned by a set of base functions. While it does not assume a kernel setting nor is it assumed that the expansion must be in terms of the sample points, so the problem of data-dependent hypothesis space is not present there. Although [27] provided an error analysis for linear programming SVM classifiers by means of a stepping-stone from quadratic programming SVM to linear programming SVM, no evidence shows that this method can still work for other classifying losses.In this paper we will present an elaborate error analysis for algorithm (10), and we use a modified error decomposition technique that was firstly introduced in [28], by dealing with the approximation error, the hypothesis error, and the sample error, and we derive an explicit learning rate for classification scheme (10) under some assumptions.


## 2. Preliminaries

For a classifying lossV, we define the generalization error of f:X→ℝ as
(11)ℰ(f)≔ℰV(f)=∫Z‍V(yf(x))dρ.
Let fρV be a measurable function minimizing the generalization error:
(12)fρV≔argminℰ(f),
where the minimum is taken over all measurable functions. According to Theorem 3(c) in [12], we may always choose an fρV satisfying fρV(x)∈[-1,1] for each x∈X. This choice will be taken throughout the paper.Estimating the excess misclassification error(13)ℛ(sgn(fz,λ))-ℛ(fc)
for classification scheme (10) is our main purpose. The following comparison theorem (see [7, 8, 12]) describes the relationship between excess misclassification error and excess generalization error.Proposition 5.
IfV is a classifying loss, then, for any measurable function f,
(14)ℛ(sgn(f))-ℛ(fc)≤{ℰ(f)-ℰ(fc)ifV(t)=(1-t)+,cVℰ(f)-ℰ(fρV)ifV′′(0)≥0,
where cV is some constant dependent on V.SincefρV(x)∈[-1,1], we can improve the error estimates by replacing values of f by projections onto [-1,1]. The idea of the following projection operator was firstly introduced for this purpose in [29].Definition 6.
The projection operatorπ is defined on the space of measurable functions f:X→ℝ as
(15)π(f)(x)={1,iff(x)>1,-1,iff(x)<-1,f(x),if-1≤f(x)≤1.The definition of classifying loss implies thatV(yπ(f)(x))≤V(yf(x)), so
(16)ℰ(π(f))≤ℰ(f),ℰz(π(f))≤ℰz(f).
It is trivial that sgn(π(f))=sgn(f). By Proposition 5,
(17)ℛ(sgn(f))-ℛ(fc)≤{ℰ(π(f))-ℰ(fc)ifV(t)=(1-t)+,cVℰ(π(f))-ℰ(fρV)ifV′′(0)≥0.So it is sufficient for us to bound (13) by means of ℰ(π(fz,λ))-ℰ(fρV), which in turn can be estimated by an error decomposition technique. However, there are essential differences between algorithm (8) and (10). For example, the hypothesis space ℋK,z and the regularizer Ωz(f) in (10) are dependent on samples z. This causes that the standard error analysis methods of (8) (see, e.g., [8, 12, 13, 30]) cannot be applied to (10) any more. This difficulty was overcome in [28] by introducing a modified error decomposition with an extra hypothesis error term. In this paper we apply the same underlying idea to classification scheme (10). To this end, we need to consider a Banach space containing all of the possible hypothesis space ℋK,z.Definition 7.
The Banach spaceℋ0 is defined as the function set on X containing all functions of the form
(18)f=∑j=1∞‍ajKuj,{aj}j=1∞∈l1,{uj}j=1∞⊂X,
with the norm
(19)∥f∥≔inf{∑j=1∞‍|aj|:f=∑j=1∞‍ajKuj}.Obviously,(20)ℋK,z⊂ℋ0,∀z∈Zm.
By the continuity of K and compactness of X, we have (21)κ≔supx∈XK(x,x)<∞.
It implies that ℋ0 is a subset of the continuous function space C(X), and
(22)∥f∥∞≤κ∥f∥,∀f∈ℋ0.
To formulate the error decomposition for scheme (10), we introduce a regularization function as
(23)fλ≔argminf∈ℋ0{ℰ(f)+λ∥f∥}.Proposition 8.
Letfz,λ be defined in (10), λ>0; then
(24)ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥≤S(z,λ)+P(z,λ)+D(λ).
Here
(25)S(z,λ)≔{ℰ(π(fz,λ))-ℰz(π(fz,λ))}+{ℰz(fλ)-ℰ(fλ)},P(z,λ)≔{ℰz(π(fz,λ))+λΩz(fz,λ)}-{ℰz(fλ)+λ∥fλ∥},(26)D(λ)≔{ℰ(fλ)-ℰ(fρV)+λ∥fλ∥}=inff∈ℋ0{ℰ(f)-ℰ(fρV)+λ∥f∥}.Proof.
(27)
ℰ
(
π
(
f
z
,
λ
)
)
-
ℰ
(
f
ρ
V
)
+
λ
∥
f
z
,
λ
∥
≤
ℰ
(
π
(
f
z
,
λ
)
)
-
ℰ
(
f
ρ
V
)
+
λ
Ω
z
(
f
z
,
λ
)
=
{
ℰ
(
π
(
f
z
,
λ
)
)
-
ℰ
z
(
π
(
f
z
,
λ
)
)
}
+
{
ℰ
z
(
π
(
f
z
,
λ
)
)
+
λ
Ω
z
(
f
z
,
λ
)
}
+
{
ℰ
z
(
f
λ
)
-
ℰ
(
f
λ
)
}
-
{
ℰ
z
(
f
λ
)
+
λ
∥
f
λ
∥
}
+
{
ℰ
(
f
λ
)
-
ℰ
(
f
ρ
V
)
+
λ
∥
f
λ
∥
}
=
S
(
z
,
λ
)
+
P
(
z
,
λ
)
+
D
(
λ
)
.P
(
z
,
λ
) and S(z,λ) are called hypothesis error and sample error, and they will be estimated, respectively, in next two sections. D(λ) is independent of samples and usually called approximation error, and it characterizes the approximation ability of the function space ℋ0 with respect to target function fρV. We will assume that, for some constants 0<β≤1 and cβ>0,
(28)D(λ)≤cβλβ,∀λ>0.


## 3. Estimating the Hypothesis Error

In this section we bound the hypothesis errorP(z,λ) by a technique of scattered data interpolation which was firstly used in kernel regression context in [25]. To this end, we need some assumptions on input space X, margin distribution ρX, and kernel K. Denote |·|2 the Euclidean norm in ℝn.Definition 9.
A subsetX of ℝn is said to satisfy an interior cone condition if there exist an angle ϑ∈(0,π/2), a radius R>0, and a unit vector ζ(x) for every x∈X such that the cone
(29)C(x,ζ(x),ϑ,R)={x+tw:w∈ℝn,|w|2=1,wTζ(x)≥cosϑ,t∈[0,R]}
is contained in X.Definition 10.
The margin distributionρX is said to satisfy condition Lτ with 0<τ<∞ if for some cτ>0(30)ρX({u∈X:|u-x|2<r})≥cτrτ,∀x∈X,0<r≤1.Recall that, fors∈ℕ, the space Cs(X) consists of functions f whose partial derivative Ddf is continuous for every d=(d1,d2,…,dn)∈ℕn with |d|≔d1+⋯+dn≤s, and ∥f∥Cs≔∑|d|≤s‍∥Ddf∥∞. Throughout the paper we assume the kernel K∈Cs(X×X) with s>0.Definition 11.
a set{x1,x2,…,xm}⊂X is said to be Δ-dense if for any x∈X there exists some 1≤i≤m such that |x-xi|2<Δ.The following lemma derived from [31] describes a local polynomial reproduction and it is the key point to bound the hypothesis error.Lemma 12.
Suppose thatX⊂ℝn is compact and satisfies an interior cone condition with some radius R>0 and angle ϑ∈(0,π/2). Fix s∈ℕ with s≥2. Assume that the point set {x1,x2,…,xm}⊂X is Δ-dense with Δ≤R/c0 for some constant c0 depending on X and s; then, for any u∈X, there exist real number bi(u),  i=1,2,…,m, satisfying that(1)
∑i=1m‍bi(u)p(xi)=p(u),p(·) is any polynomial of degree at most s on ℝn,(2)
∑i=1m‍|bi(u)|≤2,(3)
bi(u)=0 for those u satisfying |u-xi|2>c0Δ.Proposition 13.
LetV be a classifying loss satisfying (3), K∈Cs(X×X) for some s∈ℕ, s≥2. If X satisfies the conditions in Lemma 12 and {x1,x2,…,xm} is Δ-dense in X with Δ≤R/c0, then
(31)P(z,λ)≤D(λ)+2cθ∥K∥Cs(2θ-1+(4κ)θ-1)×((D(λ)λ)θ+D(λ)λ)c0sΔs.Proof.
We know from (26) that ∥fλ∥≤D(λ)/λ. So for any η>0, fλ can be written as fλ=∑j=1∞‍βjKuj with uj∈X and
(32)∥fλ∥≤∑j=1∞‍|βj|<∥fλ∥+η≤D(λ)λ+η.
At the same time, there exists some N∈ℕ such that ∑j=N∞‍|βj|<η, and thus
(33)∥∑j=1N‍βjKuj-fλ∥∞≤κ∑j=N∞‍|βj|≤κη.
Fix x∈X and j∈{1,2,…,N}, and we can take px as the Taylor polynomial of Kx of degree s-1 at uj. Then by Lemma 12, there exists {bi(uj)}i=1m∈ℝm such that
(34)∑i∈I(uj)‍bi(uj)px(xi)=px(uj)=Kx(uj),∑i∈I(uj)‍|bi(uj)|≤2,
where I(uj)={i∈{1,2,…,m}:|xi-uj|2≤c0Δ}. Moreover,
(35)maxi∈I(uj)|Kx(xi)-px(xi)|≤∥K∥Cs(c0Δ)s.
It follows from (34) that
(36)|Kuj(x)-∑i∈I(uj)‍bi(uj)Kxi(x)|=|Kx(uj)-∑i∈I(uj)‍bi(uj)Kx(xi)|=|∑i∈I(uj)‍bi(uj)(px(xi)-Kx(xi))|≤2∥K∥Cs(c0Δ)s.
The above bound holds for every x∈X and j∈{1,2,…,N}, so
(37)∥∑j=1N‍βj(Kuj-∑i∈I(uj)‍bi(uj)Kxi)∥∞≤2∥K∥Cs(c0Δ)s∑j=1N‍|βj|.
This together with (33) and (32) implies
(38)∥∑j=1N‍βj∑i∈I(uj)‍bi(uj)Kxi-fλ∥∞≤κη+2∥K∥Cs(c0Δ)s(D(λ)λ+η).
Denote f0=∑j=1N‍βj∑i∈I(uj)‍bi(uj)Kxi∈ℋK,z; we get from (16), (10), and (32) that
(39)ℰz(π(fz,λ))+λΩz(fz,λ)≤ℰz(fz,λ)+λΩz(fz,λ)≤ℰz(f0)+λΩz(f0)≤ℰz(f0)+2λ(∥fλ∥+η).
Since V is convex and satisfies (3), we have, for any t1,t2∈ℝ,
(40)|V(t1)-V(t2)|≤max{|V±′(t1)|,|V±′(t2)|}|t1-t2|≤cθ(1+max{|t1|,|t2|})θ-1|t1-t2|.
This in connect with (22), (32), and (38) yields
(41)|ℰz(f0)-ℰz(fλ)|≤cθ(1+2κ(D(λ)λ+η))θ-1∥f0-fλ∥∞≤cθ(1+2κ(D(λ)λ+η))θ-1×(κη+2∥K∥Cs(c0Δ)s(D(λ)λ+η)).
Therefore
(42)ℰz(π(fz,λ))+λΩz(fz,λ)≤ℰz(fλ)+λ∥fλ∥+D(λ)+2λη+cθ(1+2κ(D(λ)λ+η))θ-1×(κη+2∥K∥Cs(c0Δ)s(D(λ)λ+η)).
Let η→0, and we then derive
(43)P(z,λ)≤D(λ)+2cθ∥K∥Cs(2θ-1+(4κ)θ-1)×((D(λ)λ)θ+D(λ)λ)c0sΔs.We can now boundP(z,λ) by the following theorem.Theorem 14.
LetV be a classifying loss satisfying (3), K∈Cs(X×X) for some s∈ℕ,s≥2. Suppose that X satisfies the conditions in Lemma 12 and ρX satisfies condition Lτ with some τ>0, and (28) is valid; then, for any 0<δ<1 and m satisfying
(44)m≥C1(log(2δ)+log(m+1)),
with confidence 1-δ/2,
(45)P(z,λ)≤C2((log(2/δ)+log(m+1)m)s/τλβ+(λβ-1+λ(β-1)θ)×(log(2/δ)+log(m+1)m)s/τ),
where C1,C2 are some constants independent of λ, m, or δ.Proof.
Applying Lemma  3 in [21], we get that, with confidence 1-δ/2, the point set {x1,x2,…,xm} is A((log(2/δ)+log(m+1))/m)1/τ-dense in X, where A is a constant depending on X, τ, and cτ. Taking Δ=A((log(2/δ)+log(m+1))/m)1/τ, C1=(c0A/R)τ. If m≥C1(log(2/δ)+log(m+1)), then we have Δ≤R/c0. So Proposition 13 ensures us that, with confidence 1-δ/2,
(46)P(z,λ)≤cβλβ+2cθ∥K∥Cs(2θ-1+(4κ)θ-1)×(cβθλ(β-1)θ+cβλ(β-1))c0sAs(log(2/δ)+log(m+1)m)s/τ.
This proves the theorem by setting C2≔cβ+2cθ∥K∥Cs(2θ-1+(4κ)θ-1)c0sAs(cβθ+cβ).


## 4. Estimating the Sample Error

In this section we focus on the sample error, it is the major improvement we make in this paper for the error analysis of algorithm (10).Definition 15.
Letℱ be a class of functions on Z and z≔{zi}i=1m∈Zm. The l2-metric d2,z is defined on ℱ by
(47)d2,z(f,g)≔{1m∑i=1m‍|f(zi)-g(zi)|2}1/2.
For every ɛ>0, the covering number of ℱ with respect to d2,z is
(48)𝒩2,z(ℱ,ɛ)≔inf{{f∈ℱ:d2,z(f,fi)≤ɛ}l∈ℕ:∃{fi}i=1lsuchthatℱ=∪i=1l{f∈ℱ:d2,z(f,fi)≤ɛ}}.The function sets in our situation are balls ofℋ0 in the form of ℬR={f∈ℋ0:∥f∥≤R}. We need the l2-empirical covering number of ℬ1 defined as
(49)𝒩2(ℬ1,ɛ)≔supm∈ℕsupx∈Xm𝒩2,x(ℬ1,ɛ).
According to a bound for l2-empirical covering number derived in [32], we know that if K∈Cs(X×X), then
(50)log𝒩2(ℬ1,ɛ)≤cp(1ɛ)p,∀ɛ>0,
where cp is a constant independent of ɛ>0, and p∈(0,2) is a power index defined dy
(51)p={2n2n+s,when0<s≤1,2n2n+2,when1<s≤1+n2,ns,whens>1+n2.For a measurable functionf:Z→ℝ, denote 𝔼f≔∫Z‍f(z)dρ. The following definition is a variance-expectation condition for the pair (V,ρ), which is generally used to achieve tight bounds.Definition 16.
A variance powerα of the pair (V,ρ) is a number in [0,1] such that for any f:X→[-1,1], there exists some constant cα>0 satisfying
(52)𝔼[V(yf(x))-V(yfρV(x))]2≤cα[ℰ(f)-ℰ(fρV)]α.Remark 17.
It is easy to see that (52) always holds for α=0 and cα=V2(-1). Larger α is possible when V has strong convexity or ρ satisfies some noise condition (see [1, 5]).We are in a position to bound the sample error. WriteS(z,λ) as
(53)S(z,λ)={[ℰ(π(fz,λ))-ℰ(fρV)]-[ℰz(π(fz,λ))-ℰz(fρV)]}+{[ℰz(fλ)-ℰz(fρV)]-[ℰ(fλ)-ℰ(fρV)]}≔S1(z,λ)+S2(z,λ).
We will first bound S2(z,λ), and to this end we need the following one-side Bernstein inequality (see [33]).Letξ be a random variable on a probability space Z with mean 𝔼ξ=μ and variance σ2(ξ)=σ2. If |ξ-μ|≤B almost everywhere, then for all η>0(54)Probz∈Zm{1m∑i=1m‍ξ(zi)-μ≥η}≤exp{-mη22(σ2+(1/3)Bη)}.Proposition 18.
Suppose that classifying lossV satisfies (3). If (28) and (52) hold, then, for any 0<δ<1 with confidence 1-δ/4,
(55)S2(z,λ)≤C3log8δ((1m)1/(2-α)+λβ+λ(β-1)θm),
where C3 is a constant independent of λ, m, or δ.Proof.
Denoteξ1≔V(yfλ(x))-V(yπ(fλ)(x)), ξ2≔V(yπ(fλ)(x))-V(yfρV(x)). Then
(56)S2(z,λ)={1m∑i=1m‍ξ1(zi)-𝔼ξ1}+{1m∑i=1m‍ξ2(zi)-𝔼ξ2}.
By (22) and (26), we can see that
(57)∥fλ∥∞≤κ∥fλ∥≤κD(λ)λ.
We may assume |fλ(x)|>1, since otherwise ξ1=0. Then from (3), we can derive that
(58)0≤ξ1≤V(yfλ(x))≤cθ2θ(κD(λ)λ)θ,σ2(ξ1)≤cθ2θ(κD(λ)λ)θ𝔼ξ1.
Applying the one-side Bernstein inequality toξ1 we have, for any t>1 with confidence 1-e-t,
(59)1m∑i=1m‍ξ1(zi)-𝔼ξ1≤2cθ2θκθt3m(D(λ)λ)θ+2cθ2θκθtm(D(λ)λ)θ𝔼ξ1≤2cθ2θκθt3m(D(λ)λ)θ+cθ2θκθt2m(D(λ)λ)θ+𝔼ξ1=7cθ2θκθt6m(D(λ)λ)θ+𝔼ξ1.
On the other hand, bothπ(fλ)(x) and fρV(x) are contained in [-1,1], and we know from (3) and (52) that
(60)|ξ2|≤cθ2θ,σ2(ξ2)≤cα(𝔼ξ2)α.
Applying the one-side Bernstein inequality again, we have, with confidence 1-e-t,
(61)1m∑i=1m‍ξ2(zi)-𝔼ξ2≤4cθ2θt3m+2tcα(𝔼ξ2)αm≤4cθ2θt3m+α2𝔼ξ2+(1-α2)(2cαtm)1/(2-α)≤4cθ2θt3m+(2cαtm)1/(2-α)+𝔼ξ2,
where in the second inequality we have used the elementary inequality
(62)1ϱ+1ϱ*=1,withϱ,ϱ*>1⟹ab≤1ϱaϱ+1ϱ*bϱ*,∀a,b>0.
Since 𝔼ξ1+𝔼ξ2=ℰ(fλ)-ℰ(fρV)≤D(λ), combining the estimates above, we can get that, under assumption (28) with confidence 1-2e-t,
(63)S2(z,λ)≤7cθ2θκθcβθλ(β-1)θt6m+4cθ2θt3m+(2cαtm)1/(2-α)+cβλβ.
Then we prove the proposition by setting t=log(8/δ), and
(64)C3=7cθ2θκθcβθ6+4cθ2θ3+(2cα)1/(2-α)+cβ.It is more difficult to boundS1(z,λ), because it involves the samples z and thus runs over a set of functions. To get a better error estimation, An iteration technique is often used to shrink the radius of the ball containing fz,λ (see, e.g., [5, 12, 30, 32]); however this process is rather tough and complicated. In this paper We succeed to avoid the prolix iteration by considering the following reweighted empirical process
(65){ωr(f)[(ℰ(π(f))-ℰ(fρV))-(ℰz(π(f))-ℰz(fρV))]:f∈ℋ0[(ℰ(π(f))-ℰ(fρV))-(ℰz(π(f))-ℰz(fρV))]}.
Here ωr(f)=(r+ω(f))-1 for a threshold r>0 and ω(f)=ℰ(π(f))-ℰ(fρV)+λ∥f∥. Different from the classical weight function, ω(f) contains the regularization term λ∥f∥ and thus makes it possible to control the variances and ∥f∥ by the threshold r simultaneously.The following concentration inequality is a scaled version of Theorem  2.3 in [34], where the case B=1 is given.Lemma 19.
Assume thatz1,…,zm are identically distributed according to ρ. Let ℱ be a countable set of measurable functions from Z to [-B,B] and assume that all functions g in ℱ satisfy 𝔼g=0, σ2(g)≤σ2 for some positive real number σ. Denote
(66)ξ=supg∈ℱ|1m∑i=1m‍g(zi)|.
Then, for all t>0, one has
(67)Prob{ξ≥𝔼ξ+2t(σ2+2B𝔼ξ)m+Bt3m}≤e-t.This lemma allows us to take care of the deviation of the supremum of a empirical process with respect to its expectation.Proposition 20.
Letr≥0 and
(68)Φr≔supf∈ℋ0ωr(f)|[ℰ(π(f))-ℰ(fρV)]-[ℰz(π(f))-ℰz(fρV)]|.
If (3) and (52) are satisfied, then, for any t>0 with confidence 1-e-t,
(69)Φr≤2𝔼Φr+2tcαrα-2m+8cθ2θt3mr.Proof.
Before presenting the proof, let us first introduce some additional notations:(70)gf(z)≔V(yπ(f)(x))-V(yfρV(x)),hfr(z)≔ωr(f)[𝔼gf-gf(z)]=1𝔼gf+λ∥f∥+r[𝔼gf-gf(z)].
Then
(71)Φr=supf∈ℋ01m|∑i=1m‍hfr(zi)|.
By (3) and (52), we can see that
(72)|hfr(z)|≤2cθ2θr,σ2(hfr)≤𝔼(gf)2(𝔼gf+r)2≤cα(𝔼gf)α((2/α)𝔼gf)α((2/(2-α))r)2-α≤cαrα-2.
Here in the second inequality of (72), we have used the elementary inequality (62) again with ϱ=2/α,  a=(ϱ𝔼gf)1/ϱ and b=(ϱ*r)1/ϱ*. So applying Lemma 19 to Φr, we get with confidence 1-e-t(73)Φr≤𝔼Φr+2t(cαrα-2+(4cθ2θ𝔼Φr/r))m+2cθ2θt3mr≤𝔼Φr+2tcαrα-2m+8tcθ2θ𝔼Φrmr+2cθ2θt3mr≤2𝔼Φr+2tcαrα-2m+8cθ2θt3mr.So we can boundΦr through bounding its expectation. To this end, we need some preparations.Definition 21.
Let(Z,ρ) be a probability space, and ℱ is a class of measurable functions from Z to ℝ. Set {zi}i=1m to be m independent random variables distributed according to ρ and {ϵi}i=1m to be m independent Rademacher random variables. Then for η>0 the local Rademacher average of ℱ is defined by
(74)Rad(ℱ,m,η)≔𝔼supf∈ℱ𝔼f2≤η|1m∑i=1m‍ϵif(zi)|.The following lemma was given in [35].Lemma 22.
Letℱ be a class of measurable functions from Z to [-B,B]. If for some a>0 and p∈(0,2)(75)supm∈ℕsupz∈Zmlog𝒩2,z(ℱ,ɛ)≤aɛ-p,∀ɛ>0,
then there exists a constant cp′ depending only on p such that
(76)Rad(ℱ,m,η)≤cp′max{η1/2-p/4(am)1/2,B(2-p)/(2+p)(am)2/(2+p)}.Lemma 23.
Letz be a nonnegative stochastic process indexed by T and ω(t) a nonnegative nonrandom function defined on T. Define r*=inft∈Tω(t). Let ψ:[r*,+∞)→[0,+∞) be a function such that ψ(4r)≤4νψ(r) for some 0<ν<1, and
(77)𝔼[supt∈Tω(t)≤rz(t)]≤ψ(r),∀r≥r*.
Then, for any r≥r*, we have
(78)𝔼[supt∈Tz(t)ω(t)+r]≤(1+4ν1-4ν-1)ψ(r)r.Proof.
Forr≥r*, we obtain by a standard peeling approach
(79)supt∈Tz(t)ω(t)+r≤supt∈Tω(t)≤rz(t)r+∑i=0∞supt∈Tω(t)∈(4ir,4i+1r]z(t)4ir+r.
Therefore,
(80)𝔼[supt∈Tz(t)ω(t)+r]≤ψ(r)r+∑i=0∞‍ψ(4i+1r)(1+4i)r≤ψ(r)r+ψ(r)r∑i=0∞‍4(i+1)ν1+4i≤ψ(r)r(1+∑i=0∞‍4(ν-1)i+ν)=(1+4ν1-4ν-1)ψ(r)r.Now we can give a bound ofΦr.Proposition 24.
LetV be a classifying loss that satisfies (3), K∈Cs(X×X) with s>0, and p∈(0,2) given by (51). Under assumption (52), for any t>0 and r>0 satisfying
(81)r≥max{122[C4(1mλp)1/2]4/(2-p)(2-α),[C4(1mλp)2/(2+p)](2+p)/(2-p),(32tcαm)1/(2-α),cθ2θ+5t3m,D(λ)122},
where C4≔16(1+(4ν/(1-4ν-1)))cp′max{cα(2-p)/4(cp(cθ2θ-1)p)1/2, (cθ2θ)(2-p)/(2+p)(cp(cθ2θ-1)p)2/(2+p)} with ν=max{((2-p)α/4)+p/2,2p/(2+p)}. We have, with confidence 1-e-t,
(82)Φr≤34.Proof.
Using the notations in the proof of Proposition20, the weight function
(83)ω(f)=𝔼gf+λ∥f∥,r*≔inff∈ℋ0ω(f)=D(λ).
Hence r≥r*, and
(84)𝔼[supf∈ℋ0ω(f)≤r|𝔼gf-1m∑i=1m‍gf(zi)|]≤𝔼[supf∈ℬr/λ𝔼gf≤r|𝔼gf-1m∑i=1m‍gf(zi)|].
Denote 𝒢≔{gf:f∈ℬr/λ}. Standard symmetrization argument (see Lemma 2.3.1 of [36]) and Assumption (52) then yield
(85)𝔼[supf∈ℬr/λ𝔼gf≤r|𝔼gf-1m∑i=1m‍gf(zi)|]≤2Rad(𝒢,m,cαrα).
By (3) we know |gf(z)|≤cθ2θ, and
(86)|gf1(z)-gf2(z)|=|V(yπ(f1)(x))-V(yπ(f2)(x))|≤cθ2θ-1|π(f1)(x)-π(f2)(x)|≤cθ2θ-1|f1(x)-f2(x)|,
for any f1,f2∈ℬr/λ, so
(87)𝒩2,z(𝒢,ɛ)≤𝒩2,x(ℬr/λ,ɛcθ2θ-1)=𝒩2,x(ℬ1,ɛλcθ2θ-1r).
This together with (50) implies that
(88)supm∈ℕsupz∈Zmlog𝒩2,z(𝒢,ɛ)≤cp(cθ2θ-1)p(rλ)pɛ-p.
By Lemma 22, we obtain
(89)Rad(𝒢,m,cαrα)≤cp′max{cα1/2-p/4rα(1/2-p/4)(cp(cθ2θ-1)pm(rλ)p)1/2,(cθ2θ)(2-p)/(2+p)(cp(cθ2θ-1)pm(rλ)p)2/(2+p)}≔ψ(r)2.
Setting ν=max{((2-p)α/4)+p/2,2p/(2+p)}∈(0,1), it is easy to see ψ(4r)≤4νψ(r). So Lemma 23 tells us
(90)𝔼Φr=𝔼[supf∈ℋ0|𝔼gf-(1/m)∑i=1mgf(zi)|ω(f)+r]≤(1+4ν1-4ν-1)ψ(r)r.
By the choice of r, we can easily check that
(91)(1+4ν1-4ν-1)ψ(r)r≤18,2tcαrα-2m≤14,8cθ2θt3mr≤14.
Then the conclusion follows from Proposition 20.Corollary 25.
Under the condition of Proposition24, if (28) is satisfied, then for any 0<δ<1, with confidence 1-δ/4, there holds
(92)S1(z,λ)≤34[ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥]+C5log4δ[(1mλp)2/(2-p)(2-α)+(1mλp)2/(2-p)+(1m)1/(2-α)+λβ],
where C5 is a constant independent of λ, m, or δ.Proof.
Taking(93)r=[C4(1mλp)1/2]4/(2-p)(2-α)+[C4(1mλp)2/(2+p)](2+p)/(2-p)+(32tcαm)1/(2-α)+cθ2θ+5t3m+D(λ)
in Proposition 24, then, for any t>1 with confidence 1-e-t,
(94)ωr(fz,λ){[ℰ(π(fz,λ))-ℰ(fρV)]-[ℰz(π(fz,λ))-ℰz(fρV)]}≤Φr≤34.
It follows that
(95)S1(z,λ)≤34(ω(fz,λ)+r)=34[ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥]+34r.
Then the corollary is proved by setting t=log(4/δ), and
(96)C5≔34(cθ2θ+53C44/(2-p)(2-α)+C4(2+p)/(2-p)+(32cα)1/(2-α)+cθ2θ+53+cβ).


## 5. Deriving Learning Rates

We may now present the main results by combining the results obtained in the previous two sections. The following theorem gives the bounds for the excess generalization error.Theorem 26.
LetV be a classifying loss satisfying (3), K∈Cs(X×X) for some s∈ℕ, s≥2, and p∈(0,2) given by (51). Suppose that X satisfies an interior cone conditions, and ρX satisfies condition Lτ with some τ>0. If (28) is valid, then for any 0<δ<1 and m satisfying (44), by taking λ=m-γ with γ=min{s/τ(β+(1-β)θ),1/(β+(1-β)θ),2/(2-α)(2-p)β+2p}, we have, with confidence 1-δ,
(97)ℰ(π(fz,λ))-ℰ(fρV)≤C(log8δ+log(m+1))max{1,s/τ}(1m)γβ,
where C is a constant independent of m or δ.Proof.
Putting the estimates of Theorem14, Proposition 18, and Corollary 25 into the error decomposition (24), we see that, with confidence 1-δ,
(98)ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥≤C2(λβ+(λβ-1+λ(β-1)θ)(log(2/δ)+log(m+1)m)s/τ)+C3log8δ((1m)1/(2-α)+λβ+λ(β-1)θm)+34[ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥]+C5log4δ[(1mλp)2/(2-p)(2-α)+(1mλp)2/(2-p)+(1m)1/(2-α)+λβ].
Therefore, with the same confidence
(99)ℰ(π(fz,λ))-ℰ(fρV)≤ℰ(π(fz,λ))-ℰ(fρV)+λ∥fz,λ∥≤4(C2+C3+C5)(log8δ+log(m+1))max{1,s/τ}×[λβ+(1m)s/τ(λβ-1+λ(β-1)θ)+(1m)1/(2-α)+λ(β-1)θm+(1mλp)2/(2-p)(2-α)+(1mλp)2/(2-p)].
By the choice of λ, we can easily check that
(100)(1m)s/τλβ-1≤(1m)s/τλ(β-1)θ≤λβ,(1m)1/(2-α)≤λβ,λ(β-1)θm≤λβ,(1mλp)2/(2-p)(2-α)≤λβ,(1mλp)2/(2-p)≤λβ.
So our theorem follows by taking C=28(C2+C3+C5).Theorem26 together with (17) allows us to give an explicit learning rate for misclassification error of scheme (10).Corollary 27.
If the conditions in Theorem26 are satisfied, then for any 0<δ<1, with confidence 1-δ, there holds
(101)ℛ(sgn(fz,λ))-ℛ(fc)≤{C(log8δ+log(m+1))max{1,s/τ}(1m)γβifV(t)=(1-t)+,C~(log8δ+log(m+1))max{1/2,s/2τ}(1m)γβ/2ifV′′(0)≥0,
where C~≔cVC.Remark 28.
For the hinge lossVh(t)=(1-t)+, the increment exponent θ=1. If K∈C∞(X×X), then one can take s→∞ and p→0. This is the case for polynomial kernel (see [13, 14]) or Gaussian kernel (see [5, 15]), usually used in practice. So Corollary 27 tells us the learning rate of the 1-norm SVM is 𝒪(m-ς) with ς arbitrarily close to min{β,1/(2-α)}.



---

*Source: 496282-2013-11-17.xml*