Journal of Machine Learning Research ? (2004) ?-?? Submitted 9/03; Published ??/04

Support Vector Machine Soft Margin Classifiers: Error Analysis

Di-Rong Chen drchen@buaa.edu.cn Department of Applied Mathematics Beijing University of Aeronautics and Astronautics Beijing 100083, P. R. CHINA

Qiang Wu wu.qiang@student.cityu.edu.hk Yiming Ying ymying@cityu.edu.hk Ding-Xuan Zhou mazhou@math.cityu.edu.hk Department of Mathematics City University of Hong Kong Kowloon, Hong Kong, P. R. CHINA

Editor: Peter Bartlett

Abstract

The purpose of this paper is to provide a PAC error analysis for the q-norm soft margin classifier, a support vector machine classification algorithm. It consists of two parts: regularization error and sample error. While many techniques are available for treating the sample error, much less is known for the regularization error and the corresponding approximation error for reproducing kernel Hilbert spaces. We are mainly concerned about the regularization error. It is estimated for general distributions by a K-functional in weighted L^{q} spaces. For weakly separable distributions (i.e., the margin may be zero) satisfactory convergence rates are provided by means of separating functions. A projection operator is introduced, which leads to better sample error estimates especially for small complexity kernels. The misclassification error is bounded by the V -risk associated with a general class of loss functions V. The difficulty of bounding the offset is overcome. Polynomial kernels and Gaussian kernels are used to demonstrate the main results. The choice of the regularization parameter plays an important role in our analysis. Keywords: support vector machine classification, misclassification error, q-norm soft margin classifier, regularization error, approximation error

1. Introduction

In this paper we study support vector machine (SVM) classification algorithms and investigate the SVM q-norm soft margin classifier with 1 < q < ∞. Our purpose is to provide an error analysis for this algorithm in the PAC framework.

Let (X,d) be a compact metric space and Y = {1,−1}. A binary classifier f : X → {1,−1} is a function from X to Y which divides the input space X into two classes.

Let ρ be a probability distribution on Z := X × Y and (X ,Y) be the corresponding random variable. The misclassification error for a classifier f : X → Y is defined to be the probability of the event {f(X) ≠ Y }:

R (f) := Prob{f(X) ≠ Y } = ∫_{X}P(Y ≠ f(x)|x)dρ_{X}(x).  (1)

\begin{matrix}c \\ ◯ \end{matrix} 2004 Di-Rong Chen, Qiang Wu, Yiming Ying, and Ding-Xuan Zhou.

Chen, Wu, Ying, and Zhou

Here ρ_{X} is the marginal distribution on X and P(·|x) is the conditional probability measure given X = x.

The SVM q-norm soft margin classifier (Cortes & Vapnik 1995; Vapnik 1998) is constructed from samples and depends on a reproducing kernel Hilbert space associated with a Mercer kernel.

Let K : X ×X → ℝ be continuous, symmetric and positive semidefinite, i.e., for any finite set of distinct points {x_{1},··· ,x_{ℓ}} ⊂ X, the matrix (K(x_{i},x_{j}))_{i,j=1}^{ℓ} is positive semidefinite. Such a kernel is called a Mercer kernel.

The Reproducing Kernel Hilbert Space (RKHS) H_{K} associated with the kernel K is defined (Aronszajn, 1950) to be the closure of the linear span of the set of functions {K_{x}:= K(x,·) : x ∈ X} with the inner product ⟨·,·⟩_{H_{K}} = ⟨·,·⟩_{K} satisfying ⟨K_{x},K_{y}⟩_{K} = K(x,y) and

⟨K_{x},g⟩_{K} = g(x), ∀x ∈ X,g ∈ H_{K}.

Denote C(X) as the space of continuous functions on X with the norm ∥ · ∥_{∞}. Let κ := \sqrt{∥K∥_{∞}}. Then the above reproducing property tells us that

∥g∥_{∞} ≤ κ∥g∥_{K},  ∀g ∈ H_{K}.  (2)

Define \overline{H}_{K}:= H_{K}+ ℝ. For a function f = f_{1}+ b with f_{1} ∈ H_{K} and b ∈ ℝ, we denote f^{∗} = f_{1} and b_{f} = b ∈ ℝ. The constant term b is called the offset. For a function f : X → ℝ, the sign function is defined as sgn(f)(x) = 1 if f(x) ≥ 0 and sgn(f)(x) = −1 if f(x) < 0.

Now the SVM q-norm soft margin classifier (SVM q-classifier) associated with the Mercer kernel K is defined as sgn(f_{z}), where f_{z} is a minimizer of the following optimization problem involving a set of random samples z = (x_{i},y_{i})_{i=1}^{m} ∈ Z^{m} independently drawn according to ρ:

f_{z} := arg min_{f∈\overline{H}_{K}} \frac{1}{2}∥f^{∗}∥_{K}^{2}+ \frac{C}{m}∑_{i=1}^{m} ξ_{i}^{q},

subject to y_{i}f(x_{i}) ≥ 1 − ξ_{i}, and ξ_{i} ≥ 0 for i = 1,...,m.

(3)

Here C is a constant which depends on m: C = C(m), and often lim_{m→∞} C(m) = ∞.

Throughout the paper, we assume 1 < q < ∞, m ∈ ℕ, C > 0, and z = (x_{i},y_{i})_{i=1}^{m} are random samples independently drawn according to ρ. Our target is to understand how sgn(f_{z}) converges (with respect to the misclassification error) to the best classifier, the Bayes rule, as m and hence C(m) tend to infinity. Recall the regression function of ρ:

f_{ρ}(x) = ∫_{Y}ydρ(y|x) = P(Y = 1|x) − P(Y = −1|x),  x ∈ X.  (4)

Then the Bayes rule is given (e.g. Devroye, L. Györfi & G. Lugosi 1997) by the sign of the regression function f_{c} := sgn(f_{ρ}). Estimating the excess misclassification error

R (sgn(f_{z})) − R (f_{c})  (5)

for the classification algorithm (3) is our goal. In particular, we try to understand how the choice of the regularization parameter C affects the error.

To investigate the error bounds for general kernels, we rewrite (3) as a regularization scheme. Define the loss function V = V_{q} as

V (y,f(x)) := (1 − yf(x))_{+}^{q} = |y − f(x)|^{q}χ_{{yf(x)≤1}} ,  (6)

SVM Soft Margin Classifiers

where (t)_{+} = max{0,t}. The corresponding V -risk is

E(f) := E(V (y,f(x))) = ∫_{Z}V (y,f(x))dρ(x,y).  (7)

If we set the empirical error as

E_{z}(f) := \frac{1}{m}∑_{i=1}^{m} V (y_{i},f(x_{i})) = \frac{1}{m}∑_{i=1}^{m} (1 − y_{i}f(x_{i})) _{+}^{q} ,  (8)

then the scheme (3) can be written as (see Evgeniou, Pontil & Poggio 2000)

f_{z} = arg min_{f∈\overline{H}_{K}} \{ E_{z}(f) + \frac{1}{2C}∥f^{∗}∥_{K}^{2}\} .  (9)

Notice that when \overline{H}_{K} is replaced by H_{K}, the scheme (9) is exactly the Tikhonov regularization scheme (Tikhonov & Arsenin, 1977) associated with the loss function V. So one may hope that the method for analyzing regularization schemes can be applied.

The definitions of the V -risk (7) and the empirical error (8) tell us that for a function f = f^{∗}+b ∈ \overline{H}_{K}, the random variable ξ = V (y,f(x)) on Z has the mean E(f) and \frac{1}{m}∑ _{i=1}^{m} ξ(z_{i}) = E_{z}(f). Thus we may expect by some standard empirical risk minimization (ERM) argument (e.g. Cucker & Smale 2001, Evgeniou, Pontil & Poggio 2000, Shawe-Taylor et al. 1998, Vapnik 1998, Wahba 1990) to derive bounds for E(f_{z}) − E(f_{q}), where f_{q} is a minimizer of the V -risk (7). It was shown in Lin (2002) that for q > 1 such a minimizer is given by

f_{q}(x) = \frac{(1 + f_{ρ}(x))^{1/(q−1)} − (1 − f_{ρ}(x))^{1/(q−1)}}{(1 + f_{ρ}(x))^{1/(q−1)} + (1 − f_{ρ}(x))^{1/(q−1)}} ,  x ∈ X.  (10)

For q = 1 a minimizer is f_{c}, see Wahba (1999). Note that sgn(f_{q}) = f_{c}.

Recall that for the classification algorithm (3), we are interested in the excess misclassification error (5), not the excess V -risk E(f_{z}) − E(f_{q}). But we shall see in Section 3 that R (sgn(f)) − R (f_{c}) ≤ \sqrt{2(E(f) − E(f_{q}))} . One might apply this to the function f_{z} and get estimates for (5). However, special features of the loss function (6) enable us to do better: by restricting f_{z} onto [−1,1], we can improve the sample error estimates. The idea of the following projection operator was introduced for this purpose in Bartlett (1998).

Definition 1 The projection operator π is defined on the space of measurable functions f : X → ℝ as

π(f)(x) = \{ \begin{matrix}1, & iff(x) ≥ 1, \\ −1, & iff(x) ≤ −1, \\ f(x), & if − 1 < f(x) < 1. \end{matrix}  (11)

It is trivial that sgn(π(f)) = sgn(f). Hence

R (sgn(f_{z})) − R (f_{c}) ≤ \sqrt{2(E(π(f_{z})) − E(f_{q}))} .  (12)

The definition of the loss function (6) also tells us that V (y,π(f)(x)) ≤ V (y,f(x)), so

E(π(f)) ≤ E(f)  and E_{z}(π(f)) ≤ E_{z}(f).  (13)

According to (12), we need to estimate E(π(f_{z}))−E(f_{q}) in order to bound (5). To this end, we introduce a regularizing function f_{K,C}∈ \overline{H}_{K}. It is arbitrarily chosen and depends on C.

Proposition 2 Let f_{K,C}∈ \overline{H}_{K}, and f_{z} be defined by (9). Then E(π(f_{z}))−E(f_{q}) can be bounded by

\{ E(f_{K,C}) − E(f_{q}) + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}\} + \{ E(π(f_{z})) − E_{z}(π(f_{z})) + E_{z}(f_{K,C}) − E(f_{K,C})\} .  (14)

Proof Decompose the difference E(π(f_{z})) − E(f_{q}) as

\{E(π(f_{z})) − E_{z}(π(f_{z}))\} + \{ ( E_{z}(π(f_{z})) + \frac{1}{2C}∥f_{z}^{∗}∥_{K}^{2}) − ( E_{z}(f_{K,C}) + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}) \}

+\{E_{z}(f_{K,C}) − E(f_{K,C})\} + \{ E(f_{K,C}) − E(f_{q}) + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}\} − \frac{1}{2C}∥f_{z}^{∗}∥_{K}^{2}.

By the definition of f_{z} and (13), the second term is ≤ 0. Then the statement follows.

The first term in (14) is called the regularization error (Smale & Zhou 2004). It can be expressed as a generalized K-functional inf_{f∈\overline{H}_{K}} \{E(f) − E(f_{q}) + \frac{1}{2C}∥f^{∗}∥_{K}^{2}\} when f_{K,C} takes a special choice

f̃_{K,C} (a standard choice in the literature, e.g. Steinwart 2001) defined as

f̃_{K,C} := arg min_{f∈\overline{H}_{K}} \{ E(f) + \frac{1}{2C}∥f^{∗}∥_{K}^{2}\} .  (15)

Definition 3 Let V be a general loss function and f_{ρ}^{V} be a minimizer of the V -risk (7). The regularization error for the regularizing function f_{K,C}∈ \overline{H}_{K} is defined as

D(C) := E(f_{K,C}) − E(f_{ρ}^{V}) + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}.  (16)

It is called the regularization error of the scheme (9) when f_{K,C}= f̃_{K,C}:

D̃(C) := inf_{f∈\overline{H}_{K}} \{ E(f) − E(f_{ρ}^{V}) + \frac{1}{2C}∥f^{∗}∥_{K}^{2}\} .

The main concern of this paper is the regularization error. We shall investigate its asymptotic behavior. This investigation is not only important for bounding the first term in (14), but also crucial for bounding the second term (sample error): it is well known in structural risk minimization (Shawe-Taylor et al. 1998) that the size of the hypothesis space is essential. This is determined by D(C) in our setting. Once C is fixed, the sample error estimate becomes routine. Therefore, we need to understand the choice of the parameter C from the bound for D(C).

Proposition 4 For any C ≥ 1/2 and any f_{K,C}∈ \overline{H}_{K}, there holds

D(C) ≥ D̃(C) ≥ \frac{κ̃^{2}}{2C}  (17)

where

κ̃ := E_{0}/(1 + κq4^{q−1} ),  E_{0} := inf_{b∈ℝ}{E(b) − E(f_{q})}.  (18)

Moreover, κ̃ = 0 if and only if for some p_{0} ∈ [0,1], P(Y = 1|x) = p_{0} in probability.

This proposition will be proved in Section 5.

According to Proposition 4, the decay of D(C) cannot be faster than O(1/C) except for some very special distributions. This special case is caused by the offset in (9), for which D̃(C) ≡ 0. Throughout this paper we shall ignore this trivial case and assume κ̃ > 0.

When ρ is strictly separable, D(C) = O(1/C). But this is a very special phenomenon. In general, one should not expect E(f) = E(f_{q}) for some f ∈ \overline{H}_{K}. Even for (weakly) separable distributions with zero margin, D(C) decays as O(C^{−p} ) for some 0 < p < 1. To realize such a decay for these separable distributions, the regularizing function will be multiples of a separating function. For details and the concepts of strictly or weakly separable distributions, see Section 2.

For general distributions, we shall choose f_{K,C}= f̃_{K,C} in Sections 6 and 7 and estimate the regularization error of the scheme (9) associated with the loss function (6) by means of the approximation in the function space L_{ρ_{X}}^{q}. In particular, D̃(C) ≤ K (f_{q}, \frac{1}{2C}), where K (f_{q},t) is a K-functional defined as

K (f_{q},t) := \{ \begin{matrix}inf_{f∈\overline{H}_{K}} \{∥f − f_{q}∥_{L_{ρ_{X}}^{q}}^{q} + t∥f^{∗}∥_{K}^{2}\} , & if 1 < q ≤ 2, \\ inf_{f∈\overline{H}_{K}} \{q2^{q−1} (2^{q−1} + 1)∥f − f_{q}∥_{L_{ρ_{X}}^{q}} + t∥f^{∗}∥_{K}^{2}\} , & if q > 2. \end{matrix}  (19)

In the case q = 1, the regularization error (Wu & Zhou, 2004) depends on the approximation in L_{ρ_{X}}^{1} of the function f_{c} which is not continuous in general. For q > 1, the regularization error depends on the approximation in L_{ρ_{X}}^{q} of the function f_{q}. When the regression function has good smoothness, f_{q} has much higher regularity than f_{c}. Hence the convergence for q > 1 may be faster than that for q = 1, which improves the regularization error.

The second term in (14) is called the sample error. When C is fixed, the sample error E(f_{z}) − E_{z}(f_{z}) is well understood (except for the offset term). In (14), the sample error is for the function π(f_{z}) instead of f_{z} while the misclassification error (5) is kept: R (sgn(π(f_{z})))= R (sgn(f_{z})). Since the bound for V (y,π(f)(x)) is much smaller than that for V (y,f(x)), the projection improves the sample error estimate.

Based on estimates for the regularization error and sample error above, our error analysis will provide ε(δ,m,C,β) > 0 for any 0 < δ < 1 such that with confidence 1 − δ,

E(π(f_{z})) − E(f_{q}) ≤ (1 + β){D(C) + ε(δ,m,C,β)}.  (20)

Here 0 < β ≤ 1 is an arbitrarily fixed number. Moreover, lim_{m→∞} ε(δ,m,C,β) = 0.

If f_{q} lies in the L_{ρ_{X}}^{q}-closure of \overline{H}_{K}, then lim_{t→0}K (f_{q},t) = 0 by (19). Hence E(π(f_{z}))−E(f_{q}) → 0

with confidence as m (and hence C = C(m)) becomes large. This is the case when K is a universal kernel, i.e., H_{K} is dense in C(X), or when a sequence of kernels whose RKHS tends to be dense (e.g. polynomial kernels with increasing degrees) is used.

In summary, estimating the excess misclassification error R (sgn(f_{z})) − R (f_{c}) consists of three parts: the comparison (12), the regularization error D(C) and the sample error ε(δ,m,C,β) in (20). As functions of the variable C, D(C) decreases while ε(δ,m,C,β) usually increases. Choosing suitable values for the regularization parameter C will give the optimal convergence rate. To this end, we need to consider the tradeoff between these two errors. This can be done by minimizing the right side of (20), as shown in the following form.

Lemma 5 Let p,α,τ > 0. Denote c_{p,α,τ} := (p/τ)^{\frac{τ}{τ+p}} + (τ/p)^{\frac{p}{τ+p}} . Then for any C > 0,

C^{−p} + \frac{C^{τ}}{m^{α}} ≥ c_{p,α,τ}( \frac{1}{m}) ^{\frac{αp}{τ+p}} .  (21)

The equality holds if and only if C = (p/τ)^{\frac{1}{τ+p}} m^{\frac{α}{τ+p}} . This yields the optimal power \frac{αp}{τ+p} .

The goal of the regularization error estimates is to have p in D(C) = O(C^{−p} ), as large as possible. But p ≤ 1 according to Proposition 4. Good methods for sample error estimates provide large α and small τ such that ε(δ,m,C,β) = O(\frac{C^{τ}}{m^{α}}). Notice that, as always, both the approximation properties (represented by the exponent p) and the estimation properties (represented by the exponents τ and α) are important to get good estimates for the learning rates (with the optimal rate \frac{αp}{τ+p} ).

2. Demonstrating with Weakly Separable Distributions

With some special cases let us demonstrate how our error analysis yields some guidelines for choosing the regularization parameter C. For weakly separable distributions, we also compare our results with bounds in the literature. To this end, we need the covering number of the unit ball B := {f ∈ H_{K}: ∥f∥_{K} ≤ 1} of H_{K} (considered as a subset of C(X)).

Definition 6 For a subset F of a metric space and η > 0, the covering number N (F ,η) is defined to be the minimal integer ℓ ∈ ℕ such that there exist ℓ disks with radius η covering F.

Denote the covering number of B in C(X) by N (B,η). Recall the constant κ̃ defined in (18). Since the algorithm involves an offset term, we also need its covering number and set

N (η) := \{(κ + \frac{1}{κ̃})\frac{1}{η} + 1\}N (B,η).  (22)

Definition 7 We say that the Mercer kernel K has logarithmic complexity exponent s ≥ 1 if for some c > 0, there holds

logN (η) ≤ c(log(1/η))^{s},  ∀η > 0.  (23)

The kernel K has polynomial complexity exponent s > 0 if

logN (η) ≤ c(1/η)^{s},  ∀η > 0.  (24)

The covering number N (B,η) has been extensively studied (see e.g. Bartlett 1998, Williamson, Smola & Schölkopf 2001, Zhou 2002, Zhou 2003a). In particular, for convolution type kernels K(x,y) = k(x − y) with k̂≥ 0 decaying exponentially fast, (23) holds (Zhou 2002, Theorem 3). As an example, consider the Gaussian kernel K(x,y) = exp{−|x − y|^{2}/σ^{2}} with σ > 0. If X ⊂ [0,1]^{n} and 0 < η ≤ exp{90n^{2}/σ^{2}−11n−3}, then (23) is valid (Zhou 2002) with s = n+1. A lower bound (Zhou 2003a) holds with s = \frac{n}{2}, which shows the upper bound is almost sharp. It was also shown in (Zhou 2003a) that K has polynomial complexity exponent 2n/p if K is C^{p}.

To demonstrate our main results concerning the regularization parameter C, we shall only choose kernels having logarithmic complexity exponents or having polynomial complexity exponents with s small. This means, \overline{H}_{K} has small complexity.

The special case we consider here is the deterministic case: R (f_{c}) = 0. Understanding how to find D(C) and ε(δ,m,C,β) in (20) and then how to choose the parameter C is our target. For M ≥ 0, denote

θ_{M} = \{ \begin{matrix}0, & if M = 0, \\ 1, & if M > 0. \end{matrix}  (25)

Proposition 8 Suppose R (f_{c}) = 0. If f_{K,C}∈ \overline{H}_{K} satisfies ∥V (y,f_{K,C}(x))∥_{∞} ≤ M, then for every 0 < δ < 1, with confidence at least 1 − δ, we have

R (sgn(f_{z})) ≤ 2max\{ ε^{∗}, \frac{4M log(2/δ)}{m}\} + 4D(C),  (26)

where with M := \sqrt{2CD(C) + 2Cεθ_{M}}, ε^{∗} > 0 is the unique solution to the equation

logN ( \frac{ε}{q2^{q+3} M} ) − \frac{3mε}{2^{q+9}} = log(δ/2).  (27)

(a) If (23) is valid, then with c̃= 2^{q+9} {1 + c((q + 4)log8)^{s}},

ε^{∗} ≤ c̃( \frac{(logm + log(CD(C))+ log(Cθ_{M}))^{s}+ log(2/δ)}{m} ) .

(b) If (24) is valid and C ≥ 1, then with a constant c̃ (given explicitly in the proof),

ε^{∗} ≤ c̃log(2/δ)\{ \frac{(2CD(C))^{s/(2s+2)}}{m^{1/(s+1)}} + \frac{(2C)^{s/(s+2)}}{m^{1/( \frac{s}{2}+1)}} \} .  (28)

Note that the above constant c̃ depends on c,q, and κ, but not on C, m or δ. The proof of Proposition 8 will be given in Section 5.

We can now derive our error bound for weakly separable distributions.

Definition 9 We say that ρ is (weakly) separable by \overline{H}_{K} if there is a function fsp ∈ \overline{H}_{K}, called a separating function, satisfying ∥fsp^{∗}∥_{K} = 1 and yfsp(x) > 0 almost everywhere. It has separation exponent θ ∈ (0,+∞] if there are positive constants γ,c′such that

ρ_{X}{x ∈ X : |fsp(x)| < γt} ≤ c′t^{θ},  ∀ t > 0.  (29)

Observe that condition (29) with θ = +∞ is equivalent to

ρ_{X}{x ∈ X : |fsp(x)| < γt} = 0, ∀ 0 < t < 1.

That is, |fsp(x)| ≥ γ almost everywhere. Thus, weakly separable distributions with separation exponent θ = +∞ are exactly strictly separable distributions. Recall (e.g. Vapnik 1998, Shawe-Taylor et al. 1998) that ρ is said to be strictly separable by \overline{H}_{K} with margin γ > 0 if ρ is (weakly) separable together with the requirement yfsp(x) ≥ γ almost everywhere.

¿From the first part of Definition 9, we know that for a separable distribution ρ, the set {x : fsp(x) = 0} has ρ_{X}-measure zero, hence

lim_{t→0}ρ_{X}{x ∈ X : |fsp(x)| < t} = 0.

The separation exponent θ measures the asymptotic behavior of ρ near the boundary of two classes. It gives the convergence with a polynomial decay.

Theorem 10 If ρ is separable and has separation exponent θ ∈ (0,+∞] with (29) valid, then for every 0 < δ < 1, with confidence at least 1 − δ, we have

R (sgn(f_{z})) ≤ 2ε^{∗}+ \frac{8log(2/δ)}{m} + 4(2c′)^{\frac{2}{θ+2}} (Cγ^{2})^{− \frac{θ}{θ+2}} ,  (30)

where ε^{∗} is solved by

logN ( \frac{ε}{q2^{q+3} \sqrt{2(2c′)^{\frac{2}{θ+2}} γ^{− \frac{2θ}{θ+2}} C^{\frac{2}{θ+2}} + 2Cε}}) − \frac{3mε}{2^{q+9}} = log(δ/2).  (31)

(a) If (23) is satisfied, with a constant c̃ depending on γ we have

R (sgn(f_{z})) ≤ c̃( \frac{log(2/δ) + (logm + logC)^{s}}{m} + C^{− \frac{θ}{θ+2}} ) .  (32)

(b) If (24) is satisfied, there holds

R (sgn(f_{z})) ≤ c̃\{ log \frac{2}{δ}( C^{\frac{s}{(s+1)(θ+2)}} m^{− \frac{1}{s+1}} + C^{\frac{s}{s+2}} m^{− \frac{1}{s/2+1}} ) + C^{− \frac{θ}{θ+2}} \} .  (33)

Proof Choose t = (\frac{γ^{θ}}{2c′C})^{1/(θ+2)} > 0 and the function f_{K,C}= \frac{1}{t}fsp ∈ \overline{H}_{K}. Then we have \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}= \frac{1}{2Ct^{2}}.

Since yfsp(x) > 0 almost everywhere, we know that for almost every x ∈ X, y = sgn(fsp)(x). This means f_{ρ} = sgn(fsp) and then f_{q} = sgn(fsp). It follows that R (f_{c}) = 0 and V (y,f_{K,C}(x)) =

(1 − \frac{|fsp(x)|}{t})_{+}^{q} ∈ [0,1] almost everywhere. Therefore, we may take M = 1 in Proposition 8. Moreover,

E(f_{K,C}) = ∫_{Z}( 1 − \frac{yfsp(x)}{t}) _{+}^{q} dρ = ∫_{X}( 1 − \frac{|fsp(x)|}{t}) _{+}^{q} dρ_{X}.

This can be bounded by (29) as

∫_{\{x:|fsp(x)|<t\}}( 1 − \frac{|fsp(x)|}{t}) _{+}^{q} dρ_{X} ≤ ρ_{X}\{x ∈ X : |fsp(x)| < t\} ≤ c′( \frac{t}{γ})^{θ}.

It follows from the choice of t that

D(C) ≤ c′( \frac{t}{γ})^{θ}+ \frac{1}{2Ct^{2}}= (2c′)^{\frac{2}{θ+2}} (Cγ^{2})^{− \frac{θ}{θ+2}} .  (34)

Then our conclusion follows from Proposition 8.

In case (a), the bound (32) tells us to choose C such that (logC)^{s}/m → 0 and C → ∞ as m → ∞. By (32) a reasonable choice of the regularization parameter C is C = m^{\frac{θ+2}{θ}} , which yields R (sgn(f_{z})) = O(\frac{(logm)^{s}}{m}). In case (b),

when (24) is valid, C = m^{\frac{θ+2}{θ+s+θs}} =⇒ R (sgn(f_{z})) = O(m^{− \frac{θ}{θ+s+θs}} ).  (35)

The following is a typical example of separable distribution which is not strictly separable. In this example, the separation exponent is θ = 1.

Example 1 Let X = [−1/2,1/2] and ρ be the Borel probability measure on Z such that ρ_{X} is the Lebesgue measure on X and

f_{ρ}(x) = \{ \begin{matrix}1, & for − 1/2 ≤ x ≤ −1/4 and 1/4 ≤ x ≤ 1/2, \\ −1, & for − 1/4 ≤ x < 1/4. \end{matrix}

(a) If K is the linear polynomial kernel K(x,y) = x · y, then R (sgn(f_{z})) − R (f_{c}) ≥ 1/4.

(b) If K is the quadratic polynomial kernel K(x,y) = (x · y)^{2}, then with confidence 1 − δ,

R (sgn(f_{z})) ≤ \frac{q(q + 4)2^{q+11} (logm + logC + 2log(2/δ))}{m} + \frac{16}{C^{1/3}}.

Hence one should take C such that logC/m → 0 and C → ∞ as m → ∞.

Proof The first statement is trivial.

To see (b), we note that dimH_{K} = 1 and κ = 1/4. Also, E_{0} = inf_{b∈ℝ}E(b) = 1. Hence κ̃ =

1/(1 + q4^{q−2} ). Since H_{K} = {ax^{2} : a ∈ ℝ} and ∥ax^{2}∥_{K} = |a|, N (B,η) ≤ 1/(2η). Then (23) holds with s = 1 and c = 4q. By Proposition 8, we see that ε^{∗} ≤ \frac{q(q+4)2^{q+11} (log(Cm)+log(2/δ))}{m} .

Take the function fsp(x) = x^{2}− 1/16 ∈ \overline{H}_{K} with ∥fsp^{∗}∥_{K} = 1. We see that yfsp(x) > 0 almost everywhere. Moreover,

\{x ∈ X : |fsp(x)| < t\} ⊆ [ \frac{\sqrt{1 − 16t}}{4} , \frac{\sqrt{1 + 16t}}{4} ] ⋃ [−\frac{\sqrt{1 + 16t}}{4} ,−\frac{\sqrt{1 − 16t}}{4} ].

The measure of this set is bounded by 8\sqrt{2}t. Hence (29) holds with θ = 1, γ = 1 and c′= 8\sqrt{2}. Then Theorem 10 gives the stated bound for R (sgn(f_{z})).

In this paper, for the sample error estimates we only use the (uniform) covering numbers in C(X). Within the last a few years, the empirical covering numbers (in ℓ^{∞} or ℓ^{2}), the leave-one-out error or stability analysis (e.g. Vapnik 1998, Bousquet & Ellisseeff 2002, Zhang 2004), and some other advanced empirical process techniques such as the local Rademacher averages (van der Vaart & Wellner 1996, Bartlett, Bousquet & Mendelson 2004, and references therein) and the entropy integrals (van der Vaart & Wellner, 1996) have been developed to get better sample error estimates. These techniques can be applied to various learning algorithms. They are powerful to handle general hypothesis spaces even with large capacity.

In Zhang (2004) the leave-one-out technique was applied to improve the sample error estimates given in Bousquet & Ellisseeff (2002): the sample error has a kernel-independent bound O(\frac{C}{m}), improving the bound O(\frac{C}{\sqrt{m}}) in Bousquet & Ellisseeff (2002); while the regularization error D̃(C) depends on K and ρ. In particular, for q = 2 the bound (Zhang 2004, Corollary 4.2) takes the form:

E(E(f_{z})) ≤ ( 1 + \frac{4κ^{2}C}{m})^{2} inf_{f∈H_{K}} \{E(f) + \frac{1}{2C}∥f∥_{K}^{2}\} = ( 1 + \frac{4κ^{2}C}{m})^{2}\{ D̃(C) + E(f_{q})\}.  (36)

In Bartlett, Jordan & McAuliffe (2003) the empirical process techniques are used to improve the sample error estimates for ERM. In particular, Theorem 12 there states that for a convex set F of functions on X, the minimizer f̂ of the empirical error over F satisfies

E(f̂) ≤ inf_{f∈F} E(f) + K max\{ ε^{∗},( \frac{c_{r}L^{2}log(1/δ)}{m})^{1/(2−β)} , \frac{BLlog(1/δ)}{m}\} .  (37)

Here K,c_{r},β are constants, and ε^{∗} is solved by an inequality. The constant B is a bound for differences, and L is the Lipschitz constant for the loss ϕ with respect to a pseudometric on ℝ. For more details, see Bartlett, Jordan & McAuliffe (2003). The definitions of B and L together tell us that

|ϕ(y_{1}f(x_{1})) − ϕ(y_{2}f(x_{2}))| ≤ LB,  ∀ (x_{1},y_{1}) ∈ Z,(x_{2},y_{2}) ∈ Z,f ∈ F .  (38)

Because of our improvement for the bound of the random variables V (y,f(x)) given by the projection operator, for the algorithm (3) the error bounds we derive here are better than existing results when the kernel has small complexity. Let us confirm this for separable distributions with separation exponent 0 < θ < ∞ and for kernels with polynomial complexity exponent s > 0 satisfying (24). Recall that D(C) = O(C^{− \frac{θ}{θ+2}} ). Take q = 2.

Consider the estimate (36). This together with (34) tells us that the derived bound for E(E(f_{z})−

E(f_{q})) is at least of the order D̃(C)+ \frac{C}{m}D̃(C) = O(C^{− \frac{θ}{θ+2}} + \frac{C^{\frac{2}{θ+2}}}{m} ). By Lemma 5, the optimal bound derived from (36) is O(m^{− \frac{θ}{θ+2}} ). Thus, our bound (35) is better than (36) when 0 < s < \frac{2}{θ+1} .

Turn to the estimate (37). Take F to be the ball of radius \sqrt{2CD̃(C)}of H_{K} (the expected

smallest ball where f_{z}^{∗} lies), we find that the constant LB in (38) should be at least κ\sqrt{2CD̃(C)}.

This tells us that one term in the bound (37) for the sample error is at least O( ^{\frac{\sqrt{2CD̃(C)}}{m}}) = O(\frac{C^{\frac{1}{θ+2}}}{m} ), while the other two terms are more involved. Applying Lemma 5 again, we find that the bound derived from (37) is at least O(m^{− \frac{θ}{θ+1}} ). So our bound (35) is better than (37) at least for 0 < s < \frac{1}{θ+1} .

Thus, our analysis with the help of the projection operator improves existing error bounds when the kernel has small complexity. Note that in (35), the values of s for which the projection operator gives an improvement are values corresponding to rapidly diminishing regularization (C = m^{β} with β > 1 being large).

For kernels with large complexity, refined empirical process techniques (e.g. van der Vaart & Wellner 1996, Mendelson 2002, Zhang 2004, Bartlett, Jordan & McAuliffe 2003) should give better bounds: the capacity of the hypothesis space may have more influence on the sample error than the bound of the random variable V (y,f(x)), and the entropy integral is powerful to reduce this influence. To find the range of this large complexity, one needs explicit rate analysis for both the sample error and regularization error. This is out of our scope. It would be interesting to get better error bounds by combining the ideas of empirical process techniques and the projection operator.

Problem 11 How much improvement can we get for the total error when we apply the projection operator to empirical process techniques?

Problem 12 Given θ > 0,s > 0,q ≥ 1, and 0 < δ < 1, what is the largest number α > 0 such that R (sgn(f_{z})) = O(m^{−α} ) with confidence 1 − δ whenever the distribution ρ is separable with separation exponent θ and the kernel K satisfies (24)? What is the corresponding optimal choice of the regularization parameter C?

In particular, for Example 1 we have the following.

Conjecture 13 In Example 1, with confidence 1−δ there holds R (sgn(f_{z})) = O(\frac{log(2/δ)}{m}) by choosing C = m^{3}.

Consider the well known setting (Vapnik 1998, Shawe-Taylor et al. 1998, Steinwart 2001, Cristianini & Shawe-Taylor 2000) of strictly separable distributions with margin γ > 0. In this case, Shawe-Taylor et al. (1998) shows that

R (sgn(f)) ≤ \frac{2}{m}(logN (F ,2m,γ/2) + log(2/δ))  (39)

with confidence 1 − δ for m > 2/γ whenever f ∈ F satisfies y_{i}f(x_{i}) ≥ γ. Here F is a function set, N (F ,2m,γ/2) = sup_{t⃗∈X^{2m}}N (F ,t⃗,γ/2) and N (F ,t⃗,γ/2) denotes the covering number of the set

{(f(t_{i}))_{i=1}^{2m} : f ∈ F } in ℝ^{2m} with the ℓ^{∞} metric. For a comparison of this covering number with that in C(X), see Pontil (2003).

In our analysis, we can take f_{K,C}= \frac{1}{γ}fsp ∈ \overline{H}_{K}. Then M = ∥V (y,f_{K,C}(x))∥_{∞} = 0, and D(C) =

\frac{1}{2Cγ^{2}}. We see from Proposition 8 (a) that when (23) is satisfied, there holds R (f_{z}) ≤ c̃(\frac{(log(1/γ)+logm)^{s}+log(1/δ)}{m} ). But the optimal bound O(\frac{1}{m}) is also valid for spaces with larger complexity, which can be seen from

(39) by the relation of the covering numbers: N (F ,2m,γ/2) ≤ N (F ,γ/2). See also Steinwart (2001). We see the shortcoming of our approach for kernels with large complexity. This convinces the interest of Problem 11 raised above.

3. Comparison of Errors

In this section we consider how to bound the misclassification error by the V -risk. A systematic study of this problem was done for convex loss functions by Zhang (2004), and for more general loss functions by Bartlett, Jordan, and McAuliffe (2003). Using these results, it can be shown that for the loss function V_{q}, there holds

ψ( R (sgn(f)) − R (f_{c})) ≤ E(f) − E(f_{q}),

where ψ : [0,1] → ℝ_{+} is a function defined in Bartlett, Jordan, and McAuliffe (2003) and can be explicitly computed.

In fact, we have

R (sgn(f)) − R (f_{c}) ≤ c\sqrt{E(f) − E(f_{q})} .  (40)

Such a comparison of errors holds true even for a general convex loss function, see Theorem 34 in Appendix. The derived bound for the constant c in (40) need not be optimal. In the following we shall give an optimal estimate in a simpler form.

The constant we derive depends on q and is given by

C_{q} = \{ \begin{matrix}1, & if 1 ≤ q ≤ 2, \\ 2(q − 1)/q, & if q > 2. \end{matrix}  (41)

We can see that C_{q} ≤ 2.

Theorem 14 Let f : X → ℝ be measurable. Then

R (sgn(f)) − R (f_{c}) ≤ \sqrt{C_{q}(E(f) − E(f_{q}))} ≤ \sqrt{2(E(f) − E(f_{q}))} .

Proof By the definition, only points with sgn(f)(x) ≠ f_{c}(x) are involved for the misclassification error. Hence

R (sgn(f)) − R (f_{c}) = ∫_{X}|f_{ρ}(x)|χ_{{sgn(f)(x)≠sgn(f_{q})(x)}} dρ_{X}.  (42)

This in connection with the Schwartz inequality implies that

R (sgn(f)) − R (f_{c}) ≤ { ∫_{X}|f_{ρ}(x)|^{2}χ_{{sgn(f)(x)≠sgn(f_{q})(x)}} dρ_{X}} ^{1/2}.

Thus it is sufficient to show for those x ∈ X with sgn(f)(x) ≠ sgn(f_{q})(x),

|f_{ρ}(x)|^{2} ≤ C_{q}(E(f|x) − E(f_{q}|x)) ,  (43)

where for x ∈ X, we have denoted

E(f|x) := ∫_{Y}V_{q}(y,f(x))dρ(y|x).  (44)

By the definition of the loss function V_{q}, we have

E(f|x) = (1 − f(x))_{+}^{q} \frac{1 + f_{ρ}(x)}{2} + (1 + f(x))_{+}^{q} \frac{1 − f_{ρ}(x)}{2} .  (45)

It follows that

E(f|x) − E(f_{q}|x) = ∫_{0}^{f(x)−f_{q}(x)} F (u)du,  (46)

where F (u) is the function (depending on the parameter f_{ρ}(x)):

F (u) = \frac{1 − f_{ρ}(x)}{2} q(1 + f_{q}(x) + u)_{+}^{q−1} − \frac{1 + f_{ρ}(x)}{2} q(1 − f_{q}(x) − u)_{+}^{q−1} , u ∈ ℝ.

Since F (u) is nondecreasing and F (0) = 0, we see from (46) that when sgn(f)(x) ≠ sgn(f_{q})(x), there holds

E(f|x) − E(f_{q}|x) ≥ ∫_{0}^{−f_{q}(x)} F (u)du = E(0|x) − E(f_{q}|x) = 1 − E(f_{q}|x).  (47)

But

E(f_{q}|x) = \frac{2^{q−1} (1 − |f_{ρ}(x)|^{2})}{\{(1 + f_{ρ}(x))^{1/(q−1)} + (1 − f_{ρ}(x))^{1/(q−1)} \} ^{q−1}} .  (48)

Therefore, (43) is valid (with t = f_{ρ}(x)) once the following inequality is verified:

\frac{t^{2}}{C_{q}} ≤ 1 − \frac{2^{q−1} (1 − t^{2})}{\{(1 + t)^{1/(q−1)} + (1 − t)^{1/(q−1)} \} ^{q−1}} , t ∈ [−1,1].

This is the same as the inequality

( 1 − \frac{t^{2}}{C_{q}}) ^{−1/(q−1)} ≤ \frac{(1 + t)^{−1/(q−1)} + (1 − t)^{−1/(q−1)}}{2} ,  t ∈ [−1,1].  (49)

To prove (49), we use the Taylor expansion

(1 + u)^{α} = ∑_{k=0}^{∞} ( \begin{matrix}α \\ k \end{matrix}) u^{k} = ∑_{k=0}^{∞} \frac{∏ _{ℓ=0}^{k−1}(α − ℓ)}{k!} u^{k}, u ∈ (−1,1).

With α = −1/(q − 1), we have

( 1 − \frac{t^{2}}{C_{q}}) ^{−1/(q−1)} = ∑_{k=0}^{∞} \frac{∏ _{ℓ=0}^{k−1} ( \frac{1}{q−1} + ℓ)}{k!} \frac{1}{C_{q}^{k}} t^{2k}

and (all the odd power terms vanish)

\frac{(1 + t)^{−1/(q−1)} + (1 − t)^{−1/(q−1)}}{2} = ∑_{k=0}^{∞} \frac{∏ _{ℓ=0}^{k−1} ( \frac{1}{q−1} + ℓ)}{k!} ( ∏_{ℓ=0}^{k−1} \frac{\frac{1}{q−1} + ℓ + k}{1 + ℓ + k} ) t^{2k}.

Note that

∏_{ℓ=0}^{k−1} \frac{\frac{1}{q−1} + ℓ + k}{1 + ℓ + k} ≥ \frac{1}{C_{q}^{k}}.

This proves (49) and hence our conclusion.

When R (f_{c}) = 0, the estimate in Theorem 14 can be improved (Zhang 2004, Bartlett, Jordan & McAuliffe 2003) to

R (sgn(f)) ≤ E(f).  (50)

In fact, R (f_{c}) = 0 implies |f_{ρ}(x)| = 1 almost everywhere. This in connection with (48) and (47) gives E(f_{q}|x) = 0 and E(f|x) ≥ 1 when sgn(f)(x) ≠ f_{c}(x). Then (43) can be improved to the form |f_{ρ}(x)| ≤ E(f|x). Hence (50) follows from (42).

Theorem 14 tells us that the misclassification error can be bounded by the V -risk associated with the loss function V. So our next step is to study the convergence of the q-classifier with respect to the V -risk E.

4. Bounding the Offset

If the offset b is fixed in the scheme (3), the sample error can be bounded by standard argument using some measurements of the capacity of the RKHS. However, the offset is part of the optimization problem and even its boundedness can not be seen from the definition. This makes our setting here essentially different from the standard Tikhonov regularization scheme. The difficulty of bounding the offset b has been realized in the literature (e.g. Steinwart 2002, Bousquet & Ellisseeff 2002). In this paper we shall overcome this difficulty by means of special features of the loss function V.

The difficulty raised by the offset can also be seen from the stability analysis (Bousquet & Ellisseeff 2002). As shown in Bousquet & Ellisseeff (2002), the SVM 1-norm classifier without the offset is uniformly stable, meaning that sup_{z∈Z^{m},z′_{0}∈Z} ∥V (y,f_{z}(x)) − V (y,f_{z′}(x))∥_{L^{∞}} ≤ β_{m} with β_{m} → 0

as m → ∞, and z′is the same as z except that one element of z is replaced by z′_{0}.

The SVM 1-norm classifier with the offset is not uniformly stable. To see this, we choose x_{0} ∈ X and samples z = {(x_{0},y_{i})}_{i=1}^{2n+1} with y_{i} = 1 for i = 1,...,n+1, and y_{i} = −1 for i = n+2,...,2n+1.

Take z′_{0} = (x_{0},−1). As x_{i} are identical, one can see from the definition (9) that f_{z}^{∗} = 0 (since E_{z}(f_{z}) = E_{z}(b_{z} + f_{z}(x_{0}))). It follows that f_{z} = 1 while f_{z′} = −1. Thus, |f_{z} − f_{z′}| = 2 which does not converge to zero as m = 2n + 1 tends to infinity. It is unknown whether the q-norm classifier is uniformly stable for q > 1.

How to bound the offset is the main goal of this section. In Wu & Zhou (2004) a direct computation is used to realize this point for q = 1. Here the index q > 1 makes a direct computation very difficult, and we shall use two bounds to overcome this difficulty. By x ∈ (X,ρ_{X}) we mean that x lies in the support of the measure ρ_{X} on X.

Lemma 15 For any C > 0,m ∈ ℕ and z ∈ Z^{m}, a minimizer of (9) satisfies

min_{1≤i≤m} f_{z}(x_{i}) ≤ 1 and max_{1≤i≤m} f_{z}(x_{i}) ≥ −1  (51)

and a minimizer of (15) satisfies

inf_{x∈(X,ρ_{X})}f̃_{K,C}(x) ≤ 1 and sup_{x∈(X,ρ_{X})}f̃_{K,C}(x) ≥ −1.  (52)

Proof Suppose a minimizer of (9) f_{z} satisfies r := min_{1≤i≤m} f_{z}(x_{i}) > 1. Then f_{z}(x_{i}) − (r − 1) ≥ 1 for

each i. We claim that

y_{i} = 1, ∀i = 1,...,m.

In fact, if the set I := {i ∈ {1,...,m}: y_{i} = −1} is not empty, we have

E_{z}(f_{z}− (r − 1)) = \frac{1}{m}∑_{i∈I} (1 + f_{z}(x_{i}) − (r − 1)) ^{q} < \frac{1}{m}∑_{i∈I} (1 + f_{z}(x_{i})) ^{q} = E_{z}(f_{z}),

which is a contradiction to the definition of f_{z}. Hence our claim is verified. From the claim we see that E_{z}(f_{z} − (r − 1)) = 0 = E_{z}(f_{z}). This tells us that f̃_{z} := f_{z} − (r − 1) is a minimizer of (9) satisfying the first inequality, hence both inequalities of (51).

In the same way, if a minimizer of (9) f_{z} satisfies r := max_{1≤i≤m} f_{z}(x_{i}) < −1. Then we can see

that y_{i} = −1 for each i. Hence E_{z}(f_{z} − r − 1) = E_{z}(f_{z}) and f̃_{z} := f_{z} − r − 1 is a minimizer of (9) satisfying the second inequality and hence both inequalities of (51).

Therefore, we can always find a minimizer of (9) satisfying (51).

We prove the second statement in the same way. Suppose r := inf_{x∈(X,ρ_{X})}f̃_{K,C}(x) > 1 for a mini-

mizer f̃_{K,C} of (15). Then f̃_{K,C}(x) − (r − 1) ≥ 1 for almost every x ∈ (X,ρ_{X}). Hence

E ( f̃_{K,C}− (r − 1)) = ∫_{X}( 1 + f̃_{K,C}(x) − (r − 1)) ^{q}P(Y = −1|x)dρ_{X} ≤ E(f̃_{K,C}).

As f_{K,C}is a minimizer of (15), the above equality must hold. It follows that P(Y = −1|x) = 0 for almost every x ∈ (X,ρ_{X}). Hence F̃_{K,C}:= f̃_{K,C}− (r − 1) is a minimizer of (15) satisfying the first inequality and thereby both inequalities of (52).

Similarly, when r := sup_{x∈(X,ρ_{X})}f̃_{K,C}(x) < −1 for a minimizer f̃_{K,C} of (15). Then P(Y = 1|x) = 0

for almost every x ∈ (X,ρ_{X}). Hence F̃_{K,C}:= f_{K,C}−r −1 is a minimizer of (15) satisfying the second inequality and thereby both inequalities of (52).

Thus, (52) can always be realized by a minimizer of (15).

In what follows we always choose f_{z} and f̃_{K,C} to satisfy (51) and (52), respectively.

Lemma 15 yields bounds for the H_{K}-norm and offset for f_{z} and f̃_{K,C}. Denote bf̃_{K,C} as b̃_{K,C}.

Lemma 16 For any C > 0,m ∈ ℕ,f_{K,C}∈ \overline{H}_{K}, and z ∈ Z^{m}, there hold

(a) ∥f̃_{K,C}^{∗}∥_{K} ≤ \sqrt{2CD̃(C)}≤ \sqrt{2C}, |b̃_{K,C}| ≤ 1 + ∥f̃_{K,C}^{∗}∥_{∞} .

(b) ∥f̃_{K,C}∥_{∞} ≤ 1 + 2κ\sqrt{2CD̃(C)}≤ 1 + 2κ\sqrt{2C}, E(f̃_{K,C}) ≤ E(f_{q}) + D̃(C) ≤ 1.

(c) |b_{z}| ≤ 1 + κ∥f_{z}^{∗}∥_{K}.

Proof By the definition (15), we see from the choice f = 0 + 0 that

D̃(C) = E(f̃_{K,C}) − E(f_{q}) + \frac{1}{2C}∥f̃_{K,C}^{∗}∥_{K}^{2} ≤ 1 − E(f_{q}).  (53)

Then the first inequality in (a) follows.

Note that (52) gives

−1 ≤ sup_{x∈(X,ρ_{X})}f̃_{K,C} ≤ b̃_{K,C}+ ∥f̃_{K,C}^{∗}∥_{∞}

and

b̃_{K,C}− ∥f̃_{K,C}^{∗}∥_{∞} ≤ inf_{x∈(X,ρ_{X})}f̃_{K,C} ≤ 1.

Thus, |b̃_{K,C}| ≤ 1 + ∥f̃_{K,C}^{∗}∥_{∞}. This proves the second inequality in (a).

Since the first inequality in (a) and (2) lead to ∥f̃_{K,C}^{∗}∥_{∞} ≤ κ\sqrt{2CD̃(C)}, we obtain ∥f̃_{K,C}∥_{∞} ≤

1 + 2∥f̃_{K,C}^{∗}∥_{∞} ≤ 1 + 2κ\sqrt{2CD̃(C)}. Hence the first inequality in (b) holds.

The second inequality in (b) is an easy consequence of (53).

The inequality in (c) follows from (51) in the same way as the proof of the second inequality in (a).

5. Convergence of the q-norm Soft Margin Classifier

In this section, we apply the ERM technique to analyze the convergence of the q-classifier for q > 1. The situation here is more complicated than that for q = 1. We need the following lemma concerning q > 1.

Lemma 17 For q > 1, there holds

|(x)_{+}^{q} − (y)_{+}^{q} | ≤ q(max{x,y})_{+}^{q−1} |x − y|, ∀x,y ∈ ℝ.

If y ∈ [−1,1], then

|(1 − x)_{+}^{q} − (1 − y)_{+}^{q} | ≤ q4^{q−1} |x − y| + q2^{q−1} |x − y|^{q}, ∀x ∈ ℝ.

Proof We only need to prove the first inequality for x > y. This is trivial:

(x)_{+}^{q} − (y)_{+}^{q} = ∫_{y}^{x}q(u)_{+}^{q−1} du ≤ q(x)_{+}^{q−1} (x − y).

If y ∈ [−1,1], then 1 − y ≥ 0 and the first inequality yields

|(1 − x)_{+}^{q} − (1 − y)_{+}^{q} | ≤ q(max{1 − x,1 − y}) _{+}^{q−1} |x − y|.  (54)

When x ≥ 2y − 1, we have

|(1 − x)_{+}^{q} − (1 − y)_{+}^{q} | ≤ q2^{q−1} (1 − y)^{q−1} |x − y| ≤ q4^{q−1} |x − y|.

When x < 2y−1, we have 1−x < 2(y−x) and x < 1. This in combination with max{1−x,1−y} ≤ max{1 − x,2} and (54) implies

|(1 − x)_{+}^{q} − (1 − y)_{+}^{q} | ≤ q{(1 − x)^{q−1} + 2^{q−1} }|x − y| ≤ q2^{q−1} |x − y|^{q}+ q2^{q−1} |x − y|.

This proves Lemma 17.

The second part of Lemma 17 will be used in Section 6. The first part can be used to verify Proposition 4.

Proof of Proposition 4. It is trivial that D(C) ≥ D̃(C). To show the second inequality, apply the first inequality of Lemma 17 to the two numbers 1 − yf̃_{K,C}(x) and 1 − yb̃_{K,C}. We see that

(1 − yf̃_{K,C}(x))_{+}^{q} ≥ (1 − yb̃_{K,C})_{+}^{q} − q(1 + |f̃_{K,C}(x)| + |b̃_{K,C}|)^{q−1} |f̃_{K,C}^{∗}(x)|.

Notice that |f̃_{K,C}^{∗}(x)| ≤ κ∥f̃_{K,C}^{∗}∥_{K} and by Lemma 16, |b̃_{K,C}| ≤ 1 + κ∥f̃_{K,C}^{∗}∥_{K}. Hence

E(f̃_{K,C}) ≥ E(b̃_{K,C}) − κq2^{q−1} (1 + κ∥f̃_{K,C}^{∗}∥_{K})^{q−1} ∥f̃_{K,C}^{∗}∥_{K}.

It follows that when ∥f̃_{K,C}^{∗}∥_{K} ≤ κ̃, we have

E(f̃_{K,C}) − E(f_{q}) ≥ E_{0}− κq2^{q−1} (1 + κκ̃)^{q−1} κ̃.

Since E_{0} ≤ 1, the definition (18) of κ̃ yields κ̃ ≤ 1/(1 + κ) ≤ min{1,1/κ}. Hence

D̃(C) ≥ E(f̃_{K,C}) − E(f_{q}) ≥ E_{0}− κq4^{q−1} κ̃ = κ̃ ≥ κ̃^{2}.

As C ≥ 1/2, we conclude (17) in this case.

When ∥f̃_{K,C}^{∗}∥_{K} > κ̃, we also have

D̃(C) ≥ \frac{1}{2C}∥f̃_{K,C}^{∗}∥_{K}^{2} ≥ \frac{κ̃^{2}}{2C}.

Thus in both case we have verified (17).

Note that κ̃ = 0 if and only if E_{0} = 0. This means for some b′_{0} ∈ [−1,1], f_{q}(x) = b′_{0} in probability. By the definition of f_{q}, the last assertion of Proposition 4 follows.

The loss function V is not Lipschitz, but Lemma 17 enables us to derive a bound for E(π(f_{z}))− E_{z}(π(f_{z})) with confidence, as done for Lipschitz loss functions in Mukherjee, Rifkin & Poggio (2002). Since the function π(f_{z}) changes and lies in a set of functions, we shall compare the error with the empirical error for functions from a set

F := {π(f) : f ∈ B_{R}+ [−B,B]} .  (55)

Here B_{R}= {f^{∗} ∈ H_{K}: ∥f^{∗}∥_{K} ≤ R} and the constant B is a bound for the offset.

The following probability inequality was motivated by sample error estimates for the square loss (Barron 1990, Bartlett 1998, Cucker & Smale 2001, Lee, Bartlett & Williamson 1998) and will be used in our estimates.

Lemma 18 Suppose a random variable ξ satisfies 0 ≤ ξ ≤ M, and z = (z_{i})_{i=1}^{m} are independent samples. Let μ = E(ξ). Then for every ε > 0 and 0 < α ≤ 1, there holds

Prob_{z∈Z^{m}} \{ \frac{μ − \frac{1}{m}∑ _{i=1}^{m} ξ(z_{i})}{\sqrt{μ + ε}} ≥ α\sqrt{ε}\} ≤ exp\{ −\frac{3α^{2}mε}{8M}\} .

Proof As ξ satisfies |ξ − μ| ≤ M, the one-side Bernstein inequality tells us that

Prob_{z∈Z^{m}} \{ \frac{μ − \frac{1}{m}∑ _{i=1}^{m} ξ(z_{i})}{\sqrt{μ + ε}} ≥ α\sqrt{ε}\} ≤ exp\{ −\frac{α^{2}m(μ + ε)ε}{2(σ^{2}+ \frac{1}{3}Mα\sqrt{μ + ε} \sqrt{ε})} \} .

Here σ^{2} ≤ E(ξ^{2}) ≤ ME(ξ) = Mμ since 0 ≤ ξ ≤ M. Then we find that

σ^{2}+ \frac{1}{3}Mα\sqrt{μ + ε} \sqrt{ε}≤ Mμ + \frac{1}{3}M(μ + ε) ≤ \frac{4}{3}M(μ + ε).

This yields the desired inequality.

Now we can turn to the error bound involving a function set. Lemma 17 yields the following bounds concerning the loss function V:

|E_{z}(f) − E_{z}(g)| ≤ qmax{(1 + ∥f∥_{∞}) ^{q−1} ,(1 + ∥g∥_{∞}) ^{q−1} } ∥f − g∥_{∞}  (56)

and

|E(f) − E(g)| ≤ qmax{(1 + ∥f∥_{∞}) ^{q−1} ,(1 + ∥g∥_{∞}) ^{q−1} } ∥f − g∥_{∞} .  (57)

Lemma 19 Let F be a subset of C(X) such that ∥f∥_{∞} ≤ 1 for each f ∈ F. Then for every ε > 0 and 0 < α ≤ 1, we have

Prob_{z∈Z^{m}} \{ sup_{f∈F} \frac{E(f) − E_{z}(f)}{\sqrt{E(f) + ε}} ≥ 4α\sqrt{ε}\} ≤ N ( F , \frac{αε}{q2^{q−1}} ) exp\{ −\frac{3α^{2}mε}{2^{q+3}}\} .

Proof Let \{f_{j}\}_{j=1}^{J} ⊂ F with J = N ( F , \frac{αε}{q2^{q−1}} ) such that F is covered by balls centered at f_{j} with radius \frac{αε}{q2^{q−1}} . Note that ξ = V (y,f(x)) satisfies 0 ≤ ξ ≤ (1 + ∥f∥_{∞}) ^{q} ≤ 2^{q} for f ∈ F. Then for each j, Lemma 18 tells

Prob_{z∈Z^{m}} \{ \frac{E(f_{j}) − E_{z}(f_{j})}{\sqrt{E(f_{j}) + ε}} ≥ α\sqrt{ε}\} ≤ exp\{ −\frac{3α^{2}mε}{8 · 2^{q}}\} .

For each f ∈ F, there is some j such that ∥f − f_{j}∥_{∞} ≤ \frac{αε}{q2^{q−1}} . This in connection with (56) and (57) tells us that |E_{z}(f) − E_{z}(f_{j})| and |E(f) − E(f_{j})| are both bounded by αε. Hence

\frac{|E_{z}(f) − E_{z}(f_{j})|}{\sqrt{E(f) + ε}} ≤ α\sqrt{ε}  and  \frac{|E(f) − E(f_{j})|}{\sqrt{E(f) + ε}} ≤ α\sqrt{ε}.

The latter implies that \sqrt{E(f_{j}) + ε} ≤ 2\sqrt{E(f) + ε} . Therefore,

Prob_{z∈Z^{m}} \{ sup_{f∈F} \frac{E(f) − E_{z}(f)}{\sqrt{E(f) + ε}} ≥ 4α\sqrt{ε}\} ≤ ∑_{j=1}^{J} Prob\{ \frac{E(f_{j}) − E_{z}(f_{j})}{\sqrt{E(f_{j}) + ε}} ≥ α\sqrt{ε}\}

which is bounded by J · exp\{−\frac{3α^{2}mε}{2^{q+3}}\} .

Take F to be the set (55). The following covering number estimate will be used.

Lemma 20 Let F be given by (55) with R ≥ κ̃ and B = 1 + κR. Its covering number in C(X) can be bounded as follows:

N (F ,η) ≤ N ( \frac{η}{2R}) , ∀η > 0.

Proof It follows from the fact ∥π(f) − π(g)∥_{∞} ≤ ∥f − g∥_{∞} that

N (F ,η) ≤ N (B_{R}+ [−B,B],η) .

The latter is bounded by \{(κ + \frac{1}{κ̃})\frac{2R}{η}+ 1\}N (B_{R}, \frac{η}{2}) since \frac{2B}{η} ≤ (κ + \frac{1}{κ̃})\frac{2R}{η} and

∥(f^{∗}+ b_{f}) − (g^{∗}+ b_{g})∥_{∞} ≤ ∥f^{∗}− g^{∗}∥_{∞} + |b_{f} − b_{g}|.

Note that an \frac{η}{2R}-covering of B is the same as an \frac{η}{2}-covering of B_{R}. Then our conclusion follows from Definition 6.

We are in a position to state our main result on the error analysis. Recall θ_{M} in (25).

Theorem 21 Let f_{K,C}∈ \overline{H}_{K}, M ≥ ∥V (y,f_{K,C}(x))∥_{∞} , and 0 < β ≤ 1. For every ε > 0, we have

E(π(f_{z})) − E(f_{q}) ≤ (1 + β)(ε + D(C))

with confidence at least 1 − F (ε) where F : ℝ_{+} → ℝ_{+} is defined by

F (ε) := exp\{ −\frac{mε^{2}}{2M(Δ + ε)} \} + N ( \frac{β(ε + D(C))^{3/2}}{q2^{q+3} Σ} ) exp\{ −\frac{3mβ^{2}(D(C) + ε)^{2}}{2^{q+9} (Δ + ε)}\}  (58)

with Δ := D(C) + E(f_{q}) and Σ := \sqrt{2C(Δ + ε)(Δ + θ_{M}ε)} .

Proof Let ε > 0. We prove our conclusion in three steps.

Step 1: Estimate E_{z}(f_{K,C}) − E(f_{K,C}).

Consider the random variable ξ = V (y,f_{K,C}(x)) with 0 ≤ ξ ≤ M. If M > 0, since σ^{2}(ξ) ≤ ME(f_{K,C}) ≤ M(D(C)+E(f_{q})), by the one-side Bernstein inequality we obtain E_{z}(f_{K,C})−E(f_{K,C}) ≤ ε with confidence at least

1 − exp\{ −\frac{mε^{2}}{2(σ^{2}(ξ) + \frac{1}{3}Mε)} \} ≥ 1 − exp\{ −\frac{mε^{2}}{2M(Δ + ε)} \} .

If M = 0, then ξ = 0 almost everywhere. Hence E_{z}(f_{K,C}) − E(f_{K,C}) = 0 with probability 1. Thus, in both cases, there exists U_{1} ∈ Z^{m} with measure at least 1 − exp\{−\frac{mε^{2}}{2M(ε+Δ)} \} such that E_{z}(f_{K,C}) − E(f_{K,C}) ≤ θ_{M}ε whenever z ∈ U_{1}.

Step 2: Estimate E(π(f_{z})) − E_{z}(π(f_{z})).

Let F be given by (55) with R = \sqrt{2C (Δ + θ_{M}ε)} and B = 1 + κR. By Proposition 4, R ≥ \sqrt{2CD(C)}≥ κ̃. Applying Lemma 19 to F with ε̃:= D(C) + ε > 0 and α = \frac{β}{8} \sqrt{ε̃/(ε̃+ E(f_{q}))} ∈ (0,1/8], we have

E(f) − E_{z}(f) ≤ 4α\sqrt{ε̃}\sqrt{E(f) − E(f_{q}) + ε̃+ E(f_{q})} ,  ∀f ∈ F  (59)

for z ∈ U_{2} where U_{2} is a subset of Z^{m} with measure at least

1 − N ( F , \frac{αε̃}{q2^{q−1}} ) exp\{ − \frac{3mα^{2}ε̃}{2^{q+3}}\} ≥ 1 − N ( \frac{β(ε + D(C))^{3/2}}{q2^{q+3} Σ} ) exp\{ − \frac{3mβ^{2}(D(C) + ε)^{2}}{2^{q+9} (Δ + ε)}\} .

In the above inequality we have used Lemma 20 to bound the covering number.

For z ∈ U_{1}∩ U_{2}, we have

\frac{1}{2C}∥f_{z}^{∗}∥_{K}^{2} ≤ E_{z}(f_{K,C}) + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2} ≤ E(f_{K,C}) + θ_{M}ε + \frac{1}{2C}∥f_{K,C}^{∗}∥_{K}^{2}

which equals to D(C)+θ_{M}ε+E(f_{q}) = Δ+θ_{M}ε. It follows that ∥f_{z}^{∗}∥_{K}≤ R. By Lemma 16, |b_{z}| ≤ B. This means, π(f_{z}) ∈ F and (59) is valid for f = π(f_{z}).

Step 3: Bound E(π(f_{z})) − E(f_{q}) using (14).

Let α and ε̃be the same as in Step 2. For z ∈ U_{1}⋂ U_{2}, both E_{z}(f_{K,C}) − E(f_{K,C}) ≤ θ_{M}ε ≤ ε and (59) with f = π(f_{z}) hold true. Then (14) tells us that

E(π(f_{z})) − E(f_{q}) ≤ 4α\sqrt{ε̃}\sqrt{(E(π(f_{z})) − E(f_{q})) + ε̃+ E(f_{q})} + ε̃.

Denote r:= E(π(f_{z})) − E(f_{q}) + ε̃+ E(f_{q}) > 0, we see that

r ≤ ε̃+ E(f_{q}) + 4α\sqrt{ε̃}\sqrt{r}+ ε̃.

It follows that

\sqrt{r} ≤ 2α\sqrt{ε̃}+ \sqrt{4α^{2}ε̃+ 2ε̃+ E(f_{q})} .

Hence

E(π(f_{z})) − E(f_{q}) = r − (ε̃+ E(f_{q})) ≤ ε̃+ 8α^{2}ε̃+ 4αε̃\sqrt{4α^{2}+ 2 + E(f_{q})/ε̃} .

Putting the choice of α into above, we find that

E(π(f_{z})) − E(f_{q}) ≤ ε̃+ \frac{β^{2}ε̃^{2}}{8(ε̃+ E(f_{q}))} + \frac{βε̃}{2}\sqrt{\frac{ε̃}{ε̃+ E(f_{q})}} \sqrt{\frac{β^{2}ε̃}{16(ε̃+ E(f_{q}))} + 2 + \frac{E(f_{q})}{ε̃}}

which is bounded by (1 + β)ε̃= (1 + β)(ε + D(C)).

Finally, noting that the measure of U_{1}⋂ U_{2} is at least 1 − F (ε), the proof is finished.

Observe that the function F is strictly decreasing and F (0) > 1, lim_{ε→∞}F (ε) = 0. Hence for every 0 < δ < 1 there exists a unique number ε > 0 satisfying F (ε) = δ. Also, for a fixed ε > 0, F (ε) < δ for sufficiently large m, since F (ε) can be written as a^{m}+cb^{m}with 0 < a,b < 1. Therefore, Theorem 21 can be restated in the following form.

Corollary 22 Let F be given in Theorem 21. For every 0 < δ < 1, define ε(δ,m,C,β) > 0 to be the unique solution to the equation F (ε) = δ. Then with confidence at least 1−δ, (20) holds. Moreover,

lim_{m→∞} ε(δ,m,C,β) = 0.

Now we can prove the statements we made in Section 2 for the deterministic case.

Proof of Proposition 8. Take β = 1. Since R (f_{c}) = 0, we know that f_{q} = f_{c}, E(f_{q}) = 0 and Δ = D(C). Then Σ ≤ \sqrt{2C(D(C) + θ_{M}ε)}\sqrt{D(C) + ε} and

N ( \frac{β(ε + D(C))^{3/2}}{q2^{q+3} Σ} ) ≤ N ( \frac{ε}{q2^{q+3} M} ) .

The function value F (ε) can be bounded by

exp\{ −\frac{mε^{2}}{2M(D(C) + ε)}\} + N ( \frac{ε}{q2^{q+3} M} ) exp\{ −\frac{3mε}{2^{q+9}}\} .

The first term above is bounded by δ/2 when ε ≥ \frac{4M log(2/δ)}{m} + D(C). The second term is at most δ/2 if ε ≥ ε^{∗}. Therefore

ε(δ,m,C,β) ≤ max\{ \frac{4M log(2/δ)}{m}+ D(C),ε^{∗}\} ,

and (26) follows from Theorem 21.

(a) When (23) holds, noting that the left side of (27) is strictly decreasing, it is easy to check that

ε^{∗} ≤ 2^{q+9} \{ 1 + c((q + 4)log8)^{s}\} \frac{(logm + log(CD(C))+ log(Cθ_{M}))^{s}+ log(2/δ)}{m} .

This yields the stated bound for ε^{∗} in the case (a).

(b) If (24) is true, then the function defined by

F̃(ε) := c\frac{(q2^{q+4} )^{s}\{(2CD(C))^{s/2}+ (2Cε)^{s/2}\}}{ε^{s}}− \frac{3mε}{2^{q+9}}

satisfies F̃(ε^{∗}) ≥ log(δ/2). Since F̃ is a decreasing function, ε^{∗} ≤ ε̃^{∗} whenever F̃(ε̃^{∗}) ≤ log(δ/2). If ε̃^{∗} ≥ rm^{−1/(s+1)} (2CD(C))^{s/(2s+2)} log \frac{2}{δ} with

r ≥ 2^{q+8} κ̃^{−s/(s+1)} + q2^{q+10} c^{1/(s+1)} /log2,  (60)

then

c(q2^{q+4} )^{s} \frac{(2CD(C))^{s/2}}{(ε̃^{∗})^{s}}− \frac{mε̃^{∗}}{2^{q+8}} ≤ \frac{rm^{s/(s+1)}}{2^{q+8}} (2CD(C))^{\frac{s}{2s+2}} log \frac{2}{δ}\{ \frac{c(q2^{q+4} )^{s}2^{q+8}}{(r log(2/δ))^{s+1}} − 1\} .

Since r ≥ q2^{q+10} c^{1/(s+1)} /log2, according to Proposition 4, this can be bounded by

\frac{r}{2^{q+8}} m^{s/(s+1)} (2CD(C))^{s/(2s+2)} log \frac{2}{δ}\{ −\frac{1}{2}\} ≤ \frac{r}{2^{q+9}} κ̃^{s/(s+1)} log \frac{δ}{2} ≤ \frac{1}{2} log \frac{δ}{2}.

Here we have used the condition r ≥ 2^{q+8} κ̃^{−s/(s+1)} .

In the same way, if ε̃^{∗} ≥ rm^{−2/(s+2)} (2C)^{s/(s+2)} log \frac{2}{δ} with

r ≥ 2^{q+9} + q^{2}4^{q+5} c^{2/(s+2)} /log2,  (61)

we have for C ≥ 1/2,

c(q2^{q+4} )^{s}( \frac{2C}{ε̃^{∗}}) ^{s/2}− \frac{mε̃^{∗}}{2^{q+9}} ≤ \frac{1}{2} log \frac{δ}{2}.

Combining the above two bounds, we obtain the desired estimate (28) with c̃ determined by the two conditions (60) and (61). The proof of Proposition 8 is complete.

In the general case, the following bounds hold.

Corollary 23 For every 0 < δ ≤ 1, with confidence at least 1 − δ there holds

E(π(f_{z}))− E(f_{q}) ≤ 2max\{ \frac{2^{q+1} ( 1 + κ\sqrt{2CD̃(C)}) ^{q/2}\sqrt{log(2/δ)}}{\sqrt{m}} ,ε^{∗}\} + 2D̃(C),

where ε^{∗} is the solution to the equation

logN ( \frac{ε^{3/2}}{q4^{q+2} \sqrt{2C}}) − \frac{3mε^{2}}{4^{q+5}} = log \frac{δ}{2}.  (62)

Proof Take β = 1 and f_{K,C}= f̃_{K,C}. By Lemma 16, ∥f̃_{K,C}∥_{∞} ≤ 1 + 2κ\sqrt{2CD̃(C)}and we can take

M = 2^{q}(1 + κ\sqrt{2CD̃(C)})^{q}. Also, Δ = D̃(C) + E(f_{q}) ≤ 1. It follows that Σ ≤ \sqrt{2C}(Δ + ε) ≤ \sqrt{2C}(1 + ε).

Since E(π(f_{z})) ≤ 2^{q}, we only need to consider the range ε ≤ 2^{q} to bound ε(δ,m,C,β). In this range,

N ( \frac{β(ε + D̃(C))^{3/2}}{q2^{q+3} Σ} ) ≤ N ( \frac{ε^{3/2}}{q4^{q+2} \sqrt{2C}}) .

Then F (ε) can be bounded by

exp\{ −\frac{mε^{2}}{4^{q+1} (1 + κ\sqrt{2CD̃(C)})^{q}} \} + N ( \frac{ε^{3/2}}{q4^{q+2} \sqrt{2C}}) exp\{ −\frac{3mε^{2}}{4^{q+5}}\} .

Thus F (ε) ≤ δ if

ε ≥ max\{ \frac{2^{q+1} (1 + κ\sqrt{2CD̃(C)})^{q/2}\sqrt{log(2/δ)}}{\sqrt{m}} ,ε^{∗}\}

where ε^{∗} is the solution to the equation (62). This together with Theorem 21 yields the desired estimate.

The bound for the sample error derived in Corollary 23 may be further improved by the well developed empirical process techniques in the literature. We shall discuss this elsewhere.

The total error (14) consists of two parts. We shall not discuss the possibility of further improving the sample error bound here, because it is of the same importance to understand the regularization error. This becomes more important when not much estimate is available for the regularization error. In the previous sections, we could compute D(C) explicitly only for special cases. Most of the time, ρ is not strictly separable, even not weakly separable. Hence it is desirable to estimate D(C) explicitly for general distributions. In the following we shall choose f_{K,C}= f̃_{K,C} and estimate D̃(C).

6. Error Analysis by Approximation in L^{q} Spaces

The main result on the convergence analysis given in Section 5 enables us to have some nice observations. These follow from facts on approximation in L^{q} spaces.

Lemma 24 If 1 < q ≤ 2, then

(1 + u)_{+}^{q} ≤ 1 + |u|^{q}+ qu, ∀u ∈ ℝ.

Proof Set the continuous function f(u) := 1 + |u|^{q}+ qu − (1 + u)_{+}^{q}. Then f(0) = 0.

Since 0 < q − 1 ≤ 1, for u > 0 we have

f′(u) = q(1 + u^{q−1} − (1 + u)^{q−1} ) ≥ 0.

Hence f(u) ≥ 0 for u ≥ 0.

For −1 < u < 0, we see that

f′(u) = q(1 − (−u)^{q−1} − (1 + u)^{q−1} ) = q(1 − |u|^{q−1} − (1 − |u|)^{q−1} ) ≤ 0.

Hence f(u) ≥ 0 for −1 < u < 0.

Finally, when u < −1, there holds

f′(u) = q(1 − (−u)^{q−1} ) ≤ 0.

Therefore, we also have f(u) ≥ f(−1) ≥ 0 for u ≤ −1.

Thus f(u) ≥ 0 on the whole real line and Lemma 24 is proved.

SVM Soft Margin Classifiers

Theorem 25 Let f : X → ℝ be measurable. Then

E(f) − E(f_{q}) ≤ \{ \begin{matrix}∥f − f_{q}∥_{L_{ρ_{X}}^{q}}^{q}, & if1 < q ≤ 2, \\ q2^{q−1} ∥f − f_{q}∥_{L_{ρ_{X}}^{q}}( 2^{q−1} + ∥f − f_{q}∥_{L_{ρ_{X}}^{q}}^{q−1} ) , & ifq > 2. \end{matrix}

Proof Since |f_{q}(x)| ≤ 1, by the second inequality of Lemma 17, for each x ∈ X we have

E(f|x) − E(f_{q}|x) = ∫_{Y}(1 − yf(x))_{+}^{q} − (1 − yf_{q}(x))_{+}^{q} dρ(y|x)
≤ q4^{q−1} |f(x) − f_{q}(x)| + q2^{q−1} |f(x) − f_{q}(x)|^{q}.

It follows that

E(f) − E(f_{q}) = ∫_{X}E(f|x) − E(f_{q}|x)dρ_{X} ≤ q4^{q−1} ∥f − f_{q}∥_{L_{ρ_{X}}^{1}} + q2^{q−1} ∥f − f_{q}∥_{L_{ρ_{X}}^{q}}^{q}. Then the inequality for the case q > 2 follows from the Hölder inequality.

Turn to the case 1 < q ≤ 2. It is sufficient to show that for each x ∈ X,

E(f|x) − E(f_{q}|x) ≤ |f(x) − f_{q}(x)|^{q}.  (63)

The definition (10) of f_{q} tells us that

(1 + f_{q}(x))^{q−1} = \frac{2^{q−1} (1 + f_{ρ}(x))}{\{(1 + f_{ρ}(x))^{1/(q−1)} + (1 − f_{ρ}(x))^{1/(q−1)} \}^{q−1}}

and

(1 − f_{q}(x))^{q−1} = \frac{2^{q−1} (1 − f_{ρ}(x))}{\{(1 + f_{ρ}(x))^{1/(q−1)} + (1 − f_{ρ}(x))^{1/(q−1)} \}^{q−1}} .

These expressions in connection with (45) imply

E(f|x) = \frac{(1 + f(x))_{+}^{q} (1 − f_{q}(x))^{q−1}}{(1 + f_{q}(x))^{q−1} + (1 − f_{q}(x))^{q−1}} + \frac{(1 − f(x))_{+}^{q} (1 + f_{q}(x))^{q−1}}{(1 + f_{q}(x))^{q−1} + (1 − f_{q}(x))^{q−1}}

and together with (48)

E(f_{q}|x) = \frac{2(1 − f_{q}(x))^{q−1} (1 + f_{q}(x))^{q−1}}{(1 + f_{q}(x))^{q−1} + (1 − f_{q}(x))^{q−1}} .

Thus (63) follows from the following inequality (by taking t = f(x) and θ = f_{q}(x)):

\begin{matrix}\frac{(1 + t)_{+}^{q} (1 − θ)^{q−1}}{(1 + θ)^{q−1} + (1 − θ)^{q−1}} + \frac{(1 − t)_{+}^{q} (1 + θ)^{q−1}}{(1 + θ)^{q−1} + (1 − θ)^{q−1}} \\ −2\frac{(1 − θ)^{q−1} (1 + θ)^{q−1}}{(1 + θ)^{q−1} + (1 − θ)^{q−1}} ≤ |t − θ|^{q}, ∀t ∈ ℝ,θ ∈ (−1,1). \end{matrix} (64)

What is left is to verify the inequality (64). Since −1 < θ < 1, we have

(1 + t)_{+}^{q} (1 − θ)^{q−1} = (1 − θ^{2})^{q−1} (1 + θ)( \frac{1 + t}{1 + θ} ) _{+}^{q} = (1 − θ^{2})^{q−1} (1 + θ)( 1 + \frac{t − θ}{1 + θ} ) _{+}^{q} .

By Lemma 24 with u = (t − θ)/(1 + θ), we see that

(1 + t)_{+}^{q} (1 − θ)^{q−1} ≤ (1 − θ^{2})^{q−1} (1 + θ)( 1 + | \frac{t − θ}{1 + θ} |^{q}+ q\frac{t − θ}{1 + θ} ) .

In the same way, by Lemma 24 with u = −(t − θ)/(1 − θ), we have

(1 − t)_{+}^{q} (1 + θ)^{q−1} ≤ (1 − θ^{2})^{q−1} (1 − θ)( 1 + | \frac{t − θ}{1 − θ} |^{q}− q\frac{t − θ}{1 − θ} ) .

Combining the above two estimates, we obtain

(1 + t)_{+}^{q} (1 − θ)^{q−1} + (1 − t)_{+}^{q} (1 + θ)^{q−1} ≤ 2(1 − θ^{2})^{q−1} + |t − θ|^{q}{(1 − θ)^{q−1} + (1 + θ)^{q−1} } .

This proves our claim (64), thereby Theorem 25.

Recall the K-functional given by (19).

Theorem 26 For each C > 0, there holds

D̃(C) ≤ K (f_{q}, \frac{1}{2C}).

Proof The case 1 < q ≤ 2 is an easy consequence of Theorem 25.

Turn to the case q > 2. The special choice f = 0 + 0 ∈ \overline{H}_{K} and the fact ∥f_{q}∥_{L_{ρ_{X}}^{q}} ≤ 1 tell us that for any t > 0,

K (f_{q},t) = inf_{{f∈\overline{H}_{K} \atop ∥f−fq∥_{L{q \atop ρ_{X}}}≤1}} \{q2^{q−1} (2^{q−1} + 1)∥f − f_{q}∥_{L_{ρ_{X}}^{q}} + t∥f^{∗}∥_{K}^{2}\} .

According to Theorem 25, for f ∈ \overline{H}_{K} with ∥f − f_{q}∥_{L_{ρ_{X}}^{q}} ≤ 1, we have

E(f) − E(f_{q}) ≤ q2^{q−1} (2^{q−1} + 1)∥f − f_{q}∥_{L_{ρ_{X}}^{q}}.

Thus,

D̃(C) = inf_{f∈\overline{H}_{K}} \{ E(f) − E(f_{q}) + \frac{1}{2C}∥f^{∗}∥_{K}^{2}\} ≤ K (f_{q}, \frac{1}{2C})

and the proof of Theorem 26 is complete.

We can now derive several observations from Theorem 26.

The first observation says that the SVM q-classifier converges when f_{q} lies in the closure of \overline{H}_{K} in L_{ρ_{X}}^{q}. In particular, for any Borel probability measure ρ, this is always the case if K is a universal kernel since C(X) is dense in L_{ρ_{X}}^{q}.

Corollary 27 If f_{q} lies in the closure of \overline{H}_{K} in L_{ρ_{X}}^{q}, then for every ε > 0 and 0 < δ < 1, there exist C_{ε} > 0, m_{0} ∈ ℕ and a sequence C_{m}with lim_{m→∞} C_{m}= ∞ such that

Prob_{z∈Z^{m}} {R (sgn(f_{z})) − R (f_{c}) ≤ ε} ≥ 1 − δ, ∀m ≥ m_{0}, C_{ε} ≤ C ≤ C_{m}.

Proof Since f_{q} lies in the closure of \overline{H}_{K} in L_{ρ_{X}}^{q}, for every ε > 0 there is some f_{ε} = f_{ε}^{∗}+ b_{ε} ∈ \overline{H}_{K} such that q2^{q}(2^{q−1} +1)∥f_{ε}−f_{q}∥_{L_{ρ_{X}}^{q}} ≤ ε^{2}/16. Take C_{ε} = 8∥f_{ε}^{∗}∥_{K}^{2}/ε^{2}. Then for any C ≥ C_{ε}, we have

\frac{1}{2C}∥f_{ε}^{∗}∥_{K}^{2} ≤ ε^{2}/16. Theorem 26 tells us that D̃(C) ≤ ε^{2}/8. Take m_{0} such that

\frac{2^{q+1} (1 + κ\sqrt{2C_{ε}})^{q/2}\sqrt{log(2/δ)}}{\sqrt{m_{0}}} ≤ \frac{ε^{2}}{8}

and

logN ( \frac{ε^{3}}{q4^{q+4} \sqrt{2C_{ε}}}) − \frac{3m_{0}ε^{4}}{4^{q+8}} ≤ log \frac{δ}{2}.

Also, we choose C_{m} such that

\frac{2^{q+1} (1 + κ\sqrt{2C_{m}})^{q/2}\sqrt{log(2/δ)}}{\sqrt{m}} < \frac{ε^{2}}{8}

and

logN ( \frac{ε^{3}}{q4^{q+4} \sqrt{2C_{m}}}) − \frac{3mε^{4}}{4^{q+8}} ≤ log \frac{δ}{2}.

Then by Corollary 5.2, ε(δ,m,C,β) ≤ \frac{ε^{2}}{8} when m ≥ m_{0} and C_{ε} ≤ C ≤ C_{m}. Together with Theorem 14, our conclusion is proved.

Our second observation from Theorem 26 concerns nonuniversal kernels which nonetheless ensures the convergence of the SVM q-classifier. The point here is that H_{K} is not dense in C(X), but after adding the offset the space \overline{H}_{K} becomes dense.

Example 2 Let K be a Mercer kernel on X = [0,1]:

K(x,y) = ∑_{j∈J} a_{j}(x · y)^{j},

where J is a subset of ℕ, a_{j} > 0 for each j ∈ J, and ∑_{j∈J} a_{j} < ∞. Note that this kernel satisfies

K_{0}(y) ≡ 0, hence f(0) = 0 for all f ∈ H_{K}. Hence the space H_{K} is not dense in C(X) and K is not an universal kernel. But if ∑_{j∈J} \frac{1}{j} = ∞, then \overline{H}_{K} is dense in C(X) (Zhou 2003a) and hence in L_{ρ_{X}}^{q}.

Therefore, the SVM q-classifier associated with the (identical) kernel K converges.

Remark 28 In Section 4 and the proof of Theorem 21, we have shown how the offset influences the sample error. Proposition 4 and Example 2 tell that it may also influence the approximation error. However, our analysis in the following two sections will not focus on this point and it may be an interesting topic.

In practical applications, one can use varying kernels for (3).

Definition 29 Let {K_{d}}_{d∈ℕ} be a sequence of Mercer kernels on X. We say that the SVM q-classifier associated with the kernels {K_{d}} converges if for a sequence {C_{m}}_{m∈ℕ} of positive numbers, f_{z} defined by (3) with K = K_{d} and C = C_{m} satisfies the following:

For every Borel probability measure ρ on Z, and 0 < δ < 1, ε > 0, for sufficiently large d there is some m_{d} ∈ ℕ such that

Prob_{z∈Z^{m}} {R (sgn(f_{z})) − R (f_{c}) ≤ ε} ≥ 1 − δ, ∀m ≥ m_{d}.

For a universal kernel K, one may take K_{d} to be identically K and the convergence holds. But the kernels could change such as the polynomial kernels (Boser, Guyon & Vapnik 1992). Our third observation from Theorem 26 is to confirm the convergence of the SVM q-classifiers with these kernels.

Proposition 30 For any 1 < q < ∞,n ∈ ℕ and X ⊂ ℝ^{n}, the SVM q-classifier associated with {K_{d}}_{d=1}^{∞}, the polynomial kernels K_{d}(x,y) = (1 + x · y)^{d}, converges.

Proposition 30 is a consequence of a quantitative result below.

Let P_{d} be the space of all polynomials of degree at most d. It is a RKHS H_{K_{d}} with the Mercer kernel K_{d}(x,y) = (1 + x · y)^{d}. The rich knowledge from approximation theory tells us that for an arbitrary Borel probability measure on Z, there is a sequence of polynomials {p_{d} ∈ P_{d}}_{d=1}^{∞} such that lim_{d→∞} ∥f_{q}− p_{d}∥_{L_{ρ_{X}}^{q}} = 0. The rate of this convergence depends on the regularity of the function f_{q} (hence the function f_{ρ}) and the marginal distribution ρ_{X}. With this in hand, we can now state the result on the convergence of the q-classifier with polynomial kernels K_{d}.

Corollary 31 Let X ⊂ ℝ^{n}, and ρ be an arbitrary Borel probability measure on Z. Let d ∈ ℕ and K_{d}(x,y) = (1 + x · y)^{d} be the polynomial kernel. Set ∥X∥:= sup_{x∈X}|x|. Let {p_{d} ∈ P_{d}}_{d=1}^{∞} satisfy E_{d} :=

∥f_{q} − p_{d}∥_{L_{ρ_{X}}^{q}} → 0 (as d → ∞). Set N := (n + d)!/(n!d!) + 1 and 0 < σ < \frac{2}{q}. Then there exists m_{q,σ} ∈ ℕ such that for m ≥ m_{q,σ} and C = m^{σ}, for every 0 < δ < 1, with confidence 1−δ there holds

R (sgn(f_{z})) − R (f_{c}) ≤ \sqrt{q}2^{q+1} \sqrt{E_{d}}+ \frac{∥p_{d}∥_{K_{d}}}{m^{σ/2}} + \frac{2^{q+5} (N log(\frac{2}{δ}))^{1/4}(1 + ∥X∥^{2})^{qd/8}}{m^{\frac{1}{4}− \frac{qσ}{8}}}.

Proof Take p_{d}^{∗} = p_{d} with zero offset in the K-functional. Then by Theorem 26,

D̃(C) ≤ K (f_{q}, \frac{1}{2C}) ≤ q2^{q−1} (2^{q−1} + 1)E_{d}+ \frac{1}{2C}∥p_{d}∥_{K_{d}}^{2}.

The covering numbers of the finite dimensional space P_{d} (e.g. Cucker & Zhou 2004) and (22) give us the estimate:

N (η) ≤ (κ + \frac{1}{κ̃} )( \frac{2}{η} + 1) ^{N},

where N − 1 = (n + d)!/(n!d!) is the dimension of the space P_{d}(ℝ^{n}). Also, κ = \sqrt{∥K_{d}∥_{∞}} ≤ (1 + ∥X∥^{2})^{d/2}.

Take C = m^{σ}. By Corollary 23, solving the equation (62) yields

ε(δ,m,C,β) ≤ \frac{(2^{q+5} \sqrt{N}+ \sqrt{log(κ + \frac{1}{κ̃})} (logm + log(2/δ))^{1/2}}{\sqrt{m}} + \frac{4^{q+2} κ^{\frac{q}{2}} \sqrt{log(\frac{2}{δ})}}{m^{\frac{1}{2}− \frac{qσ}{4}}}

which is bounded by 4^{5+q} \sqrt{N log(\frac{2}{δ})}κ^{q/2}m^{\frac{qσ}{4} − \frac{1}{2}} for m ≥ m_{q,σ}. Here m_{q,σ} is an integer depending on q,σ (but not on m, d or δ). Then for each m ≥ m_{q,σ}, with confidence 1 − δ the desired estimate holds true.

Remark 32 Note that P_{d} is a finite dimension space. Thus the norms ∥ · ∥_{K_{d}} and ∥ · ∥_{L_{ρ_{X}}^{q}} are equivalent for a fixed d when ρ_{X} is non-degenerate. It would be interesting to compare the norm ∥p∥_{K_{d}} with ∥p∥_{L_{ρ_{X}}^{q}} for p ∈ P_{d} as d tends to infinity.

Proof of Proposition 30. For every ε > 0, there exists some d_{0} ∈ ℕ such that \sqrt{q}2^{q−1} \sqrt{E_{d}}≤ ε/2 for every d ≥ d_{0}. Then by Corollary 31 we can find some m_{q,σ} ≤ m_{d} ∈ ℕ such that m_{d}^{−σ/2} ∥p_{d}∥_{K_{d}}≤ ε/4

and 2^{q+5} (N log(2/δ))^{1/4}(1 + ∥X∥^{2})^{dq/8}m_{d}^{\frac{qσ}{8} − \frac{1}{4}} ≤ ε/4. Then for any m ≥ m_{d} we have R (sgn(f_{z})) − R (f_{c}) ≤ ε with confidence 1 − δ. This proves Proposition 30.

7. Rate of Convergence for the q-norm Soft Margin Classifier

Corollary 23 and Theorem 26 enable us to get the convergence rate for the SVM q-classifier. The rate depends on the K-functional K (f_{q},t). It can be characterized by the quantity (Smale & Zhou 2003, Zhou 2003b)

I_{q}(g,R) := inf_{{f∈\overline{H}_{K} \atop ∥f^{∗}∥_{K}≤R}} \{∥g − f∥_{L_{ρ_{X}}^{q}}\} .  (65)

Define

J_{q}(f_{q},R) := \{ \begin{matrix}(I_{q}(f_{q},R))^{q}, & if 1 < q ≤ 2, \\ q2^{q−1} (2^{q−1} + 1)I_{q}(f_{q},R), & if q > 2. \end{matrix}

Then the following corollary holds true.

Corollary 33 For any t > 0 there holds

K (f_{q},t) ≤ inf_{R>0} {J_{q}(f_{q},R) + tR^{2}}.

One may choose appropriate R to estimate the convergence rate of K (f_{q},t), which together with Corollary 23 gives the convergence rate of the V -risk and a strategy of choosing the regularization parameter C. In general, the choice of R depends on the regularity of f_{q} and the kernel K. Let us demonstrate this by examples.

In what follows let X ⊂ ℝ^{n} have Lipschitz boundary and ρ be a probability measure such that dρ_{X} = dx is the Lebesgue measure. Consider q = 2 and thus f_{q} = f_{ρ}. We use the approximation error studied in Smale & Zhou (2003) (see also Niyogi & Girosi (1996) for related discussion):

I_{2}^{∗}(g,R) := inf_{{f^{∗}∈H_{K} \atop ∥f^{∗}∥_{K}≤R}} \{∥g − f^{∗}∥_{L^{2}}\}

to bound the term I_{2}(f_{ρ},R). With the choice b_{f} = 0 we obtain

I_{2}(f_{ρ},R) ≤ I_{2}^{∗}(f_{ρ},R).

Note that we disregard the influence of the offset here and thus the rate need not be optimal. The first example includes spline kernels (Wahba 1990).

Example 3 Let X ⊂ ℝ^{n} and K be a Mercer kernel such that H_{K} is the Sobolev space H^{r}(X) with r > n/2. If f_{ρ} lies in the Sobolev space H^{s}(X) with 0 < s < r, then

E(π(f_{z})) − E(f_{ρ}) = O( \begin{matrix}√ & \overline{logm + C} \\ √ & \overline{m} \end{matrix} + \frac{C^{n/(4r+3n)}}{m^{2r/(4r+3n)}}) + O( C^{−s/r} ) .

Thus, C should be chosen such that C → ∞, C/m → 0 as m → ∞.

Proof It was shown in Smale & Zhou (2003, Theorem 3.1) that for 0 < θ < 1, I_{2}^{∗}(f_{ρ},R) = O(R^{−θ/(1−θ)} ) if and only if f_{ρ} lies in the interpolation space (L_{ρ_{X}}^{2},H_{K})_{θ,∞}. It is well known that H^{s}(X) ⊂ (L^{2},H^{r}(X))_{s/r,∞} for 0 < s < r. Here H_{K} = H^{r}(X) and dρ_{X} = dx. Therefore, the assumption f_{ρ} ∈ H^{s}(X) tells us that f_{ρ} ∈ (L_{ρ_{X}}^{2},H_{K})_{s/r,∞}. Hence there holds

I_{2}(f_{ρ},R) ≤ I_{2}^{∗}(f_{ρ},R) ≤ C_{ρ}R^{−s/(r−s)}

for some constant C_{ρ}. Choose R = C_{ρ}^{(r−s)/r} C^{(r−s)/2r} to obtain

K (f_{ρ}, \frac{1}{2C}) ≤ (I_{2}(f_{ρ},R))^{2}+ \frac{R^{2}}{2C} ≤ \frac{3}{2}C_{ρ}^{2(r−s)/r} C^{−s/r} .

Using the well known covering number estimates for Sobolev spaces

logN (B_{R},η) ≤ C_{r}( \frac{1}{η}) ^{n/r}

and solving the equation (62), we see that

ε^{∗} ≤ 2^{6}\sqrt{\frac{logκ + logm + logC + log(2/δ)}{m}} + 2^{6+3n/(4r)} \sqrt{C_{r}}\frac{C^{n/(4r+3n)}}{m^{2r/(4r+3n)}}.

This proves the conclusion.

Example 4 Let σ > 0,s > 0 and K be the Gaussian kernel K(x,y) = exp\{−\frac{|x−y|^{2}}{σ^{2}} \} .

(a) If f_{ρ} lies in the interpolation space (L_{ρ_{X}}^{2},H_{K})_{θ,∞} for some 0 < θ < 1, that is, K (f_{ρ},t) ≤ C_{θ}t^{θ} for some constant C_{θ}, then for any 0 < δ < 1, with confidence 1 − δ, there holds

E(π(f_{z})) − E(f_{ρ}) = O( \begin{matrix}√ & \overline{C + (logm)^{n+1}} \\ √ & \overline{m} \end{matrix} ) + O( C^{−θ} ) .

This implies the parameter C should be taken to satisfy C → ∞ and C/m → 0 as m → ∞. An asymptotic optimal choice is C = O(m^{1/(1+2θ)} ). With this choice, the convergence rate is O(m^{−θ/(1+2θ)} ).

(b) If f_{ρ} ∈ H^{s}(X) with s > 0, then for any 0 < δ < 1, with confidence 1 − δ, we have

E(π(f_{z})) − E(f_{ρ}) = O( \begin{matrix}√ & \overline{C + (logm)^{n+1}} \\ √ & \overline{m} \end{matrix} ) + O( (logC)^{−s/2} ).

An asymptotically optimal choice is C = O( \frac{m}{(logm)^{s}}) which gives the convergence rate O((logm)^{−s/2} ).

Proof Solving the equation (62) with the covering number estimate (23) yields

ε^{∗} = O( \begin{matrix}√ & \overline{(1 + c)(logC + logm)^{n+1}} \\ √ & \overline{m} \end{matrix} ) .

Then the statement in (a) follows easily from Corollary 23, Theorem 21 and Corollary 33.

To see the conclusion in (b), we notice that the assumption f_{ρ} ∈ H^{s}(X) provides the approximation error estimates (Smale & Zhou 2003, Zhou 2003b)

I_{2}(f_{ρ},R) ≤ I_{2}^{∗}(f_{ρ},R) ≤ C_{s}(logR)^{−s/4}

for every R > C_{s}, where C_{s} is a constant depending on s,σ,n and the Sobolev norm of f_{ρ}. Choose R = \sqrt{2C}(logC)^{−s/4} to obtain

K (f_{ρ}, \frac{1}{2C}) ≤ (I_{2}(f_{ρ},R))^{2}+ \frac{R^{2}}{2C} ≤ (2^{s}C_{s}^{2}+ 1)(logC)^{−s/2} .

Then the desired bound follows from Theorem 26 and the above established bound for ε^{∗}.

It was shown in Smale & Zhou (2003) that for the Gaussian kernel in Example 4, I_{2}^{∗}(g,R) = O(R^{−ϵ}) with ϵ > 0 only if g is C^{∞}. Hence logarithmic convergence rate is expected for a Sobolev function f_{ρ}. However, in practice, one often chooses the different variances σ of the Gaussian kernel according to the different sample size m. With this flexibility, the regularization error can be improved greatly and polynomial convergence rates are possible.

Acknowledgments

The authors would like to thank Professor Zhen Wang for his helpful discussion on the best constants in Theorem 14 and Theorem 25. They are also grateful to the referees for the constructive suggestions and comments.

This work is supported partially by the Research Grants Council of Hong Kong [Project No. CityU 1087/02P] and by City University of Hong Kong [Project No. 7001442]. The corresponding author is Ding-Xuan Zhou. Yiming Ying is on leave from Institute of Mathematics, Chinese Academy of Science, Beijing 100080, P. R. CHINA.

Appendix. Error Comparison for a General Loss Function

In this appendix for a general convex loss function we bound the excess misclassification error by the excess V -risk. Here the loss function takes the form

V (y,f(x)) = ϕ(yf(x))

for a univariate function ϕ: ℝ → ℝ_{+} .

For each x ∈ X, we denote

E(f|x) := ∫_{Y}V (y,f(x))dρ(y|x),  (66)

then E(f|x) = Q(η(x),f(x)). Here Q: [0,1] × (ℝ ∪ {±∞}) → ℝ_{+} is given by

Q(η,f) = ηϕ(f) + (1 − η)ϕ(−f),

and η: X → ℝ is defined by η(x) := P(Y = 1|x). Set

f_{ϕ}^{∗}(η) := arg min_{f∈ℝ∪{±∞}} Q(η,f).

Then f_{ρ}^{V}(x) = f_{ϕ}^{∗}(η(x)). The main result of Zhang (2004) can be stated as follows.

Theorem A Let ϕ be convex. Assume f_{ϕ}^{∗}(η) > 0 when η > 0.5. Assume there exists c > 0 and s ≥ 1 such that for all η ∈ [0,1],

|0.5 − η|^{s} ≤ c^{s}(Q(η,0) − Q(η,f_{ϕ}^{∗}(η))) ,  (67)

then for any measurable function f(x):

R (sgn(f)) − R (f_{c}) ≤ 2c( E(f) − E(f_{ρ}^{V})) ^{1/s}.

Further analysis was made by Bartlett, Jordan & McAuliffe (2003). For example, it was proved in Bartlett, Jordan & McAuliffe (2003, Theorem 6) that for a convex function ϕ, f_{ϕ}^{∗}(η) > 0 for any η > 0.5 if and only if ϕ is differentiable at 0 and ϕ′(0) < 0. Borrowing some ideas from Bartlett, Jordan & McAuliffe (2003), we can derive a simple criterion for the condition (67) with s = 2. The existence of ϕ′′(0) means that the function ϕ′(x) is well defined in a neighborhood of 0 and is differentiable at 0. Note that the convexity of ϕ implies ϕ′′(0) ≥ 0.

Theorem 34 Let ϕ: ℝ → ℝ_{+} be a convex function such that ϕ′′(0) exists. If ϕ′(0) < 0 and ϕ′′(0) > 0, then (67) holds for s = 2. Hence for any measurable function f:

R (sgn(f)) − R (f_{c}) ≤ 2c\sqrt{E(f) − E(f_{ρ}^{V})} .

Proof By the definition of ϕ′′(0), there exists some 1/2 ≥ c_{0} > 0 such that

| \frac{ϕ′(f) − ϕ′(0)}{f} − ϕ′′(0)| ≤ \frac{ϕ′′(0)}{2}, ∀f ∈ [−c_{0},c_{0}].

This implies

ϕ′(0) + ϕ′′(0)f − \frac{ϕ′′(0)}{2}|f| ≤ ϕ′(f) ≤ ϕ′(0) + ϕ′′(0)f + \frac{ϕ′′(0)}{2}|f|.

If η > 1/2, then for 0 ≤ f ≤ c_{0},

\frac{∂Q}{∂f}(η,f) = ηϕ′(f) − (1 − η)ϕ′(−f) ≤ (2η − 1)ϕ′(0) + ϕ′′(0)f + \frac{ϕ′′(0)}{2}f.

Thus for 0 ≤ f ≤ Δ_{η} := min\{\frac{−ϕ′(0)}{ϕ′′(0)} (η − \frac{1}{2}),c_{0}\}, we have

\frac{∂Q}{∂f}(η,f) ≤ (2η − 1)ϕ′(0) + \frac{3}{2}ϕ′′(0)\frac{−ϕ′(0)}{ϕ′′(0)} (η − \frac{1}{2}) ≤ \frac{ϕ′(0)}{2}(η − \frac{1}{2}) < 0.

Therefore as a function of the variable f, Q(η,f) is strictly decreasing on the interval [0,Δ_{η}]. But f_{ϕ}^{∗}(η) > 0 is its minimal point, hence

Q(η,0) − Q(η,f_{ϕ}^{∗}(η)) ≥ Q(η,0) − Q(η,Δ_{η}) ≥ −\frac{ϕ′(0)}{2}(η − \frac{1}{2})Δ_{η}.

When \frac{−ϕ′(0)}{ϕ′′(0)} (η − \frac{1}{2}) > c_{0}, we have Δ_{η} = c_{0} ≥ 2c_{0}(η − \frac{1}{2}). Hence

Q(η,0) − Q(η,f_{ϕ}^{∗}(η)) ≥ \frac{−ϕ′(0)}{2} min\{ 2c_{0}, \frac{−ϕ′(0)}{ϕ′′(0)} \} (η − \frac{1}{2})^{2}.

That is, (67) holds with s = 2 and

c = max\{ \frac{\sqrt{2ϕ′′(0)}}{−ϕ′(0)},\sqrt{\frac{1}{−ϕ′(0)c_{0}}} \} .

The proof for η < 1/2 is the same by estimating the upper bound of \frac{∂Q}{∂f}(η,f) for f < 0.

Turn to the special loss function V = V_{q} given in (6) by ϕ(t) = (1 − t)_{+}^{q}. Applying Theorem 34, we see that the function ϕ satisfies ϕ′(0) = −q < 0 and ϕ′′(0) = q(q − 1) > 0. This verifies (40) and the constant c can be obtained from the proof of Theorem 34.

References

N. Aronszajn. Theory of reproducing kernels. Trans. Amer. Math. Soc. 68 (1950), 337–404, 1950.

A. R. Barron. Complexity regularization with applications to artificial neural networks. G. Roussa, editor, in Nonparametric Functional Estimation, Kluwer, Dortrecht, pages 561–576, 1990.

P. L. Bartlett. The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE Trans. Inform. Theory, 44: 525–536, 1998.

P. L. Bartlett, O. Bousquet, and S. Mendelson. Local Rademacher complexities. Annals Statis., 2004, to appear.

P. L. Bartlett, M. I. Jordan, and J. D. McAuliffe. Convexity, classification, and risk bounds. Preprint, 2003.

B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop of Computational Learning Theory, 5, Pittsburgh, ACM, pages 144–152, 1992.

O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learning Res., 2: 499–526, 2002.

C. Cortes and V. Vapnik. Support-vector networks. Mach. Learning, 20: 273–297, 1995.

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge Uni-

versity Press, 2000. F. Cucker and S. Smale. On the mathematical foundations of learning. Bull. Amer. Math. Soc., 39:

1–49, 2001. F. Cucker and D. X. Zhou. Learning Theory: an Approximation Theory Viewpoint. Monograph

manuscript in preparation for Cambridge University Press, 2004. L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer-

Verlag, New York, 1997. T. Evgeniou, M. Pontil, and T. Poggio. Regularization networks and support vector machines. Adv.

Comput. Math., 13: 1–50, 2000. W. S. Lee, P. Bartlett, and R. Williamson. The importance of convexity in learning with least square

loss. IEEE Trans. Inform. Theory, 44: 1974–1980, 1998. Y. Lin. Support vector machines and the Bayes rule in classification. Data Mining and Knowledge

Discovery 6: 259–275, 2002. S. Mendelson. Improving the sample complexity using global data. IEEE Trans. Inform. Theory 48:

1977–1991, 2002. S. Mukherjee, R. Rifkin, and T. Poggio. Regression and classification with regularization. In D. D.

Denison, M. H. Hansen, C. C. Holmes, B. Mallick, and B. Yu, eds., Lecture Notes in Statistics: Nonlinear Estimation and Classification, Springer-Verlag, New York, pages 107–124, 2002.

P. Niyogi and F. Girosi. On the relationship between generalization error, hypothesis complexity,

and sample complexity for radial basis functions. Neural Comp., 8: 819–842, 1996. M. Pontil. A note on different covering numbers in learning theory. J. Complexity 19: 665–671,

2003. F. Rosenblatt. Principles of Neurodynamics. Spartan Book, New York, 1962. J. Shawe-Taylor, P. L. Bartlett, R. C. Williamson, and M. Anthony. Structural risk minimization

over data-dependent hierarchies. IEEE Trans. Inform. Theory 44: 1926–1940, 1998. S. Smale and D. X. Zhou. Estimating the approximation error in learning theory. Anal. Appl., 1:

17–41, 2003. S. Smale and D. X. Zhou. Shannon sampling and function reconstruction from point values. Bull.

Amer. Math. Soc. , 41: 279–305, 2004. I. Steinwart. On the influence of the kernel on the consistency of support vector machines. Journal

of machine learning research, 2: 67–93, 2001. I. Steinwart. Support vector machines are universally consistent. J. Complexity, 18: 768–791, 2002. A. Tikhonov and V. Arsenin. Solutions of Ill-posed Problems. W. H. Winston, 1977.

A. W. van der Vaart and J. A. Wellner. Weak Convergence and Empirical Processes. Springer-

Verlag, New York, 1996. V. Vapnik. Estimation of Dependences Based on Empirical Data. Springer-Verlag, New York, 1982. V. Vapnik. Statistical Learning Theory. John Wiley & Sons, 1998. G. Wahba. Spline models for observational data. SIAM, 1990. G. Wahba. Support vector machines, reproducing kernel Hilbert spaces and the Randomized GACV.

In Schölkopf, Burges and Smola, eds., Advances in Kernel Methods - Support Vector Learning, MIT Press, pages 69–88, 1999.

R. C. Williamson, A. J. Smola, and B. Schölkopf. Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators. IEEE Trans. Inform. Theory 47: 2516–2532, 2001.

Q. Wu and D. X. Zhou. Analysis of support vector machine classification. Preprint, 2004. T. Zhang. Statistical behavior and consistency of classification methods based on convex risk mini-

mization. Annals Statis., 32: 56–85, 2004. D. X. Zhou. The covering number in learning theory. J. Complexity, 18: 739–767, 2002. D. X. Zhou. Capacity of reproducing kernel spaces in learning theory. IEEE Trans. Inform. Theory,

49: 1743–1752, 2003a. D. X. Zhou. Density problem and approximation error in learning theory. Preprint, 2003b.